Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn generalized Ramsey numbers of ErdH{o}s and Rogers
229
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
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.
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.
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$.
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.
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
