Disproving the Neighborhood Conjecture

Details Disproving the Neighborhood Conjecture Disproving the Neighborhood Conjecture

2008-10-10

arxiv.org/abs/0810.1981v1

Computer Science

Computer Science and Game Theory

14 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Disproving the Neighborhood Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Disproving the Neighborhood Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Disproving the Neighborhood Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-449013