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.
Vorschau
Rechte
Nutzung und Vervielfältigung:
Bitte beachten Sie, dass einzelne Bestandteile der Publikation anderweitigen Lizenz- bzw. urheberrechtlichen Bedingungen unterliegen können.