Search

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]

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]

We show that a quasirandom k-uniform hypergraph G has a tight Euler tour subject to the necessary condition that k divides all vertex degrees. The case when G is complete confirms a conjecture of Chung, Diaconis and Graham from 1989 on the existence of universal cycles for the k-subsets of an n-set. [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]

A famous theorem of Kirkman says that there exists a Steiner triple system of order n if and only if n ≡ 1,3 mod 6. In 1973, Erdős conjectured that one can find so-called 'sparse' Steiner triple systems. Roughly speaking, the aim is to have at most j−3 triples on every set of j points, which would be best possible. (Triple systems with this sparseness property are also referred to as having high girth.) We prove this conjecture asymptotically by analysing a natural generalization of the triangle removal process. Our result also solves a problem posed by Lefmann, Phelps and Rödl as well as Ellis and Linial in a strong form, and answers a question of Krivelevich, Kwan, Loh and Sudakov. Moreover, we pose a conjecture which would generalize the Erdős conjecture to Steiner systems with arbitrary parameters and provide some evidence for this. [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]