Mathematics Colloquium: Order-size pairs in graphs and hypergraphs – forcing and avoiding them
Author: Lona
Speaker: Maria Aksenovich, Karlsruhe Institute of Technology
Abstract: A graph has a pair (m,f) if it has an induced subgraph on m vertices and f edges. We write (n,e)-> (m,f) if any graph on n vertices and e edges has a pair (m,f). Let the forcing set for (m,f) be {e: (n,e)-> (m,f)}. These notions were first introduced and investigated by Erdos, Furedi, Rothschild, and Sos. They investigated sizes of forcing sets for pairs (m,f), indicating which pairs are “easy” to force and which are not.In joint work with Lea Weber, we show that for infinitely many pairs their forcing set is empty. In the case of r-uniform hypergraphs, for r>2, Weber showed that the forcing set for (m,f) has zero density for most values of f. Surprisingly, it was not immediately clear whether there are nontrivial pairs (m,f), with forcing sets of positive density. In a joint work with Balogh, Clemen, and Weber we show that there is such a pair in case r=3 and conjecture that it is the only such pair.