BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that any quasirandom graph with n vertices and rn edges can be decomposed into n copies of any fixed tree with r edges. The case of decomposing a complete graph establishes a conjecture of Ringel from 1963.
What is the minimum number of triangles in a graph of given order and size? Motivated by earlier results of Mantel and Turán, Rademacher solved the first non-trivial case of this problem in 1941. The problem was revived by Erdős in 1955; it is now known as the Erdős-Rademacher problem. After attracting much attention, it was solved asymptotically in a major breakthrough by Razborov in 2008. In this paper, we provide an exact solution for all large graphs whose edge density is bounded away from~1, which in this range confirms a conjecture of Lovász and Simonovits from 1975. Furthermore, we give a description of the extremal graphs.
We prove that any quasirandom dense large graph in which all degrees are equal and even can be decomposed into any given collection of two-factors (2-regular spanning subgraphs). A special case of this result gives a new solution to the Oberwolfach problem.
Given a graph F, let st(F) be the number of subdivisions of F, each with a different vertex set, which one can guarantee in a graph G in which every edge lies in at least t copies of F. In 1990, Tuza asked for which graphs F and large t, one has that st(F) is exponential in a power of t. We show that, somewhat surprisingly, the only such F are complete graphs, and for every F which is not complete, st(F) is polynomial in t. Further, for a natural strengthening of the local condition above, we also characterise those F for which st(F) is exponential in a power of t.
A famous conjecture of Pósa from 1962 asserts that every graph on n vertices and with minimum degree at least 2n/3 contains the square of a Hamilton cycle. The conjecture was proven for large graphs in 1996 by Komlós, Sárközy and Szemerédi. In this paper we prove a degree sequence version of Pósa's conjecture: Given any η>0, every graph G of sufficiently large order n contains the square of a Hamilton cycle if its degree sequence d1≤⋯≤dn satisfies di≥(1/3+η)n+i for all i≤n/3. The degree sequence condition here is asymptotically best possible. Our approach uses a hybrid of the Regularity-Blow-up method and the Connecting-Absorbing method.
We prove that, for large n, every 3-connected D-regular graph on n vertices with D≥n/4 is Hamiltonian. This is best possible and confirms a conjecture posed independently by Bollobás and Häggkvist in the 1970s. The proof builds on a structural decomposition result proved recently by the same authors.
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' outneighbourhood of S is a little larger than S. This generalises a result of Kühn, Osthus and Treglown on approximate Hamilton decompositions of dense regular oriented graphs. It also generalises 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.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.