Independent Sets in Hypergraphs and Related Problems

<p dir="ltr">The primary focus of this dissertation is on understanding certain enumeration questions concerning independent sets in hypergraphs. The contribution is divided into three parts, treated in Chapters 2-4. In his seminal work, Shearer [105] discovered a fundamental connection between zero-free disks for the independence polynomial of graphs and the Lovasz Local Lemma. In Chapter 2, inspired by his work, we are concerned with the zero-free regions (in the complex plane) for the independence polynomial of bounded degree hypergraphs and algorithmic implications thereof. The main result of Chapter 3 is a bound on the number of independent sets in regular, uniform hypergraphs under certain structural conditions. Chapter 4 focuses on counting antichains in generalizations of the Boolean lattice. This chapter can be considered as separate; its roots, however, are partly connected to that of Chapter 3, as both draw inspiration from the work of Jeff Kahn on independent sets of bipartite graphs [68, 70]. </p><p dir="ltr">Chapter 2 is based on the published work: On the zeroes of hypergraph independence polynomials. Combinatorics, Probability and Computing. 2024 Jan; 33(1):65-84. It is joint work with D. Galvin, G. McKinley, W. Perkins and P. Tetali. </p><p dir="ltr">Chapter 3 is based on the published work: On the Number of Independent Sets in Uniform, Regular, Linear Hypergraphs, European Journal of Combinatorics. 2022 Jan 1; 99:103401. It is joint work with E. Cohen, W. Perkins, and P. Tetali. </p><p dir="ltr">Chapter 4 is based on the work under review: Note on the number of antichains in generalizations of the Boolean lattice. arxiv: 2305.16520. It is joint work with J. Park and P. Tetali.</p>