2-Colorings of Hypergraphs with Large Girth

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 Δ(H) be the maximal degree of vertices of a hypergraph H. By Δ_k(n,g) we denote the minimal degree Δ such that there exists an n-homogeneous hypergraph H with maximal degree Δ and girth at least g but without property B_k. In the paper, an upper bound for Δ_k(n,g) is obtained.