2008/10/10 by Heidi Gebauer, Gebauer, Heidi
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #Limits and Structures in Graph Theory #cs.DM #cs.GT
paper · pdf · doi:10.48550/arxiv.0810.1981
14 pages, 3 figures
arxiv created 2008/10/10 · openalex publication_date 2008/10/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the following Maker/Breaker game. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph F, with Maker going first. Maker's goal is to completely occupy a hyperedge and Breaker tries to avoid this. Beck conjectures that if the maximum neighborhood size of F is at most 2^(n-1) then Breaker has a winning strategy. We disprove this conjecture by establishing an n-uniform hypergraph with maximum neighborhood size 3*2^(n-3) where Maker has a winning strategy. Moreover, we show how to construct an n-uniform hypergraph with maximum degree 2^(n-1)/n where Maker has a winning strategy. Finally we show that each n-uniform hypergraph with maximum degree at most 2^(n-2)/(en) has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.