|
This article is cited in 1 scientific paper (total 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.
Received: 16.06.2019 Revised: 11.12.2019
Citation:
Yu. A. Demidovich, “2-Colorings of Hypergraphs with Large Girth”, Mat. Zametki, 108:2 (2020), 200–214; Math. Notes, 108:2 (2020), 188–200
Linking options:
https://www.mathnet.ru/eng/mzm12463https://doi.org/10.4213/mzm12463 https://www.mathnet.ru/eng/mzm/v108/i2/p200
|
Statistics & downloads: |
Abstract page: | 270 | Full-text PDF : | 52 | References: | 42 | First page: | 3 |
|