Several problems in extremal combinatorics

Abstract

This thesis presents three distinct contributions to extremal combinatorics. First, it resolves a conjecture by Bollobás, Brightwell, and Leader on the prevalence of unate k-SAT functions, proving that for all fixed k≥2, almost all k-SAT functions on n variables are unate (i.e., monotone after negating certain variables). Second, it addresses a question posed by Sapozhenko on the enumeration of q-ary t-error correcting codes. Improving upon previous bounds, it demonstrates that for a broad range of parameters, the number of such codes is tightly bounded by the Hamming bound. Finally, it investigates the commonness and uncommonness of systems of linear equations over finite fields. Answering questions of Kamčev, Liebenau, and Morrison, it shows that all 2k linear systems with k even and girth k-1 are uncommon over sufficiently large finite fields, and provides a near-complete classification of common 25 linear systems. This thesis provides new insights into the structure of various combinatorial objects and contributes to the broader understanding of extremal combinatorics.