A 3-connected graph $G$ is weakly 3-connected if, for every edge $e$ of $G$, at most one of $G\backslash e$ and $G/e$ is 3-connected. The main result of this paper is that any weakly 3-connected graph can be reduced to $K_4$ by a sequence of simple operations. This extends a result of Dawes [5] on minimally 3-connected graphs.

We consider the complexity of the two-variable rank generating function, $S$, of a graphic 2-polymatroid. For a graph $G$, $S$ is the generating function for the number of subsets of edges of $G$ having a particular size and incident with a particular number of vertices of $G$. We show that for any $x, y \in \mathbb{Q}$ with $xy \not =1$, it is #P-hard to evaluate $S$ at $(x,y)$. We also consider the $k$-thickening of a graph and computing $S$ for the $k$-thickening of a graph.

Motivated by a property of linear resistive electrical networks, we introduce the class of Rayleigh matroids. These form a subclass of the balanced matroids defined by Feder and Mihail [9] in 1992. We prove a variety of results relating Rayleigh matroids to other well-known classes – in particular, we show that a binary matroid is Rayleigh if and only if it does not contain $\mathcal{S}_{8}$ as a minor. This has the consequence that a binary matroid is balanced if and only if it is Rayleigh, and provides the first complete proof in print that $\mathcal{S}_{8}$ is the only minor-minimal binary non-balanced matroid, as claimed in [9]. We also give an example of a balanced matroid which is not Rayleigh.

We derive the distribution of the number of links and the average weight for the shortest path tree (SPT) rooted at an arbitrary node to $m$ uniformly chosen nodes in the complete graph of size $N$ with i.i.d. exponential link weights. We rely on the fact that the full shortest path tree to all destinations (ie, $m=N-1$) is a uniform recursive tree to derive a recursion for the generating function of the number of links of the SPT, and solve this recursion exactly.

The explicit form of the generating function allows us to compute the expectation and variance of the size of the subtree for all $m$. We also obtain exact expressions for the average weight of the subtree.

In this paper, we give sharp upper bounds on the maximum number of edges in very unbalanced bipartite graphs not containing any cycle of length 6. To prove this, we estimate roughly the sum of the sizes of the hyperedges in triangle-free multi-hypergraphs.

Let $s$ and $t$ be integers satisfying $s \geq 2$ and $t \geq 2$. Let $S$ be a tree of size $s$, and let $P_t$ be the path of length $t$. We show in this paper that, for every edge-colouring of the complete graph on $n$ vertices, where $n=224(s-1)^2t$, there is either a monochromatic copy of $S$ or a rainbow copy of $P_t$. So, in particular, the number of vertices needed grows only linearly in $t$.

Let ${P_s(d)}$ be the probability that a random 0/1-matrix of size $d \times d$ is singular, and let ${E(d)}$ be the expected number of 0/1-vectors in the linear subspace spanned by $d-1$ random independent 0/1-vectors. (So ${E(d)}$ is the expected number of cube vertices on a random affine hyperplane spanned by vertices of the cube.)

We prove that bounds on ${P_s(d)}$ are equivalent to bounds on ${E(d)}$: \[{P_s(d)} = \bigg(2^{-d} {E(d)} + \frac{d^2}{2^{d+1}} \bigg) (1 + \so(1)). \] We also report on computational experiments pertaining to these numbers.

Let $P_1, {\ldots}\,,P_k$ be $k$ vertex-disjoint paths in a graph $G$ where the ends of $P_i$ are $x_i$, and $y_i$. Let $H$ be the subgraph induced by the vertex sets of the paths. We find edge bounds $E_1(n)$, $E_2(n)$ such that:

1. if $e(H) \geq E_1(|V(H)|)$, then there exist disjoint paths $P_1', {\ldots}\,,P_k'$ where the ends of $P_i'$ are $x_i$ and $ y_i$ such that $|\bigcup_i V(P_i)| > |\bigcup_i V(P_i')|$;

2. if $e(H) \geq E_2(|V(H)|)$, then there exist disjoint paths $P_1', {\ldots}\,, P_k'$ where the ends of $P_i'$ are $x_i'$ and $y_i'$ such that $|\bigcup_i V(P_i)| > |\bigcup_i V(P_i')|$ and $\{ x_1, {\ldots}\,, x_k \} = \{ x_1' , {\ldots}\, , x_k' \}$ and $\{ y_1, {\ldots}\,, y_k \} = \{ y_1', {\ldots}\,, y_k'\}$.

