Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs
88
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For $ngeq s> rgeq 1$ and $kgeq 2$, write $n rightarrow (s)_{k}^r$ if every hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by textcite{AGLM14} and textcite{EHMR84} we show that [ text{if } r geq 3 text{ and } n rightarrow (s)_k^r text{ then } 2^n rightarrow (s+1)_{k+3}^{r+1}. ] This yields an improvement for some of the known lower bounds on multicolour hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of colouring all $r$-subsets of $V$ such that no hyperedge of size $geq r+1$ is monochromatic. We provide upper and lower bounds on the number of colours necessary in terms of the chromatic number $chi(H)$. In particular we show that this number is $O(log^{(r-1)} (r chi(H)) + r)$.
rate research
Read More
We prove new upper bounds on the multicolour Ramsey numbers of paths and even cycles. It is well known that $(k-1)n+o(n)leq R_k(P_n)leq R_k(C_n)leq kn+o(n)$. The upper bound was recently improved by Sarkozy who showed that $R_k(C_n)leqleft(k-frac{k}{16k^3+1}right)n+o(n)$. Here we show $R_k(C_n) leq (k-frac14)n +o(n)$, obtaining the first improvement to the coefficient of the linear term by an absolute constant.
A set of vertices $Xsubseteq V$ in a simple graph $G(V,E)$ is irredundant if each vertex $xin X$ is either isolated in the induced subgraph $langle Xrangle$ or else has a private neighbor $yin Vsetminus X$ that is adjacent to $x$ and to no other vertex of $X$. The emph{irredundant Ramsey number} $s(m,n)$ is the smallest $N$ such that in every red-blue coloring of the edges of the complete graph of order $N$, either the blue subgraph contains an $m$-element irredundant set or the red subgraph contains an $n$-element irredundant set. The emph{mixed Ramsey number} $t(m,n)$ is the smallest $N$ for which every red-blue coloring of the edges of $K_N$ yields an $m$-element irredundant set in the blue subgraph or an $n$-element independent set in the red subgraph. In this paper, we first improve the upper bound of $t(3,n)$; using this result, we confirm that a conjecture proposed by Chen, Hattingh, and Rousseau, that is, $lim_{nrightarrow infty}frac{t(m,n)}{r(m,n)}=0$ for each fixed $mgeq 3$, is true for $mleq 4$. At last, we prove that $s(3,9)$ and $t(3,9)$ are both equal to $26$.
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)$.
For a fixed set of positive integers $R$, we say $mathcal{H}$ is an $R$-uniform hypergraph, or $R$-graph, if the cardinality of each edge belongs to $R$. An $R$-graph $mathcal{H}$ is emph{covering} if every vertex pair of $mathcal{H}$ is contained in some hyperedge. For a graph $G=(V,E)$, a hypergraph $mathcal{H}$ is called a textit{Berge}-$G$, denoted by $BG$, if there exists an injection $f: E(G) to E(mathcal{H})$ such that for every $e in E(G)$, $e subseteq f(e)$. In this note, we define a new type of Ramsey number, namely the emph{cover Ramsey number}, denoted as $hat{R}^R(BG_1, BG_2)$, as the smallest integer $n_0$ such that for every covering $R$-uniform hypergraph $mathcal{H}$ on $n geq n_0$ vertices and every $2$-edge-coloring (blue and red) of $mathcal{H}$ , there is either a blue Berge-$G_1$ or a red Berge-$G_2$ subhypergraph. We show that for every $kgeq 2$, there exists some $c_k$ such that for any finite graphs $G_1$ and $G_2$, $R(G_1, G_2) leq hat{R}^{[k]}(BG_1, BG_2) leq c_k cdot R(G_1, G_2)^3$. Moreover, we show that for each positive integer $d$ and $k$, there exists a constant $c = c(d,k)$ such that if $G$ is a graph on $n$ vertices with maximum degree at most $d$, then $hat{R}^{[k]}(BG,BG) leq cn$.
Given a positive integer $s$, a graph $G$ is $s$-Ramsey for a graph $H$, denoted $Grightarrow (H)_s$, if every $s$-colouring of the edges of $G$ contains a monochromatic copy of $H$. The $s$-colour size-Ramsey number ${hat{r}}_s(H)$ of a graph $H$ is defined to be ${hat{r}}_s(H)=min{|E(G)|colon Grightarrow (H)_s}$. We prove that, for all positive integers $k$ and $s$, we have ${hat{r}}_s(P_n^k)=O(n)$, where $P_n^k$ is the $k$th power of the $n$-vertex path $P_n$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
