Disproving the Neighborhood Conjecture - Computer Science > Computer Science and Game TheoryReport as inadecuate




Disproving the Neighborhood Conjecture - Computer Science > Computer Science and Game Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: We study the following Maker-Breaker game. Maker and Breaker take turns inchoosing 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 avoidthis. Beck conjectures that if the maximum neighborhood size of F is at most2^n-1 then Breaker has a winning strategy. We disprove this conjecture byestablishing an n-uniform hypergraph with maximum neighborhood size 3*2^n-3where Maker has a winning strategy. Moreover, we show how to construct ann-uniform hypergraph with maximum degree 2^n-1-n where Maker has a winningstrategy. Finally we show that each n-uniform hypergraph with maximum degree atmost 2^n-2-en has a proper halving 2-coloring, which solves another openproblem posed by Beck related to the Neighborhood Conjecture.



Author: Heidi Gebauer

Source: https://arxiv.org/







Related documents