Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the minimum degree of minimal Ramsey graphs for cliques versus cycles
99
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is said to be $q$-Ramsey for a $q$-tuple of graphs $(H_1,ldots,H_q)$, denoted by $Gto_q(H_1,ldots,H_q)$, if every $q$-edge-coloring of $G$ contains a monochromatic copy of $H_i$ in color $i,$ for some $iin[q]$. Let $s_q(H_1,ldots,H_q)$ denote the smallest minimum degree of $G$ over all graphs $G$ that are minimal $q$-Ramsey for $(H_1,ldots,H_q)$ (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, ErdH{o}s and Lovasz, who determined its value precisely for a pair of cliques. Over the past two decades the parameter $s_q$ has been studied by several groups of authors, the main focus being on the symmetric case, where $H_icong H$ for all $iin [q]$. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles and trees. We determine $s_2(H_1,H_2)$ when $(H_1,H_2)$ is a pair of one clique and one tree, a pair of one clique and one cycle, and when it is a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on $s_q(C_ell,ldots,C_ell,K_t,ldots,K_t)$ in terms of the size of the cliques $t$, the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.
rate research
Read More
We prove that $s_r(K_k) = O(k^5 r^{5/2})$, where $s_r(K_k)$ is the Ramsey parameter introduced by Burr, ErdH{o}s and Lov{a}sz in 1976, which is defined as the smallest minimum degree of a graph $G$ such that any $r$-colouring of the edges of $G$ contains a monochromatic $K_k$, whereas no proper subgraph of $G$ has this property. The construction used in our proof relies on a group theoretic model of generalised quadrangles introduced by Kantor in 1980.
If $G$ is a graph and $vec H$ is an oriented graph, we write $Gto vec H$ to say that every orientation of the edges of $G$ contains $vec H$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the threshold $p_{vec H}=p_{vec H}(n)$ for the property $G(n,p)to vec H$ for the cases in which $vec H$ is an acyclic orientation of a complete graph or of a cycle.
Given any graph $H$, a graph $G$ is said to be $q$-Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$. Further, such a graph $G$ is said to be minimal $q$-Ramsey for $H$ if additionally no proper subgraph $G$ of $G$ is $q$-Ramsey for $H$. In 1976, Burr, ErdH{o}s, and Lovasz initiated the study of the parameter $s_q(H)$, defined as the smallest minimum degree among all minimal $q$-Ramsey graphs for $H$. In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$-Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$-abundant. Among other results, we prove that every cycle is $s_q$-abundant for any integer $qgeq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.
We study graphs with the property that every edge-colouring admits a monochromatic cycle (the length of which may depend freely on the colouring) and describe those graphs that are minimal with this property. We show that every member in this class reduces recursively to one of the base graphs $K_5-e$ or $K_4vee K_4$ (two copies of $K_4$ identified at an edge), which implies that an arbitrary $n$-vertex graph with $e(G)geq 2n-1$ must contain one of those as a minor. We also describe three explicit constructions governing the reverse process. As an application we are able to establish Ramsey infiniteness for each of the three possible chromatic subclasses $chi=2, 3, 4$, the unboundedness of maximum degree within the class as well as Ramsey separability of the family of cycles of length $leq l$ from any of its proper subfamilies.
Given graphs $H_1, dots, H_t$, a graph $G$ is $(H_1, dots, H_t)$-Ramsey-minimal if every $t$-coloring of the edges of $G$ contains a monochromatic $H_i$ in color $i$ for some $iin{1, dots, t}$, but any proper subgraph of $G $ does not possess this property. We define $mathcal{R}_{min}(H_1, dots, H_t)$ to be the family of $(H_1, dots, H_t)$-Ramsey-minimal graphs. A graph $G$ is dfn{$mathcal{R}_{min}(H_1, dots, H_t)$-saturated} if no element of $mathcal{R}_{min}(H_1, dots, H_t)$ is a subgraph of $G$, but for any edge $e$ in $overline{G}$, some element of $mathcal{R}_{min}(H_1, dots, H_t)$ is a subgraph of $G + e$. We define $sat(n, mathcal{R}_{min}(H_1, dots, H_t))$ to be the minimum number of edges over all $mathcal{R}_{min}(H_1, dots, H_t)$-saturated graphs on $n$ vertices. In 1987, Hanson and Toft conjectured that $sat(n, mathcal{R}_{min}(K_{k_1}, dots, K_{k_t}) )= (r - 2)(n - r + 2)+binom{r - 2}{2} $ for $n ge r$, where $r=r(K_{k_1}, dots, K_{k_t})$ is the classical Ramsey number for complete graphs. The first non-trivial case of Hanson and Tofts conjecture for sufficiently large $n$ was setteled in 2011, and is so far the only settled case. Motivated by Hanson and Tofts conjecture, we study the minimum number of edges over all $mathcal{R}_{min}(K_3, mathcal{T}_k)$-saturated graphs on $n$ vertices, where $mathcal{T}_k$ is the family of all trees on $k$ vertices. We show that for $n ge 18$, $sat(n, mathcal{R}_{min}(K_3, mathcal{T}_4)) =lfloor {5n}/{2}rfloor$. For $k ge 5$ and $n ge 2k + (lceil k/2 rceil +1) lceil k/2 rceil -2$, we obtain an asymptotic bound for $sat(n, mathcal{R}_{min}(K_3, mathcal{T}_k))$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
