Inducing Graphs, Hypergraphs, and Tournaments

Abstract

In this thesis, we consider two problems in extremal and probabilistic combinatorics. The first question relates to the so-called Edge-Statistics conjecture of Alon, Hefetz, Krivelevich and Tyomkyn, stated as follows: given integers k ≥ 1 and 0 < ℓ <k(k-1)/2, when a uniformly random k-vertex subset is sampled from a large graph, the probability of it inducing precisely ℓ edges is at most 1/e + o_k(1). Independent recent studies have proven this conjecture in different parametrised regimes of k and ℓ, yielding a complete proof overall. We begin by briefly discussing some of the methods used in these papers and then shift our focus to the generalisation of the conjecture to uniform hypergraphs, a direction of research suggested by Alon et al.. We detail our attempts to extend the techniques used in the aforementioned papers to the hypergraph framework and conclude with a discussion on the limitations of our approaches and potential ways to address them. The second problem we tackle addresses the notion of quasirandom tournaments. A sequence of tournaments {T_n}n≥1 is said to be quasirandom if and only if every tournament on k vertices appears as a subtournament in T_n with a density that is 1+o(1) times its expected density in a random tournament. A tournament H is said to be quasirandom-forcing if it has the following property: if the density of H in T_n is 1 + o(1) times the expected density of H in a random tournament, then this is true for every subtournament of T_n, i.e., {T_n}n≥1 is quasirandom. Recent papers have proven that the only quasirandom-forcing tournaments are transitive tournaments on at least four vertices and one particular tournament on five vertices. We generalise this notion of forcing quasirandomness to pairs of tournaments and make partial progress towards characterising all non-transitive quasirandom-forcing pairs. We then state the methods we intend to use to handle the remaining pairs and finish with some open problems regarding pairs containing a transitive tournament.