Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRamsey numbers for bipartite graphs with small bandwidth
212
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.
rate research
Read More
We estimate the $3$-colour bipartite Ramsey number for balanced bipartite graphs $H$ with small bandwidth and bounded maximum degree. More precisely, we show that the minimum value of $N$ such that in any $3$-edge colouring of $K_{N,N}$ there is a monochromatic copy of $H$ is at most $big(3/2+o(1)big)|V(H)|$. In particular, we determine asymptotically the $3$-colour bipartite Ramsey number for balanced grid graphs.
In this paper, we consider a variant of Ramsey numbers which we call complementary Ramsey numbers $bar{R}(m,t,s)$. We first establish their connections to pairs of Ramsey $(s,t)$-graphs. Using the classification of Ramsey $(s,t)$-graphs for small $s,t$, we determine the complementary Ramsey numbers $bar{R}(m,t,s)$ for $(s,t)=(4,4)$ and $(3,6)$.
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))$.
Given two graphs $G$ and $H$, the $k$-colored Gallai-Ramsey number $gr_k(G : H)$ is defined to be the minimum integer $n$ such that every $k$-coloring of the complete graph on $n$ vertices contains either a rainbow copy of $G$ or a monochromatic copy of $H$. In this paper, we consider $gr_k(K_3 : H)$ where $H$ is a connected graph with five vertices and at most six edges. There are in total thirteen graphs in this graph class, and the Gallai-Ramsey numbers for some of them have been studied step by step in several papers. We determine all the Gallai-Ramsey numbers for the remaining graphs, and we also obtain some related results for a class of unicyclic graphs.
Let $mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
