|
|||||
 |
|
|
|
|
|
|
|
Extremal
hypergraphs for the Erdős–Selfridge theorem using labelings
of binary trees
Kathryn Grossmann, Dongming (Merrick) Hua, Benjamin Pagano, Hannah Sheats, Eric Sundberg, Ann Thompson and Sireesh Vinnakota |
|
Vol. 17 (2024), No. 5, 845–899
|
Abstract |
|
A positional game is a sort of tic-tac-toe played on a hypergraph — a generalized graph where each “edge” may connect any number of vertices in , not just two. The Erdős–Selfridge theorem gives a simple criterion for the existence of a winning strategy for the first player on a finite hypergraph. The bound in the Erdős–Selfridge theorem is tight, and numerous extremal hypergraphs exist that realize the bound. While characterizing all extremal hypergraphs for the Erdős–Selfridge theorem is still an open problem, we make progress in the following way. Many extremal hypergraphs can be formed by labeling the nodes of a rooted binary tree and defining each edge to be the set of labels on a root-to-leaf path. For a restricted set of labelings, we characterize when a given labeling will realize an extremal hypergraph for the Erdős–Selfridge theorem; therefore, we determine when one side or the other will have a winning strategy for such labelings. |
Keywords
positional games, generalized tic-tac-toe, maker-breaker
games
|
Mathematical Subject Classification
Primary: 91A43, 91A46
|
Milestones
Received: 7 September 2021
Revised: 15 June 2023
Accepted: 19 July 2023
Published: 21 November 2024
Communicated by Joshua Cooper
|
Authors |
| Kathryn Grossmann | |
| Department of Mathematics Occidental College Los Angeles, CA United States |
|
| Dongming (Merrick) Hua | |
| University of California at Santa
Barbara Santa Barbara, CA United States |
|
| Benjamin Pagano | |
| Department of Mathematics Occidental College Los Angeles, CA United States |
|
| Hannah Sheats | |
| Department of Mathematics Ohio State University Columbus, OH United States |
|
| Eric Sundberg | |
| Department of Mathematics Occidental College Los Angeles, CA United States |
|
| Ann Thompson | |
| Department of Mathematics University of Texas at Austin Austin, TX United States |
|
| Sireesh Vinnakota | |
| Department of Mathematics University of California at Irvine Irvine, CA United States |
|
| © 2024 MSP (Mathematical Sciences Publishers). |
