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.

Rechte

Nutzung und Vervielfältigung:


CC BY 4.0

Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.

Zitieren

Zitierform:
Zitierform konnte nicht geladen werden.