Events Search and Views Navigation
January 2020
Adam Zsolt Wagner, The largest projective cube-free subsets of $Z_{2^n}$
What is the largest subset of $Z_{2^n}$ that doesn't contain a projective d-cube? In the Boolean lattice, Sperner's, Erdos's, Kleitman's and Samotij's theorems state that families that do not contain many chains must have a very specific layered structure. We show that if instead of $Z_2^n$ we work in $Z_{2^n}$, analogous statements hold if one replaces the word k-chain by projective cube of dimension $2^{k-1}$. The largest d-cube-free subset of $Z_{2^n}$, if d is not a power of two, exhibits…
Find out more »Dillon Mayhew, Courcelle’s Theorem for hypergraphs
Courcelle's Theorem is an influential meta-theorem published in 1990. It tells us that a property of graph can be tested in polynomial time, as long as the property can expressed in the monadic second-order logic of graphs, and as long as the input is restricted to a class of graphs with bounded tree-width. There are several properties that are NP-complete in general, but which can be expressed in monadic logic (3-colourability, Hamiltonicity...), so Courcelle's Theorem implies that these difficult properties…
Find out more »