{"id":"arxiv/2603.12610","url":"https://arxiv.org/abs/2603.12610","tags":["math.CO"],"score":0,"title":"A step towards the Erdős-Rogers problem","domain":"math.CO","source":"arxiv","authors":["Longma Du","Xinyu Hu","Ruilong Liu","Guanghui Wang"],"reviews":0,"subject":"math.CO","summary":"For $2\\le k\\le t<s$, the Erdős-Rogers function $f^{(k)}_{t,s}(N)$ denotes the largest $m$ such that every $K^{(k)}_s$-free $k$-graph on $N$ vertices contains a $K^{(k)}_t$-free induced subgraph on $m$ vertices. Mubayi and Suk (J. London Math. Soc. 2018) conjectured that $f^{(k)}_{k+1,k+2}(N)=(\\log_{(k-2)}N)^{Θ(1)}$ for $k\\ge 4$, where $\\log_{(i)}$ denotes the $i$-fold iterated logarithm. This is equivalent to the statement that $f^{(k)}_{k+1,s}(N)=(\\log_{(k-2)}N)^{Θ(1)}$ for every $s\\ge k+2$. In this paper, we introduce multi-color patterns into a random construction of a $2$-graph to build…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-13","reactions":{}}