The Erdos-Faber-Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on$n$vertices is at most n. Erdös considered this to be one of his three most favorite combinatorial problems and offered a $500 reward for a proof of this conjecture. We prove this conjecture for every large n. Here, we also provide a randomised algorithm to find such a colouring in polynomial time with high probability.

We introduce a notion of the crux of a graph $G$, measuring the order of a smallest dense subgraph in $G$. This simple-looking notion leads to some generalizations of known results about cycles, offering an interesting paradigm of “replacing average degree by crux.” In particular, we prove that every graph contains a cycle of length linear in its crux. Long proved that every subgraph of a hypercube $Q^m$ (resp., discrete torus $C_3^m$) with average degree $d$ contains a path of length $2^{d/2}$ (resp., $2^{d/4}$) and conjectured that there should be a path of length $2^{d}-1$ (resp., $3^{d/2}-1$). As a corollary of our result, together with isoperimetric inequalities, we close these exponential gaps giving asymptotically optimal bounds on long paths in hypercubes, discrete tori, and more generally Hamming graphs. We also consider random subgraphs of $C_4$-free graphs and hypercubes, proving near optimal lower bounds on the lengths of long cycles.

Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made more challenging due to correlations between the occurrence of different edges. We develop an edge-switching technique for hypergraphs which allows us to show that these correlations are limited for a large range of densities. This extends some previous results of Kim, Sudakov, and Vu for graphs. From our results we deduce several corollaries on subgraph counts in random $d$-regular hypergraphs. We also prove a conjecture of Dudek, Frieze, Ruciński, and Šileikis on the threshold for the existence of an $\ell$-overlapping Hamilton cycle in a random $d$-regular $r$-graph. Moreover, we apply our results to prove bounds on the query complexity of testing subgraph-freeness. The problem of testing subgraph-freeness in the general graphs model was first studied by Alon, Kaufman, Krivelevich, and Ron, who obtained several bounds on the query complexity of testing triangle-freeness. We extend some of these previous results beyond the triangle setting and to the hypergraph setting.

We provide a combinatorial characterization of all testable properties of k-graphs (i.e. k-uniform hypergraphs). Here, a k-graph property P is testable if there is a randomized algorithm which makes a bounded number of edge queries and distinguishes with probability 2/3 between k-graphs that satisfy P and those that are far from satisfying P. For the 2-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. Our results for the k-graph setting are in contrast to those of Austin and Tao, who showed that for the somewhat stronger concept of local repairability, the testability results for graphs do not extend to the 3-graph setting.

We show that if $T$ is a strongly $10^9k^6\log(2k)$-connected tournament, there exists a partition $A,B$ of $V(T)$ such that each of $T[A]$, $T[B]$, and $T[A,B]$ is strongly $k$-connected. This provides solutions to tournament analogues of two partition conjectures of Thomassen regarding highly connected graphs. We also discuss spanning linkages as well as nonseparating subdivisions in highly connected tournaments.

Let $F$ be a strictly $k$-balanced $k$-uniform hypergraph with $e(F)\geq |F|-k+1$ and maximum co-degree at least two. The random greedy $F$-free process constructs a maximal $F$-free hypergraph as follows. Consider a random ordering of the hyperedges of the complete $k$-uniform hypergraph $K_n^k$ on $n$ vertices. Start with the empty hypergraph on $n$ vertices. Successively consider the hyperedges $e$ of $K_n^k$ in the given ordering and add $e$ to the existing hypergraph provided that $e$ does not create a copy of $F$. We show that asymptotically almost surely this process terminates at a hypergraph with $\tilde{O}(n^{k-(|F|-k)/(e(F)-1)})$ hyperedges. This is best possible up to logarithmic factors.

Let $n$ be sufficiently large and suppose that $G$ is a digraph on $n$ vertices where every vertex has in- and outdegree at least $n/2$. We show that $G$ contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla, where the threshold is $n/2+1$. Our result is best possible and improves on an approximate result by Häggkvist and Thomason.

We show that every sufficiently large $r$-regular digraph $G$ which has linear degree and is a robust outexpander has an approximate decomposition into edge-disjoint Hamilton cycles, i.e., $G$ contains a set of $r-o(r)$ edge-disjoint Hamilton cycles. Here $G$ is a robust outexpander if for every set $S$ which is not too small and not too large, the “robust” outneighborhood of $S$ is a little larger than $S$. This generalizes a result of Kühn, Osthus, and Treglown on approximate Hamilton decompositions of dense regular oriented graphs. It also generalizes a result of Frieze and Krivelevich on approximate Hamilton decompositions of quasirandom (di)graphs. In turn, our result is used as a tool by Kühn and Osthus to prove that any sufficiently large $r$-regular digraph $G$ which has linear degree and is a robust outexpander even has a Hamilton decomposition.

The famous Pósa conjecture states that every graph of minimum degree at least $2n/3$ contains the square of a Hamilton cycle. This has been proved for large $n$ by Komlós, Sarközy, and Szemerédi. Here we prove that if $p \ge n^{-1/2+\varepsilon}$, then asymptotically almost surely, the binomial random graph $G_{n,p}$ contains the square of a Hamilton cycle. This provides an “approximate threshold” for the property in the sense that the result fails to hold if $p\le n^{-1/2}$.

We show that for each $\beta > 0$, every digraph G of sufficiently large order n whose outdegree and indegree sequences $d_1^+ \leq \cdots \leq d_n^+$ and $d_1^- \leq \cdots \leq d_n^-$ satisfy $d_i^+, d_i^- \geq \min{\{i + \beta n, n/2\}}$ is Hamiltonian. In fact, we can weaken these assumptions to (i) $d_i^+ \geq \min{\{i + \beta n, n/2\}}$ or $d^-_{n - i - \beta n} \geq n-i$, (ii) $d_i^- \geq \min{\{i + \beta n, n/2\}}$ or $d^+_{n - i - \beta n} \geq n-i$, and still deduce that G is Hamiltonian. This provides an approximate version of a conjecture of Nash-Williams from 1975 and improves a previous result of Kühn, Osthus, and Treglown.

We say that a graph G has a perfect H-packing (also called an H-factor) if there exists a set of disjoint copies of H in G which together cover all the vertices of G. Given a graph H, we determine, asymptotically, the Ore-type degree condition which ensures that a graph G has a perfect H-packing. More precisely, let $\delta_{\rm Ore}(H,n)$ be the smallest number k such that every graph G whose order n is divisible by $|H|$ and with $d(x)+d(y)\geq k$ for all nonadjacent $x\not=y\in V(G)$ contains a perfect H-packing. We determine $\lim_{n\to\infty}\delta_{\rm Ore}(H,n)/n$.

We prove that every graph of minimum degree at least r and girth at least 27 contains a subdivision of $K_{r+1}$. This implies that the conjecture of Hajós, that every graph of chromatic number at least r contains a subdivision of $K_r$, is true for graphs of girth at least 27. This conjecture is known to be false in general.

Given 0 < p < 1, we prove that a pseudorandom graph G with edge density p and sufficiently large order has the following property: Consider any red/blue-coloring of the edges of G and let r denote the proportion of edges which have the color red. Then there is a Hamilton cycle C so that the proportion of red edges of C is close to r. The analogue also holds for perfect matchings instead of Hamilton cycles. We also prove a bipartite version which is used elsewhere to give a minimum-degree condition for the existence of a Hamilton cycle in a 3-uniform hypergraph.