Name
Abstract | ||
|---|---|---|
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 com- pletely occupy a hyperedge and Breaker tries to avoid this. Beck conjectures that if the maximum neighborhood size of F is at most 2n 1 then Breaker has a winning strategy. We disprove this con- jecture by establishing an n-uniform hypergraph with maximum neighborhood size 3 � 2n 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 Neighbourhood Conjecture. |
Year | Venue | Keywords |
|---|---|---|
2008 | Clinical Orthopaedics and Related Research | game theory,maximum degree,discrete mathematics |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Mathematical economics,Open problem,Vertex (geometry),Hypergraph,Degree (graph theory),Conjecture,Mathematics | Journal | abs/0810.1 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Heidi Gebauer | 1 | 83 | 11.07 |