Thirty-Third Annual Victorian Algebra Conference, Sydney, Australia, 2015

Register for: VAC33

Details of talk

TitleDefinability of $\mathbb{SP}$-classes of uniform hypergraphs
PresenterLucy Ham (La Trobe University)
Author(s)Ms Lucy Ham

An $\mathbb{SP}$-class of $k$-uniform hypergraphs is a class of $k$-uniform
hypergraphs closed under taking induced substructures and direct products. The
uniform hypergraphs are just the simple graphs.
Using results of Erd\H{o}s and Hajnal, we show that for $k>2$, no
$\mathbb{SP}$-class of $k$-uniform hypergraphs with bounded chromatic number is
definable by a single
first-order sentence, except in two trivial cases. This result is analogous to
one proved by Caicedo for simple graphs (after Erd\H{o}s, Nesetril and Pultr),
where there are four exceptional cases. We also show that both our result
and Caicedo’s continue to hold when we restrict to the class of finite uniform
hypergraphs, verifying the finite level $\mathbb{SP}$-preservation theorem in
case. The finite level $\mathbb{SP}$-preservation theorem remains open for
arbitrary relational structures.