Disproving the Neighborhood Conjecture

Simple item page
dc.creatorGebauer, Heidi
dc.date2008-10-10
dc.date.accessioned2026-07-07T10:09:25Z
dc.date.available2026-07-07T10:09:25Z
dc.descriptionWe 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.
dc.description14 pages, 3 figures
dc.identifierhttps://arxiv.org/abs/0810.1981
dc.identifierhttp://arxiv.org/abs/0810.1981
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/171316
dc.subjectComputer Science and Game Theory
dc.subjectDiscrete Mathematics
dc.subjectG.2.2
dc.titleDisproving the Neighborhood Conjecture
dc.typetext

Files

Collections

arXiv