[Theory] UC Theory Seminar

[Alexander Razborov]

Departments of Mathematics & Computer Science
Combinatorics & Theory Seminar

Tuesday, March 8, 3:30pm
John Crerar Library 298

Julia Wolf (University of Cambridge)

TITLE:  Irregular triads in 3-uniform hypergraphs

ABSTRACT: Szemerédi's celebrated regularity lemma states, roughly 
speaking, that the vertex set of any large graph can be partitioned into 
a bounded number of sets in such a way that all but a small proportion 
of pairs of sets from this partition induce a `regular' graph. The 
example of the half-graph shows that the existence of irregular pairs 
cannot be ruled out in general.

Recognising the half-graph as an instance of the so-called 'order 
property' from model theory, Malliaris and Shelah proved in 2014 that if 
one assumes that the large graph contains no half-graphs of a fixed size 
(as induced bipartite subgraphs), then it is possible to obtain a 
regularity partition with no irregular pairs. In addition, the number of 
parts of the partition is polynomial in the regularity parameter, and 
the density of each regular pair is either close to zero or close to 1.

This beautiful result exemplifies a long-standing theme in model theory, 
namely that so-called stable structures (which are characterised by an 
absence of large instances of the order property), are extremely 
well-behaved.

In this talk I will present recent joint work with Caroline Terry (OSU), 
in which we define a higher-arity generalisation of the order property 
and prove that its absence characterises those large 3-uniform 
hypergraphs whose regularity decompositions allow for particularly good 
control of the irregular triads.

%%%%%%%%%%%%%%%%%%%%%%%
While the University will no longer require wearing masks in this 
setting, we will set aside a couple of tables (more if it becomes
necessary) designated "masks required".