For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1     

Loose Hamilton cycles in hypergraphs

We prove that any k-uniform hypergraph on n vertices with minimum degree at least contains a loose Hamilton cycle. The proof strategy is similar to that used by Kühn and Osthus for the 3-uniform case. Though some additional difficulties arise in the k-uniform case, our argument here is considerably simplified by applying the recent hypergraph blow-up lemma of Keevash.     

Hamilton ?-cycles in uniform hypergraphs

We say that a k-uniform hypergraph C is an ?-cycle if there exists a cyclic ordering of the vertices of C such that every edge of C consists of k consecutive vertices and such that every pair of consecutive edges (in the natural ordering of the edges) intersects in precisely ? vertices. We prove that if 1??<k and k−? does not divide k then any k-uniform hypergraph on n vertices with minimum degree at least contains a Hamilton ?-cycle. This confirms a conjecture of Hàn and Schacht. Together with results of Rödl, Ruciński and Szemerédi, our result asymptotically determines the minimum degree which forces an ?-cycle for any ? with 1??<k.     

Hamilton decompositions of regular expanders: A proof of Kelly’s conjecture for large tournaments

A long-standing conjecture of Kelly states that every regular tournament on n$n$ vertices can be decomposed into (n−1)/2$(n-1)/2$ edge-disjoint Hamilton cycles. We prove this conjecture for large n$n$. In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs. We show that every sufficiently large regular digraph G$G$ on n$n$ vertices whose degree is linear in n$n$ and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erd?s on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of Nash-Williams. We also apply our result to solve a problem on the domination ratio of the Asymmetric Travelling Salesman problem, which was raised e.g. by Glover and Punnen as well as Alon, Gutin and Krivelevich.     

A note on complete subdivisions in digraphs of large outdegree

Mader conjectured that for all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order . In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let be a digraph of order n whose minimum outdegree is at least d. Then contains a subdivision of a complete digraph of order . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008     

Random maximal H‐free graphs*

Given a graph H, a random maximal H‐free graph is constructed by the following random greedy process. First assign to each edge of the complete graph on n vertices a birthtime which is uniformly distributed in [0, 1]. At time p=0 start with the empty graph and increase p gradually. Each time a new edge is born, it is included in the graph if this does not create a copy of H. The question is then how many edges such a graph will have when p=1. Here we give asymptotically almost sure bounds on the number of edges if H is a strictly 2‐balanced graph, which includes the case when H is a complete graph or a cycle. Furthermore, we prove the existence of graphs with girth greater than 𝓁 and chromatic number n*y1/(𝓁‐1)+o(1), which improves on previous bounds for 𝓁>3. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 61–82, 2001     

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

Maximum Antichains in Random Subsets of a Finite Set

We consider the random poset (n, p) which is generated by first selecting each subset of [n]={1, …, n} with probability p and then ordering the selected subsets by inclusion. We give asymptotic estimates of the size of the maximum antichain for arbitrary p=p(n). In particular, we prove that if pn/log n→∞, an analogue of Sperner's theorem holds: almost surely the maximum antichain is (to first order) no larger than the antichain which is obtained by selecting all elements of (n, p) with cardinality n/2. This is almost surely not the case if pn=∞.     

Edge‐disjoint Hamilton cycles in random graphs

We show that provided we can with high probability find a collection of edge‐disjoint Hamilton cycles in , plus an additional edge‐disjoint matching of size if is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 397–445, 2015