8
$\begingroup$

Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ edges.

Surely this problem has been studied before. Is there a good reference for it, or any interesting conjectures here?

Edit:

I was aware of the fact that when $m\le \frac{1}{r}\binom{n}{2}$ that $R((n,m);r) = n$.

However, the problem still seems very interesting to me. For example, what can we say about the shape of $R((n,(1/2+\epsilon)\binom{n}{2});2)$? This should be at most (roughly) $n2^{2\epsilon n}$ by a modification of the Erdos-Szekeres argument for finding cliques. But if I use a random coloring, then I think we only get a lower bound of $2^{\Omega(\epsilon^2 n)}$ by appealing to a Chernoff bound.

Improve this question
$\endgroup$
2
  • $\begingroup$ One simple comment is that if $m\leq \frac{1}{r}\binom{n}{2}$, then $R((n,m);r)=n$ (by taking the majority color class). So the parameter is only interesting for "dense" graphs. $\endgroup$
    – Louis D
    Commented Jan 20, 2023 at 17:07
  • 1
    $\begingroup$ I think you might want to add some restrictions (such as connected subgraph) otherwise by pigeon-hole principle isn't this just $$ N = \max \left[ \min\left\{ k,\ m\leq \left\lceil \frac{1}{r}\binom{k}{2}\right\rceil \right\} ,n \right]$$ ? $\endgroup$
    – Thomas Lesgourgues
    Commented Jan 23, 2023 at 1:09

1 Answer 1

Reset to default
4
$\begingroup$

A good reference is Radziszowski's article Small Ramsey Numbers, which gets updated as new results are proven. In particular, this refers to basically all known Ramsey style results. The ones you're interested in have the notation $R(G_1,G_2,\dots,G_r)$, where we're $r$-coloring the edges of a $K_N$, looking to avoid a monochromatic $G_j$. Your $G$'s run through all possible graphs with $n$ vertices and $m$ edges. These questions are answered for small $n$, or for $G_j$ of certain types (e.g., a complete graph, complete graph minus an edge, tree, cycle, cube, fan, wheel, book, star, path). For general $n,m,r$ the question is open, but this article links to dozens of others that deal with various special cases.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .