Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStability for the ErdH{o}s-Rothschild problem
77
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a sequence $mathbf{k} := (k_1,ldots,k_s)$ of natural numbers and a graph $G$, let $F(G;mathbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;mathbf{k})$ to denote the maximum of $F(G;mathbf{k})$ over all graphs $G$ on $n$ vertices. This problem was first considered by ErdH{o}s and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. In previous work with Yilma, we constructed a finite optimisation problem whose maximum is equal to the limit of $log_2 F(n;mathbf{k})/{nchoose 2}$ as $n$ tends to infinity and proved a stability theorem for complete multipartite graphs $G$. In this paper we provide a sufficient condition on $mathbf{k}$ which guarantees a general stability theorem for any graph $G$, describing the asymptotic structure of $G$ on $n$ vertices with $F(G;mathbf{k}) = F(n;mathbf{k}) cdot 2^{o(n^2)}$ in terms of solutions to the optimisation problem. We apply our theorem to systematically recover existing stability results as well as all cases with $s=2$. The proof uses a novel version of symmetrisation on edge-coloured weighted multigraphs.
rate research
Read More
Let $textbf{k} := (k_1,ldots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;textbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;textbf{k})$ to denote the maximum of $F(G;textbf{k})$ over all graphs $G$ on $n$ vertices. There are currently very few known exact (or asymptotic) results known for this problem, posed by ErdH{o}s and Rothschild in 1974. We prove some new exact results for $n to infty$: (i) A sufficient condition on $textbf{k}$ which guarantees that every extremal graph is a complete multipartite graph, which systematically recovers all existing exact results. (ii) Addressing the original question of ErdH{o}s and Rothschild, in the case $textbf{k}=(3,ldots,3)$ of length $7$, the unique extremal graph is the complete balanced $8$-partite graph, with colourings coming from Hadamard matrices of order $8$. (iii) In the case $textbf{k}=(k+1,k)$, for which the sufficient condition in (i) does not hold, for $3 leq k leq 10$, the unique extremal graph is complete $k$-partite with one part of size less than $k$ and the other parts as equal in size as possible.
Let $mathbf{k} := (k_1,dots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;mathbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;mathbf{k})$ to denote the maximum of $F(G;mathbf{k})$ over all graphs $G$ on $n$ vertices. This problem was first considered by ErdH{o}s and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. We prove that, for every $mathbf{k}$ and $n$, there is a complete multipartite graph $G$ on $n$ vertices with $F(G;mathbf{k}) = F(n;mathbf{k})$. Also, for every $mathbf{k}$ we construct a finite optimisation problem whose maximum is equal to the limit of $log_2 F(n;mathbf{k})/{nchoose 2}$ as $n$ tends to infinity. Our final result is a stability theorem for complete multipartite graphs $G$, describing the asymptotic structure of such $G$ with $F(G;mathbf{k}) = F(n;mathbf{k}) cdot 2^{o(n^2)}$ in terms of solutions to the optimisation problem.
The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers $s,t$ and an $n$-vertex graph $G$ with $lfloor n^2/4 rfloor +t$ edges and triangle covering number $s$, we determine (for large $n$) sharp bounds on the minimum number of triangles in $G$ and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, ErdH os, and Lovasz-Simonovits whose results apply only to $s le t$. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture.
In 1981, ErdH{o}s and Hajnal asked whether the sum of the reciprocals of the odd cycle lengths in a graph with infinite chromatic number is necessarily infinite. Let $mathcal{C}(G)$ be the set of cycle lengths in a graph $G$ and let $mathcal{C}_text{odd}(G)$ be the set of odd numbers in $mathcal{C}(G)$. We prove that, if $G$ has chromatic number $k$, then $sum_{ellin mathcal{C}_text{odd}(G)}1/ellgeq (1/2-o_k(1))log k$. This solves ErdH{o}s and Hajnals odd cycle problem, and, furthermore, this bound is asymptotically optimal. In 1984, ErdH{o}s asked whether there is some $d$ such that each graph with chromatic number at least $d$ (or perhaps even only average degree at least $d$) has a cycle whose length is a power of 2. We show that an average degree condition is sufficient for this problem, solving it with methods that apply to a wide range of sequences in addition to the powers of 2. Finally, we use our methods to show that, for every $k$, there is some $d$ so that every graph with average degree at least $d$ has a subdivision of the complete graph $K_k$ in which each edge is subdivided the same number of times. This confirms a conjecture of Thomassen from 1984.
Robertson and Seymour proved that the family of all graphs containing a fixed graph $H$ as a minor has the ErdH{o}s-Posa property if and only if $H$ is planar. We show that this is no longer true for the edge version of the ErdH{o}s-Posa property, and indeed even fails when $H$ is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
