ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Online Ramsey numbers

Jacob Fox

The online Ramsey number r~(s,n)\tilde r(s,n) is defined via a game as follows. Initially there are infinitely many vertices and no edges. Each turn, the builder adds an edge to the graph, and the painter colors the edge blue or red. We define r~(s,n)\tilde r(s,n) to be the minimum mm such that the builder can force a win in mm moves, i.e., force a red KsK_s or a blue KnK_n.

Note: r~(s,n)≤r^(s,n)=(r(s,n)2)\tilde r(s,n) \le \hat r (s,n) = \binom{r(s,n)}{2}.

(Conlon) For infinitely many nn, r~(n,n)≤(0.99)n(r(n,n)2)\tilde r(n,n) \le (0.99)^n \binom{r(n,n)}{2}. The constant 0.990.99 can probably be made much smaller.

Note that if r~(n,n)≥(1.999)n\tilde r(n,n) \ge (1.999)^n for all nn, then r(n,n)≥(2+δ)nr(n,n) \ge (\sqrt 2 + \delta)^n for some δ>0\delta > 0. This is a possible strategy for improving lower bounds on diagonal Ramsey numbers. More modestly, we can ask:

Problem: Show that r~(n,n)≥(2+ϵ)n\tilde r(n,n) \ge (\sqrt 2 + \epsilon)^n for some ϵ>0\epsilon > 0.

Related: (Conlon--Fox--Grinshpun) r~(3,n)=Θ~(n3)\tilde r(3,n) = \tilde \Theta(n^3), where Θ~\tilde\Theta means up to a poly log(n)\text{poly\,log}(n) factor. The lower bound is proved via a lopsided local lemma.

\section{Erd\H{o}s--Hajnal for tournaments}

Maria Chudnovsky

Let T∗T^* denote the following tournament on 66 vertices labeled by {1,2,…,6}\{1, 2, \dots, 6\}: orient 6→1,6→3,5→2,4→16 \to 1, 6 \to 3, 5 \to 2, 4 \to 1, and orient all remaining pairs i→ji \to j where i<ji < j.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.