Timeline for Ramsey multiplicity
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 16, 2020 at 4:23 | comment | added | Gerry Myerson | There's a very nice proof of $m(3)\ge2$. Call it a biangle when a red edge and a blue edge meet at a vertex. There are at most six biangles at each vertex of $K_6$, so at most $36$ biangles total in a coloring of $K_6$. Each non-monochrome triangle has exactly two biangles, so there are at most $36/2=18$ non-monochrome triangles. But there are ${6\choose3}=20$ triangles in $K_6$, so at least two of them must be monochrome. | |
| Jul 16, 2020 at 3:57 | history | edited | Andrés E. Caicedo | CC BY-SA 4.0 |
added 195 characters in body
|
| Nov 18, 2012 at 7:07 | vote | accept | Andrés E. Caicedo | ||
| Jun 14, 2010 at 14:55 | answer | added | Andrés E. Caicedo | timeline score: 12 | |
| Jun 14, 2010 at 14:34 | history | edited | Andrés E. Caicedo | CC BY-SA 2.5 |
added 171 characters in body; edited tags
|
| Jun 14, 2010 at 8:17 | comment | added | Thomas Bloom | Isn't the upper bound easy to show, since it's just the expected number of monochromatic K_n from a random red/blue colouring? | |
| May 31, 2010 at 0:55 | answer | added | Simon Thomas | timeline score: 2 | |
| May 26, 2010 at 20:19 | comment | added | Andrés E. Caicedo | I suppose for a reasonable infinitary version one would consider generating sets. Given a coloring $c$ of the edges of $K_\omega$, define a set $S$ of monochromatic copies of $K_\omega$ to be generating iff any monochromatic copy of $K_\omega$ is a subgraph of one in $S$. Call the size of a smallest generating set $g(c)$. A reasonable variant of $m(\omega)$ would be the size of $g(c)$ for "most" $c$, for some appropriate version of "most" (there are several natural measures). Of course, playing with this and its variants takes us in a completely different direction than the finite case. | |
| May 26, 2010 at 17:45 | comment | added | Tony Huynh | @Simon: Sorry, I meant to type $m(\omega) \geq \omega$. But you are clearly correct that $m(\omega)=2^{\omega}$. The countable subsets of $\omega$ have cardinality $2^{\omega}$. | |
| May 26, 2010 at 17:27 | comment | added | Simon Thomas | Unless you allow yourself to countable all monochromatic $K_{\omega}$ when the answer is clearly $m(\omega) = 2^{\omega}$. | |
| May 26, 2010 at 17:26 | comment | added | Tony Huynh | @Simon: If we insist that the monochromatic $K_{\omega}$ is maximal, isn't $m(\omega)=1$? I can colour all the edges red. | |
| May 26, 2010 at 17:26 | comment | added | Simon Thomas | Even worse, $m(\omega) = 1$, since you can't do better than this if all the edges are given the same color. Pity about that! | |
| May 26, 2010 at 17:23 | comment | added | Tony Huynh | @Joel: Isn't it clear that $m(\omega)=\omega$? For example we can partition the vertex set of $K_{\omega}$ into $\omega$ sets of size $\omega$. | |
| May 26, 2010 at 17:22 | comment | added | Simon Thomas | Of course, in the case of $m(\omega)$, you would presumably add the condition that the monochromatic $K_{\omega}$ are maximal? | |
| May 26, 2010 at 17:06 | comment | added | Joel David Hamkins | Do you know $m(\omega)$, in the infinitary Ramsey case? | |
| May 26, 2010 at 16:47 | history | asked | Andrés E. Caicedo | CC BY-SA 2.5 |