This article is cited in 1 paper

2-Colorings of Hypergraphs with Large Girth

Yu. A. Demidovich

Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region

Abstract: 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.

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

UDC: 517

Received: 16.06.2019
Revised: 11.12.2019

DOI: 10.4213/mzm12463

 English version: Mathematical Notes, 2020, 108:2, 188–200

Bibliographic databases:

• 
• 
• 
•