Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Food For Thought Seminar

Jason O'Neill

UCSD

Well-separated set systems

Abstract:

Given a finite set $X$ of size $n$, we can form a metric space on the power set $\mathcal{P}(X)$ by the metric $d(A,B) = |A \triangle B|$ where $A \triangle B := (A \cap B^c) \cup (A^c \cap B)$. An $\alpha$-well separated set system is a subset $\mathcal{F} \subset \mathcal{P}(X)$ so that for all distinct $A, B \in \mathcal{F}$, we have that $d(A,B) \geq \alpha n$. In this talk, we will focus on the case where $\alpha= \frac{1}{2}$ and use linear algebra techniques to explore bounding the size of an $\alpha$-well separated family. We will also discuss the construction of these large $\alpha$-well separated set systems via Hadamard matrices.

May 7, 2019

1:00 PM

AP&M 7321

****************************