A generalization of Turán's theorem
We prove a generalization of Turán's theorem proposed by Balogh and Lidický.
Source author record
Domagoj Bradač
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
5works
1topics
4close collaborators
Published work
5 publications
preprint2022arXiv
Asymptotics of the hypergraph bipartite Turán problem
For positive integers s,t,r, let Ks,t(r) denote the r-uniform hypergraph whose vertex set is the union of pairwise disjoint sets X,Y1,…,Yt, where ∣X∣=s and ∣Y1∣=⋯=∣Yt∣=r−1, and whose edge set is {{x}∪Yi:x∈X,1≤i≤t}. The study of the Turán function of Ks,t(r) received considerable interest in recent years. Our main results are as follows. First, we show that \begin{equation} \mathrm{ex}(n,K_{s,t}^{(r)}) = O_{s,r}(t^{\frac{1}{s-1}}n^{r - \frac{1}{s-1}}) \end{equation} for all s,t≥2 and r≥3, improving the power of n in the previously best bound and resolving a question of Mubayi and Verstraëte about the dependence of ex(n,K2,t(3)) on t. Second, we show that this upper bound is tight when r is even and t≫s. This disproves a conjecture of Xu, Zhang and Ge. Third, we show that the above upper bound is not tight for r=3, namely that ex(n,Ks,t(3))=Os,t(n3−s−11−εs) (for all s≥3). This indicates that the behaviour of ex(n,Ks,t(r)) might depend on the parity of r. Lastly, we prove a conjecture of Ergemlidze, Jiang and Methuku on the hypergraph analogue of the bipartite Turán problem for graphs with bounded degrees on one side. Our tools include a novel twist on the dependent random choice method as well as a variant of the celebrated norm graphs constructed by Kollár, Rónyai and Szabó.
Open access
preprint2022arXiv
Covering random graphs with monochromatic trees
Given an r-edge-coloured complete graph Kn, how many monochromatic connected components does one need in order to cover its vertex set? This natural question is a well-known essentially equivalent formulation of the classical Ryser's conjecture which, despite a lot of attention over the last 50 years, still remains open. A number of recent papers consider a sparse random analogue of this question, asking for the minimum number of monochromatic components needed to cover the vertex set of an r-edge-coloured random graph G(n,p). Recently, Bucić, Korándi and Sudakov established a connection between this problem and a certain Helly-type local to global question for hypergraphs raised about 30 years ago by Erdős, Hajnal and Tuza. We identify a modified version of the hypergraph problem which controls the answer to the problem of covering random graphs with monochromatic components more precisely. To showcase the power of our approach, we essentially resolve the 3-colour case by showing that (logn/n)1/4 is a threshold at which point three monochromatic components are needed to cover all vertices of a 3-edge-coloured random graph, answering a question posed by Kohayakawa, Mendonça, Mota and Schülke. Our approach also allows us to determine the answer in the general r-edge coloured instance of the problem, up to lower order terms, around the point when it first becomes bounded, answering a question of Bucić, Korándi and Sudakov.
Open access
preprint2022arXiv
Powers of Hamilton cycles of high discrepancy are unavoidable
The Pósa-Seymour conjecture asserts that every graph on n vertices with minimum degree at least (1−1/(r+1))n contains the rth power of a Hamilton cycle. Komlós, Sárközy and Szemerédi famously proved the conjecture for large n. The notion of discrepancy appears in many areas of mathematics, including graph theory. In this setting, a graph G is given along with a 2-coloring of its edges. One is then asked to find in G a copy of a given subgraph with a large discrepancy, i.e., with significantly more than half of its edges in one color. For r≥2, we determine the minimum degree threshold needed to find the rth power of a Hamilton cycle of large discrepancy, answering a question posed by Balogh, Csaba, Pluhár and Treglown. Notably, for r≥3, this threshold approximately matches the minimum degree requirement of the Pósa-Seymour conjecture.
Open access
preprint2022arXiv
The Turán number of the grid
For a positive integer t, let Ft denote the graph of the t×t grid. Motivated by a 50-year-old conjecture of Erdős about Turán numbers of r-degenerate graphs, we prove that there exists a constant C=C(t) such that ex(n,Ft)≤Cn3/2. This bound is tight up to the value of C. One of the interesting ingredients of our proof is a novel way of using the tensor power trick.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.