A set of vertices $X\subseteq V$ in a simple graph $G(V,E)$ is irredundant if each vertex $x\in X$ is either isolated in the induced subgraph $G[X]$ or else has a private neighbor $y\in V\setminus X$ that is adjacent to $x$ and to no other vertex of $X$. The \emph{mixed Ramsey number} $t(m,n)$ is the smallest $N$ for which every red-blue coloring of the edges of $K_N$ has an $m$-element irredundant set in the blue subgraph or an $n$-element independent set in the red subgraph. In this paper, we determine $t(3,n)$ up to a polylogarithmic factor of order $\log{n}$ by showing that $t(3,n)=O\left(n^{5/4}/{\log^{1/4}{n}}\right)$. Using this result, we verify the special case of a conjecture proposed by Chen, Hattingh, and Rousseau, that is, $\lim_{n\rightarrow \infty}t(4,n)/r(4,n)=0$.
This paper determines the asymptotic behavior of mixed Ramsey numbers \(t(3, n)\). The mixed Ramsey number \(t(m, n)\) is the minimum number \(N\) such that any red-blue coloring of the edges of the complete graph \(K_N\) contains an \(m\)-element irredundant set in the blue subgraph or an \(n\)-element independent set in the red subgraph. A set of vertices \(X\) is irredundant if each vertex \(x \in X\) is either isolated in the induced subgraph \(G[X]\) or has a private neighbor \(y\) outside of \(X\) that is adjacent only to \(x\) in \(X\).
Prior results established that \(c (n/\log n)^{(m-1)/(m^2-m-1)} < t(m, n)\) for some constant \(c\) and that for \(m=3\), \(t(3, n) < (\sqrt{10}/2) n^{3/2}\). Furthermore, it was conjectured that \(\lim_{n \to \infty} t(m, n) / r(m, n) = 0\) for fixed \(m \ge 4\) where \(r(m, n)\) is the standard Ramsey number.
The key innovation of the paper is pinning down \(t(3, n)\) to within a polylogarithmic factor. The authors prove that \(t(3, n) = \Theta(n^{5/4} / \log^{1/4}(n))\). The main technique involves leveraging a structure theorem from Hattingh that provides information about the neighborhoods of vertices when there is no 3-element irredundant set in the blue subgraph, along with Shearer’s lemma on the independence number of triangle-free graphs. They also use a result of Kim that \(r(3,n) = \Theta(n^2/\log n)\).
As an application of their main result, the authors verify the conjecture \(\lim_{n \to \infty} t(m, n) / r(m, n) = 0\) for \(m=4\). The paper depends on Spencer’s lower bound on \(r(m,n)\).
| Action | Title | Date | Authors |
|---|
| Action | Title | Date | Authors |
|---|