Disproving the Neighborhood Conjecture - Computer Science > Computer Science and Game TheoryReportar como inadecuado




Disproving the Neighborhood Conjecture - Computer Science > Computer Science and Game Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.



Autor: Heidi Gebauer

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados