Some Combinatorial Games on Hypergraphs : Builder Game and Discrepancy

This thesis explores several graph-theoretical problems and presents three games played on hypergraphs.

In Chapter 2, we present theoretical results related to the existence of paths and expanders in hypergraphs. Chapters 3 and 4 discuss properties of random graph processes and an approximation of the number of edges in a k-nearest neighbor graph.

In Chapter 5, the Builder game focuses on constructing specific subgraphs in 3-uniform hypergraphs through controlled random graph processes.  The player must construct a subgraph that satisfies properties such as minimum degree or includes a perfect matching, a Hamilton path, a k-vertex tree, or a cycle, within a given edge budget. 

Chapter 6 extends the study of discrepancy games, focusing on the (p:p)-discrepancy game played on hypergraphs. In these games, two players, the Balancer and the Unbalancer, alternately claim vertices of a hypergraph. The Balancer aims to choose approximately half of the vertices in each edge, while the Unbalancer tries to disrupt this.

In Chapter 7 we extend the study of Vector balancing games. These are two-player positional games in which one player selects vectors, and the other player assigns signs to minimize the infinity norm of the resulting sum.

Rights

Use and reproduction:


CC BY 4.0

Please note that individual components of the publication may be subject to other licensing or copyright conditions.

Cite

Citation style:
Could not load citation form.