Search

In 1994, Erdős, Gyárfás and Łuczak posed the following problem: given disjoint vertex sets V 1 , ... , V n of size k , with exactly one edge between any pair V i , V j , how large can n be such that there will always be an independent transversal? They showed that the maximal n is at most (1 + o (1)) k 2 , by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a 2 e -factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if n ≤ (1 − o (1)) k 2 , there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are 'locally sparse', meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global maximum degree condition for the existence of an independent transversal. We show that this can be relaxed to an average degree condition. We can also use our new theorem to establish tight bounds for a more general version of the Erdős–Gyárfás–Łuczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turán numbers of complete bipartite graphs, which might be of independent interest. [ABSTRACT FROM AUTHOR]

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph K 2 n , there exists a decomposition of K 2 n into isomorphic rainbow spanning trees. This settles conjectures of Brualdi–Hollingsworth (from 1996) and Constantine (from 2002) for large graphs. [ABSTRACT FROM AUTHOR]

We study the F -decomposition threshold δ F for a given graph F. Here an F -decomposition of a graph G is a collection of edge-disjoint copies of F in G which together cover every edge of G. (Such an F -decomposition can only exist if G is F -divisible, i.e. if e (F) | e (G) and each vertex degree of G can be expressed as a linear combination of the vertex degrees of F.) The F -decomposition threshold δ F is the smallest value ensuring that an F -divisible graph G on n vertices with δ (G) ≥ (δ F + o (1)) n has an F -decomposition. Our main results imply the following for a given graph F , where δ F ⁎ is the fractional version of δ F and χ : = χ (F) : (i) δ F ≤ max ⁡ { δ F ⁎ , 1 − 1 / (χ + 1) } ; (ii) if χ ≥ 5 , then δ F ∈ { δ F ⁎ , 1 − 1 / χ , 1 − 1 / (χ + 1) } ; (iii) we determine δ F if F is bipartite. In particular, (i) implies that δ K r = δ K r ⁎. Our proof involves further developments of the recent 'iterative' absorbing approach. [ABSTRACT FROM AUTHOR]

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let 0 < p < 1 be constant and let G ∼ G n , p . Let odd ( G ) be the number of odd degree vertices in G . Then a.a.s. the following hold: (i) G can be decomposed into ⌊ Δ ( G ) / 2 ⌋ cycles and a matching of size odd ( G ) / 2 . (ii) G can be decomposed into max ⁡ { odd ( G ) / 2 , ⌈ Δ ( G ) / 2 ⌉ } paths. (iii) G can be decomposed into ⌈ Δ ( G ) / 2 ⌉ linear forests. Each of these bounds is best possible. We actually derive (i)–(iii) from ‘quasirandom’ versions of our results. In that context, we also determine the edge chromatic number of a given dense quasirandom graph of even order. For all these results, our main tool is a result on Hamilton decompositions of robust expanders by Kühn and Osthus. [ABSTRACT FROM AUTHOR]