Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtremal problems of ErdH{o}s, Faudree, Schelp and Simonovits on paths and cycles
86
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For positive integers $n>dgeq k$, let $phi(n,d,k)$ denote the least integer $phi$ such that every $n$-vertex graph with at least $phi$ vertices of degree at least $d$ contains a path on $k+1$ vertices. Many years ago, ErdH{o}s, Faudree, Schelp and Simonovits proposed the study of the function $phi(n,d,k)$, and conjectured that for any positive integers $n>dgeq k$, it holds that $phi(n,d,k)leq lfloorfrac{k-1}{2}rfloorlfloorfrac{n}{d+1}rfloor+epsilon$, where $epsilon=1$ if $k$ is odd and $epsilon=2$ otherwise. In this paper we determine the value of the function $phi(n,d,k)$ exactly. This confirms the above conjecture of ErdH{o}s et al. for all positive integers $k eq 4$ and in a corrected form for the case $k=4$. Our proof utilizes, among others, a lemma of ErdH{o}s et al., a theorem of Jackson, and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin, where the latter two results concern maximum cycles in bipartite graphs. Besides, we construct examples to provide answers to two closely related questions raised by ErdH{o}s et al.
rate research
Read More
A chordless cycle, or equivalently a hole, in a graph $G$ is an induced subgraph of $G$ which is a cycle of length at least $4$. We prove that the ErdH{o}s-Posa property holds for chordless cycles, which resolves the major open question concerning the ErdH{o}s-Posa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either $k+1$ vertex-disjoint chordless cycles, or $c_1k^2 log k+c_2$ vertices hitting every chordless cycle for some constants $c_1$ and $c_2$. It immediately implies an approximation algorithm of factor $mathcal{O}(sf{opt}log {sf opt})$ for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least $ell$ for any fixed $ellge 5$ do not have the ErdH{o}s-Posa property.
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.
We prove that there exists a function $f:mathbb{N}rightarrow mathbb{R}$ such that every digraph $G$ contains either $k$ directed odd cycles where every vertex of $G$ is contained in at most two of them, or a vertex set $X$ of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral ErdH{o}s-Posa property of undirected odd cycles, proved by Reed [Mangoes and blueberries. Combinatorica 1999], to digraphs.
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.
Extending the concept of Ramsey numbers, Erd{H o}s and Rogers introduced the following function. For given integers $2le s<t$ let $$ f_{s,t}(n)=min {max {|W| : Wsubseteq V(G) {and} G[W] {contains no} K_s} }, $$ where the minimum is taken over all $K_t$-free graphs $G$ of order $n$. In this paper, we show that for every $sge 3$ there exist constants $c_1=c_1(s)$ and $c_2=c_2(s)$ such that $f_{s,s+1}(n) le c_1 (log n)^{c_2} sqrt{n}$. This result is best possible up to a polylogarithmic factor. We also show for all $t-2 geq s geq 4$, there exists a constant $c_3$ such that $f_{s,t}(n) le c_3 sqrt{n}$. In doing so, we partially answer a question of ErdH{o}s by showing that $lim_{nto infty} frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=infty$ for any $sge 4$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
