Kameryn Williams: Maximal unbalanced families

This talk is in fact taking place in the Algebra, Geometry, Cryptology Seminar on Tuesday (October 2, 3:00 p.m. in MG 139).

The presentation will be on results obtained during an REU under Justin Moore. Their joint paper is available at http://arxiv.org/abs/1209.2309.

Title: Maximal unbalanced families

Abstract: A family of subsets of an n element set is unbalanced if the convex hull of its characteristic vectors misses the diagonal in the $n$-cube. Such a family is maximal if every proper superset is balanced. I will present results on the upper and lower bounds for the number of maximal unbalanced families over an $n$ element set. Both bounds are of the form $2^{C n^2}$, for some $C > 0$. In particular, the proof for the upper bound is obtained via the geometry of the collection of all maximal unbalanced families for some $n$. Additionally I will present some results on the automorphisms of this collection and conjecture that the only automorphisms correspond to complementations or permutations on the n element set.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.