Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn a colored Turan problem of Diwan and Mubayi
61
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Suppose that $R$ (red) and $B$ (blue) are two graphs on the same vertex set of size $n$, and $H$ is some graph with a red-blue coloring of its edges. How large can $R$ and $B$ be if $Rcup B$ does not contain a copy of $H$? Call the largest such integer $mathrm{mex}(n, H)$. This problem was introduced by Diwan and Mubayi, who conjectured that (except for a few specific exceptions) when $H$ is a complete graph on $k+1$ vertices with any coloring of its edges $mathrm{mex}(n,H)=mathrm{ex}(n, K_{k+1})$. This conjecture generalizes Turans theorem. Diwan and Mubayi also asked for an analogue of ErdH{o}s-Stone-Simonovits theorem in this context. We prove the following asymptotic characterization of the extremal threshold in terms of the chromatic number $chi(H)$ and the textit{reduced maximum matching number} $mathcal{M}(H)$ of $H$. $$mathrm{mex}(n, H)=left(1- frac{1}{2(chi(H)-1)} - Omegaleft(frac{mathcal{M}(H)}{chi(H)^2}right)right)frac{n^2}{2}.$$ $mathcal{M}(H)$ is, among the set of proper $chi(H)$-colorings of $H$, the largest set of disjoint pairs of color classes where each pair is connected by edges of just a single color. The result is also proved for more than $2$ colors and is tight up to the implied constant factor. We also study $mathrm{mex}(n, H)$ when $H$ is a cycle with a red-blue coloring of its edges, and we show that $mathrm{mex}(n, H)lesssim frac{1}{2}binom{n}{2}$, which is tight.
rate research
Read More
Classical questions in extremal graph theory concern the asymptotics of $operatorname{ex}(G, mathcal{H})$ where $mathcal{H}$ is a fixed family of graphs and $G=G_n$ is taken from a `standard increasing sequence of host graphs $(G_1, G_2, dots)$, most often $K_n$ or $K_{n,n}$. Inverting the question, we can instead ask how large $e(G)$ can be with respect to $operatorname{ex}(G,mathcal{H})$. We show that the standard sequences indeed maximize $e(G)$ for some choices of $mathcal{H}$, but not for others. Many interesting questions and previous results arise very naturally in this context, which also, unusually, gives rise to sensible extremal questions concerning multigraphs and non-uniform hypergraphs.
Let $t$ be an integer such that $tgeq 2$. Let $K_{2,t}^{(3)}$ denote the triple system consisting of the $2t$ triples ${a,x_i,y_i}$, ${b,x_i,y_i}$ for $1 le i le t$, where the elements $a, b, x_1, x_2, ldots, x_t,$ $y_1, y_2, ldots, y_t$ are all distinct. Let $ex(n,K_{2,t}^{(3)})$ denote the maximum size of a triple system on $n$ elements that does not contain $K_{2,t}^{(3)}$. This function was studied by Mubayi and Verstraete, where the special case $t=2$ was a problem of ErdH{o}s that was studied by various authors. Mubayi and Verstraete proved that $ex(n,K_{2,t}^{(3)})<t^4binom{n}{2}$ and that for infinitely many $n$, $ex(n,K_{2,t}^{(3)})geq frac{2t-1}{3} binom{n}{2}$. These bounds together with a standard argument show that $g(t):=lim_{nto infty} ex(n,K_{2,t}^{(3)})/binom{n}{2}$ exists and that [frac{2t-1}{3}leq g(t)leq t^4.] Addressing the question of Mubayi and Verstraete on the growth rate of $g(t)$, we prove that as $t to infty$, [g(t) = Theta(t^{1+o(1)}).]
Let $F$ be a fixed graph. The rainbow Turan number of $F$ is defined as the maximum number of edges in a graph on $n$ vertices that has a proper edge-coloring with no rainbow copy of $F$ (where a rainbow copy of $F$ means a copy of $F$ all of whose edges have different colours). The systematic study of such problems was initiated by Keevash, Mubayi, Sudakov and Verstraete. In this paper, we show that the rainbow Turan number of a path with $k+1$ edges is less than $left(frac{9k}{7}+2right) n$, improving an earlier estimate of Johnston, Palmer and Sarkar.
The Turan number of a graph $H$, $text{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices which does not have $H$ as a subgraph. A wheel $W_n$ is an $n$-vertex graph formed by connecting a single vertex to all vertices of a cycle $C_{n-1}$. Let $mW_{2k+1}$ denote the $m$ vertex-disjoint copies of $W_{2k+1}$. For sufficiently large $n$, we determine the Turan number and all extremal graphs for $mW_{2k+1}$. We also provide the Turan number and all extremal graphs for $W^{h}:=bigcuplimits^m_{i=1}W_{k_i}$ when $n$ is sufficiently large, where the number of even wheels is $h$ and $h>0$.
The extremal number $mathrm{ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r in [1,2]$ is realisable if there exists a graph $F$ with $mathrm{ex}(n , F) = Theta(n^r)$. Several decades ago, ErdH{o}s and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $0,1, frac{7}{5}, 2$, and the numbers of the form $1+frac{1}{m}$, $2-frac{1}{m}$, $2-frac{2}{m}$ for integers $m geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$. In this paper, we make progress on the conjecture of ErdH{o}s and Simonovits. First, we show that $2 - frac{a}{b}$ is realisable for any integers $a,b geq 1$ with $b>a$ and $b equiv pm 1 ~({rm mod}:a)$. This includes all previously known ones, and gives infinitely many limit points $2-frac{1}{m}$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
