RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2019 Volume 488, Pages 168–176 (Mi znsl6910)

This article is cited in 2 papers

On the Erdős–Hajnal problem in the case of $3$-graphs

D. D. Cherkashinabc

a Chebyshev Laboratory, St. Petersburg State University
b Moscow Institute of Physics and Technology, Moscow region, 141700, Russia
c National Research University Higher School of Economics, St. Petersburg, Russia

Abstract: Let $m(n,r)$ denote the minimal number of edges in an $n$-uniform hypergraph which is not $r$-colorable. For the broad history of the problem see [10]. It is known [4] that for a fixed $n$ the sequence
$$ \frac{m(n,r)}{r^n} $$
has a limit. The only trivial case is $n=2$ in which $m(2,r) = \binom{r+1}{2}$. In this note we focus on the case $n=3$. First, we compare the existing methods in this case and then improve the lower bound.

Key words and phrases: extremal combinatorics, hypergraph colorings.

UDC: 519.176

Received: 14.11.2019

Language: English



© Steklov Math. Inst. of RAS, 2024