2-Colorings of Hypergraphs with Large Girth

Yu. A. Demidovich

Matematičeskie zametki, Tome 108 (2020) no. 2, pp. 200-214

Résumé

A hypergraph $H=(V,E)$ has property $B_k$ if there exists a 2-coloring of the set $V$ such that each edge contains at least $k$ vertices of each color. We let $m_{k,g}(n)$ and $m_{k,b}(n)$, respectively, denote the least number of edges of an $n$-homogeneous hypergraph without property $B_k$ which contains either no cycles of length at least $g$ or no two edges intersecting in more than $b$ vertices. In the paper, upper bounds for these quantities are given. As a consequence, we obtain results for $m^{*}_k(n)$, i.e., for the least number of edges of an $n$-homogeneous simple hypergraph without property $B_k$. Let $\Delta(H)$ be the maximal degree of vertices of a hypergraph $H$. By $\Delta_k(n,g)$ we denote the minimal degree $\Delta$ such that there exists an $n$-homogeneous hypergraph $H$ with maximal degree $\Delta$ and girth at least $g$ but without property $B_k$. In the paper, an upper bound for $\Delta_k(n,g)$ is obtained.

Détail

Keywords: hypergraphs, girth, property $B$, simple hypergraphs.