Search

A celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {H}$ with small maximum codegree has an almost‐perfect matching. We extend this result by obtaining a conflict‐free matching, where conflicts are encoded via a collection C$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {H}$ has a conflict‐free, almost‐perfect matching. This has many applications, one of which yields new asymptotic results for so‐called 'high‐girth' Steiner systems. Our main tool is a random greedy algorithm which we call the 'conflict‐free matching process'. [ABSTRACT FROM AUTHOR]

The MaxCut problem asks for the size mc(G)${\rm mc}(G)$ of a largest cut in a graph G$G$. It is well known that mc(G)⩾m/2${\rm mc}(G)\geqslant m/2$ for any m$m$‐edge graph G$G$, and the difference mc(G)−m/2${\rm mc}(G)-m/2$ is called the surplus of G$G$. The study of the surplus of H$H$‐free graphs was initiated by Erdős and Lovász in the 70s, who, in particular, asked what happens for triangle‐free graphs. This was famously resolved by Alon, who showed that in the triangle‐free case the surplus is Ω(m4/5)$\Omega (m^{4/5})$, and found constructions matching this bound. We prove several new results in this area. (i)Confirming a conjecture of Alon, Krivelevich and Sudakov, we show that for every fixed odd r⩾3$r\geqslant 3$, any Cr$C_r$‐free graph with m$m$ edges has surplus Ωr(mr+1r+2)$\Omega _r(m^{\frac{r+1}{r+2}})$. This is tight, as is shown by a construction of pseudo‐random Cr$C_r$‐free graphs due to Alon and Kahale. It improves previous results of several researchers, and complements a result of Alon, Krivelevich and Sudakov which is the same bound when r$r$ is even.(ii)Generalising the result of Alon, we allow the graph to have triangles, and show that if the number of triangles is a bit less than in a random graph with the same density, then the graph has large surplus. For regular graphs, our bounds on the surplus are sharp.(iii)We prove that an n$n$‐vertex graph with few copies of Kr$K_r$ and average degree d$d$ has surplus Ωr(dr−1/nr−3)$\Omega _r(d^{r-1}/n^{r-3})$, which is tight when d$d$ is close to n$n$ provided that a conjectured dense pseudo‐random Kr$K_r$‐free graph exists. This result is used to improve the best known lower bound (as a function of m$m$) on the surplus of Kr$K_r$‐free graphs.Our proofs combine techniques from semi‐definite programming, probabilistic reasoning, as well as combinatorial and spectral arguments. [ABSTRACT FROM AUTHOR]

We show that for any d=d(n) with d0(ϵ)≤d=o(n), with high probability, the size of a largest induced cycle in the random graph G(n,d/n) is (2±ϵ)ndlogd. This settles a long‐standing open problem in random graph theory. [ABSTRACT FROM AUTHOR]

For a hypergraph H$H$, define its intersection spectrum I(H)$I(H)$ as the set of all intersection sizes |E∩F|$|E\cap F|$ of distinct edges E,F∈E(H)$E,F\in E(H)$. In their seminal paper from 1973 which introduced the local lemma, Erdős and Lovász asked: how large must the intersection spectrum of a k$k$‐uniform 3‐chromatic intersecting hypergraph be? They showed that such a hypergraph must have at least three intersection sizes, and conjectured that the size of the intersection spectrum tends to infinity with k$k$. Despite the problem being reiterated several times over the years by Erdős and other researchers, the lower bound of three intersection sizes has remarkably withstood any improvement until now. In this paper, we prove the Erdős–Lovász conjecture in a strong form by showing that there are at least k1/2−o(1)$k^{1/2-o(1)}$ intersection sizes. Our proof consists of a delicate interplay between Ramsey‐type arguments and a density increment approach. [ABSTRACT FROM AUTHOR]

The iterative absorption method has recently led to major progress in the area of (hyper‐)graph decompositions. Among other results, a new proof of the existence conjecture for combinatorial designs, and some generalizations, was obtained. Here, we illustrate the method by investigating triangle decompositions: We give a simple proof that a triangle‐divisible graph of large minimum degree has a triangle decomposition and prove a similar result for quasi‐random host graphs. [ABSTRACT FROM AUTHOR]

We prove a rainbow version of the blow‐up lemma of Komlós, Sárközy, and Szemerédi for μn‐bounded edge colorings. This enables the systematic study of rainbow embeddings of bounded degree spanning subgraphs. As one application, we show how our blow‐up lemma can be used to transfer the bandwidth theorem of Böttcher, Schacht, and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of μn‐bounded edge colorings. Kim, Kühn, Kupavskii, and Osthus exploit this to prove several rainbow decomposition results. Our proof methods include the strategy of an alternative proof of the blow‐up lemma given by Rödl and Ruciński, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan. [ABSTRACT FROM AUTHOR]

We show that the maximum number of triples on n points, if no three triples span at most five points, is (1±o(1))n2/5. More generally, let f(r)(n;k,s) be the maximum number of edges in an r‐uniform hypergraph on n vertices not containing a subgraph with k vertices and s edges. In 1973, Brown, Erdős and Sós conjectured that the limit limn→∞n−2f(3)(n;k,k−2) exists for all k. They proved this for k=4, where the limit is 1/6 and the extremal examples are Steiner triple systems. We prove the conjecture for k=5 and show that the limit is 1/5. The upper bound is established via a simple optimisation problem. For the lower bound, we use approximate H‐decompositions of Kn for a suitably defined graph H. [ABSTRACT FROM AUTHOR]