Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLower bounds on the ErdH{o}s-Gyarfas problem via color energy graphs
58
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given positive integers $p$ and $q$, a $(p,q)$-coloring of the complete graph $K_n$ is an edge-coloring in which every $p$-clique receives at least $q$ colors. ErdH{o}s and Shelah posed the question of determining $f(n,p,q)$, the minimum number of colors needed for a $(p,q)$-coloring of $K_n$. In this paper, we expand on the color energy technique introduced by Pohoata and Sheffer to prove new lower bounds on this function, making explicit the connection between bounds on extremal numbers and $f(n,p,q)$. Using results on the extremal numbers of subdivided complete graphs, theta graphs, and subdivided complete bipartite graphs, we generalize results of Fish, Pohoata, and Sheffer, giving the first nontrivial lower bounds on $f(n,p,q)$ for some pairs $(p,q)$ and improving previous lower bounds for other pairs.
rate research
Read More
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.
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.
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.
In 1935, ErdH{o}s and Szekeres proved that $(m-1)(k-1)+1$ is the minimum number of points in the plane which definitely contain an increasing subset of $m$ points or a decreasing subset of $k$ points (as ordered by their $x$-coordinates). We consider their result from an on-line game perspective: Let points be determined one by one by player A first determining the $x$-coordinate and then player B determining the $y$-coordinate. What is the minimum number of points such that player A can force an increasing subset of $m$ points or a decreasing subset of $k$ points? We introduce this as the ErdH{o}s-Szekeres on-line number and denote it by $text{ESO}(m,k)$. We observe that $text{ESO}(m,k) < (m-1)(k-1)+1$ for $m,k ge 3$, provide a general lower bound for $text{ESO}(m,k)$, and determine $text{ESO}(m,3)$ up to an additive constant.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
