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]

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]

We present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $\hat{R}_{\mathrm{ind}}(P_n)\leq 5 \cdot 10^7n$ , thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and Łuczak. We also provide a bound for the k-colour version, showing that $\hat{R}_{\mathrm{ind}}^k(P_n)=O(k^3\log^4k)n$. Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,\frac{1+\varepsilon}{n})$ , contains typically an induced path of length $\Theta(\varepsilon^2) n$. [ABSTRACT FROM AUTHOR]

Motivated by longstanding conjectures regarding decompositions of graphs into paths and cycles, we prove the following optimal decomposition results for random graphs. Let 0 < p < 1 be constant and let G ∼ G n , p . Let odd ( G ) be the number of odd degree vertices in G . Then a.a.s. the following hold: (i) G can be decomposed into ⌊ Δ ( G ) / 2 ⌋ cycles and a matching of size odd ( G ) / 2 . (ii) G can be decomposed into max ⁡ { odd ( G ) / 2 , ⌈ Δ ( G ) / 2 ⌉ } paths. (iii) G can be decomposed into ⌈ Δ ( G ) / 2 ⌉ linear forests. Each of these bounds is best possible. We actually derive (i)–(iii) from ‘quasirandom’ versions of our results. In that context, we also determine the edge chromatic number of a given dense quasirandom graph of even order. For all these results, our main tool is a result on Hamilton decompositions of robust expanders by Kühn and Osthus. [ABSTRACT FROM AUTHOR]