On 2‐Colorings of Hypergraphs |
| |
| Authors: | Michael A. Henning Anders Yeo |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF JOHANNESBURG, JOHANNESBURG, SOUTH AFRICAContract grant sponsor: South African National Research Foundation and the University of Johannesburg.;2. ENGINEERING SYSTEMS AND DESIGN, SINGAPORE UNIVERSITY OF TECHNOLOGY AND DESIGN, SINGAPORE, SINGAPORE |
| |
| Abstract: | In this article, we continue the study of 2‐colorings in hypergraphs. A hypergraph is 2‐colorable if there is a 2‐coloring of the vertices with no monochromatic hyperedge. Let  denote the class of all k‐uniform k‐regular hypergraphs. It is known (see Alon and Bregman [Graphs Combin. 4 (1988) 303–306] and Thomassen [J. Amer. Math. Soc. 5 (1992), 217–229] that every hypergraph  is 2‐colorable, provided  . As remarked by Alon and Bregman the result is not true when  , as may be seen by considering the Fano plane. Indeed there are several constructions for building infinite families of hypergraphs in  that are not 2‐colorable. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set X of vertices in a hypergraph H to be a free set in H if we can 2‐color  such that every edge in H receives at least one vertex of each color. We conjecture that for  , every hypergraph  has a free set of size  in H. We show that the bound  cannot be improved for any  and we prove our conjecture when  . Our proofs use results from areas such as transversal in hypergraphs, cycles in digraphs, and probabilistic arguments. |
| |
| Keywords: | blocking sets hypergraphs bipartite 2‐colorable even dicycles. AMS subject classification: 05C69 |
|
|