The bounds are the best possible, in that there exist arbitrarily large graphs $H'$ with $e(H') = E_i (H') - 1$ without the properties stipulated in 1 and 2.

Motivated by a scheduling problem that arises in the study of optical networks, we prove the following result, which is a variation of a conjecture of Haxell, Wilfong and Winkler.

Let $k,n$ be two positive integers, let $w_{sj}, 1 \leq s \leq n, 1 \leq j \leq k$ be nonnegative reals satisfying $\sum_{j=1}^k w_{sj}< 1/n$ for every $1 \leq s \leq n$ and let $d_{sj}$ be arbitrary nonnegative reals. Then there are real numbers $x_1, x_2, {\ldots}\,,x_n$ such that for every $j$, $1 \leq j \leq k$, the $n$ cyclic closed intervals $I_s^{(j)}=[x_s+d_{sj},x_s+d_{sj}+w_{sj}]$, $(1 \leq s \leq n)$, where the endpoints are reduced modulo 1, are pairwise disjoint on the unit circle.

The proof is based on some properties of multivariate polynomials and on the validity of the Dyson conjecture.

We put the final piece into a puzzle first introduced by Bollobás, Erdõs and Szemerédi in 1975. For arbitrary positive integers $n$ and $r$ we determine the largest integer $\Delta=\Delta (r,n)$, for which any $r$-partite graph with partite sets of size $n$ and of maximum degree less than $\Delta$ has an independent transversal. This value was known for all even $r$. Here we determine the value for odd $r$ and find that $\Delta(r,n)=\Delta(r-1,n)$. Informally this means that the addition of an oddth partite set does not make it any harder to guarantee an independent transversal.

In the proof we establish structural theorems which could be of independent interest. They work for all$r\geq 7$, and specify the structure of slightly sub-optimal graphs for even$r\geq 8$.

There are several known results asserting that undirected graphs can be partitioned in a way that satisfies various constraints imposed on the degrees. The corresponding results for directed graphs, where degrees are replaced by outdegrees, often fail, and when they do hold, they are usually much harder, and lead to fascinating open problems. In this note we list three problems of this type, and mention the undirected analogues. All graphs and digraphs considered here are simple, that is, they have no loops and no multiple edges.

The problem we consider here is based on the following question posed by François Jaeger in 1981 at a combinatorics meeting in Eger (Hungary):

Let $P=(X,\le)$ be a finite partially ordered set. That is, $X$ is a finite ground set and $\le$ is a partial ordering on $X$ (a reflexive, transitive, and weakly antisymmetric relation). An $x\in X$ is an immediate predecessor of a $y\in X$ if $x<y$ and there is no $z\in X$ with $x<z<y$ (where $x<y$ means that $x\le y$ and $x\ne y$). The Hasse diagram$H(P)$ is the undirected graph with vertex set $X$ and with $\{x,y\}$ forming an edge if $x$ is an immediate predecessor of $y$ or if $y$ is an immediate predecessor of $x$. We denote bya $\alpha(H(P))$ the independence number of the Hasse diagram, that is, the maximum possible size of a subset $I\subseteq X$ such that no element of $I$ is an immediate predecessor (in $P$) of another element of $I$. This quantity should not be confused with the maximum size of an antichain in $P$, which is sometimes denoted by $\alpha(P)$.

In the present work we prove the following conjecture of Erdős, Roth, Sárközy and T. Sós: Let $f$ be a polynomial of integer coefficients such that $2|f(z)$ for some integer $z$. Then, for any $k$-colouring of the integers, the equation $x+y=f(z)$ has a solution in which $x$ and $y$ have the same colour. A well-known special case of this conjecture referred to the case $f(z)=z^2$.

A Hamiltonian cycle in a 3-uniform hypergraph is a cyclic ordering of the vertices in which every three consecutive vertices form an edge. In this paper we prove an approximate and asymptotic version of an analogue of Dirac's celebrated theorem for graphs: for each γ>0 there exists n0 such that every 3-uniform hypergraph on $n\geq n_0$ vertices, in which each pair of vertices belongs to at least $(1/2+\gamma)n$ edges, contains a Hamiltonian cycle.

We elucidate the close connection between the repulsive lattice gas in equilibrium statistical mechanics and the Lovász Local Lemma in probabilistic combinatorics. We show that the conclusion of the Lovász Local Lemma holds for dependency graph $G$ and probabilities $\{p_x\}$ if and only if the independent-set polynomial for $G$ is nonvanishing in the polydisc of radii $\{p_x\}$. Furthermore, we show that the usual proof of the Lovász Local Lemma – which provides a sufficient condition for this to occur – corresponds to a simple inductive argument for the nonvanishing of the independent-set polynomial in a polydisc, which was discovered implicitly by Shearer [28] and explicitly by Dobrushin [12, 13]. We also present a generalization of the Lovász Local Lemma that allows for ‘soft’ dependencies. The paper aims to provide an accessible discussion of these results, which are drawn from a longer paper [26] that has appeared elsewhere.