|
Zapiski Nauchnykh Seminarov POMI, 2019, Volume 488, Pages 168–176
(Mi znsl6910)
|
|
|
|
This article is cited in 2 scientific papers (total 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.
Received: 14.11.2019
Citation:
D. D. Cherkashin, “On the Erdős–Hajnal problem in the case of $3$-graphs”, Combinatorics and graph theory. Part XI, Zap. Nauchn. Sem. POMI, 488, POMI, St. Petersburg, 2019, 168–176
Linking options:
https://www.mathnet.ru/eng/znsl6910 https://www.mathnet.ru/eng/znsl/v488/p168
|
Statistics & downloads: |
Abstract page: | 96 | Full-text PDF : | 25 | References: | 25 |
|