Solved diagonal online-Ramsey lower bound and a common-core obstruction to greedy Painter
Statement
Online Ramsey numbers
Jacob Fox
The online Ramsey number 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 to be the minimum such that the builder can force a win in moves, i.e., force a red or a blue .
Note: .
(Conlon) For infinitely many , . The constant can probably be made much smaller.
Note that if for all , then for some . This is a possible strategy for improving lower bounds on diagonal Ramsey numbers. More modestly, we can ask:
Problem: Show that for some .
Related: (Conlon--Fox--Grinshpun) , where means up to a factor. The lower bound is proved via a lopsided local lemma.
\section{Erd\H{o}s--Hajnal for tournaments}
Maria Chudnovsky
Let denote the following tournament on vertices labeled by : orient , and orient all remaining pairs where .
Record
- Source
- Added
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.