Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Strengthening of ErdH{o}s-Gallai Theorem and Proof of Woodalls Conjecture
80
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For a 2-connected graph $G$ on $n$ vertices and two vertices $x,yin V(G)$, we prove that there is an $(x,y)$-path of length at least $k$ if there are at least $frac{n-1}{2}$ vertices in $V(G)backslash {x,y}$ of degree at least $k$. This strengthens a well-known theorem due to ErdH{o}s and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with $n$ vertices contains a cycle of length at least $2k$ if it has at least $frac{n}{2}+k$ vertices of degree at least $k$. This confirms a 1975 conjecture made by Woodall. As another applications, we obtain some results which generalize previous theorems of Dirac, ErdH{o}s-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Koml{o}s-S{o}s Conjecture which was verified by Bazgan et al. and of a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond.
rate research
Read More
The ErdH{o}s-Faber-Lov{a}sz conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on $n$ vertices is at most $n$. In this paper, we prove this conjecture for every large $n$. We also provide stabili
Generalized Turan problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants.
For fixed $p$ and $q$, an edge-coloring of the complete graph $K_n$ is said to be a $(p, q)$-coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n, p, q)$ is the minimum number of colors needed for $K_n$ to have a $(p, q)$-coloring. This function was introduced about 45 years ago, but was studied systematically by ErdH{o}s and Gy{a}rf{a}s in 1997, and is now known as the ErdH{o}s-Gy{a}rf{a}s function. In this paper, we study $f(n, p, q)$ with respect to Gallai-colorings, where a Gallai-coloring is an edge-coloring of $K_n$ without rainbow triangles. Combining the two concepts, we consider the function $g(n, p, q)$ that is the minimum number of colors needed for a Gallai-$(p, q)$-coloring of $K_n$. Using the anti-Ramsey number for $K_3$, we have that $g(n, p, q)$ is nontrivial only for $2leq qleq p-1$. We give a general lower bound for this function and we study how this function falls off from being equal to $n-1$ when $q=p-1$ and $pgeq 4$ to being $Theta(log n)$ when $q = 2$. In particular, for appropriate $p$ and $n$, we prove that $g=n-c$ when $q=p-c$ and $cin {1,2}$, $g$ is at most a fractional power of $n$ when $q=lfloorsqrt{p-1}rfloor$, and $g$ is logarithmic in $n$ when $2leq qleq lfloorlog_2 (p-1)rfloor+1$.
An $r$-uniform hypergraph ($r$-graph for short) is called linear if every pair of vertices belong to at most one edge. A linear $r$-graph is complete if every pair of vertices are in exactly one edge. The famous Brown-ErdH{o}s-Sos conjecture states that for every fixed $k$ and $r$, every linear $r$-graph with $Omega(n^2)$ edges contains $k$ edges spanned by at most $(r-2)k+3$ vertices. As an intermediate step towards this conjecture, Conlon and Nenadov recently suggested to prove its natural Ramsey relaxation. Namely, that for every fixed $k$, $r$ and $c$, in every $c$-colouring of a complete linear $r$-graph, one can find $k$ monochromatic edges spanned by at most $(r-2)k+3$ vertices. We prove that this Ramsey version of the conjecture holds under the additional assumption that $r geq r_0(c)$, and we show that for $c=2$ it holds for all $rgeq 4$.
We provide a cyclic permutation analogue of the ErdH os-Szekeres theorem. In particular, we show that every cyclic permutation of length $(k-1)(ell-1)+2$ has either an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $ell+1$, and show that the result is tight. We also characterize all maximum-length cyclic permutations that do not have an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $ell+1$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
