Date:
Sun, 28/05/201711:00-13:00
Location:
Rothberg B221 (CS building)
First talk (11:00--11:50):
Speaker: Ilan Karpas, HU
Tilte: Two results about union-closed families
Abstract: A family F of subsets of [n] is called union-closed, if for any A,B \in F, A \cup B \in F. A famous conjecture, known as Frankl's conjecture, states that any union-closed family F which contains a non-empty set, has an element i \in [n] that appears in at least half the sets in the family. We will see, using very elementary Boolean analysis considerations, that the statement is true, provided |F|>=2^{n-1}. This improves a result by Tom Eccles, who proved the conjecture holds for |F|>=(2/3-1/104)2^n.
Our second result, is that for any union-closed family F of subsets of [n]:
|D^+ F \setminus F|<=2^{n-1}, where D^+F denotes the upper shadow of F.
This result is tight.
-----------------------------------------------------
Second talk (12:00--12:50):
Speaker: Michael Simkin, HU
Title: The Threshold for the Appearance of Latin Square-Like Objects in Random Arrays
Abstract: Consider an $n \times n$ $(0,1)$-matrix $M$, each entry an independent random variable equal to $1$ with probability $p$. In 1964 Erd\H{o}s and R\'enyi determined that the threshold for $M$ to support a permutation matrix is $p = \frac{\log n}{n}$; the same as the threshold for the disappearance of all $0$ rows and columns.
A natural generalization is to consider an $n \times n \times m$ $(0,1)$-array $A$, each entry an independent random variable equal $1$ with probability $p$. We ask: what is the threshold for $A$ to support a maximal-size collection of $1$s with no more than a single $1$ in each row, column, or shaft? When $m = n$ such a configuration is a Latin square, and determining the threshold is an open problem. We show that for $m = (1 - \varepsilon) n$ and $m = (1 + \varepsilon) n$ the threshold is $p = \frac{\log n}{n}$. The techniques for $m < n$ and $m > n$ are quite different. In the former case we rely on bounds on the permanent of $(0,1)$-matrices and in the latter on an analysis of the random greedy packing algorithm in random hypergraphs.
Joint work with Zur Luria
Speaker: Ilan Karpas, HU
Tilte: Two results about union-closed families
Abstract: A family F of subsets of [n] is called union-closed, if for any A,B \in F, A \cup B \in F. A famous conjecture, known as Frankl's conjecture, states that any union-closed family F which contains a non-empty set, has an element i \in [n] that appears in at least half the sets in the family. We will see, using very elementary Boolean analysis considerations, that the statement is true, provided |F|>=2^{n-1}. This improves a result by Tom Eccles, who proved the conjecture holds for |F|>=(2/3-1/104)2^n.
Our second result, is that for any union-closed family F of subsets of [n]:
|D^+ F \setminus F|<=2^{n-1}, where D^+F denotes the upper shadow of F.
This result is tight.
-----------------------------------------------------
Second talk (12:00--12:50):
Speaker: Michael Simkin, HU
Title: The Threshold for the Appearance of Latin Square-Like Objects in Random Arrays
Abstract: Consider an $n \times n$ $(0,1)$-matrix $M$, each entry an independent random variable equal to $1$ with probability $p$. In 1964 Erd\H{o}s and R\'enyi determined that the threshold for $M$ to support a permutation matrix is $p = \frac{\log n}{n}$; the same as the threshold for the disappearance of all $0$ rows and columns.
A natural generalization is to consider an $n \times n \times m$ $(0,1)$-array $A$, each entry an independent random variable equal $1$ with probability $p$. We ask: what is the threshold for $A$ to support a maximal-size collection of $1$s with no more than a single $1$ in each row, column, or shaft? When $m = n$ such a configuration is a Latin square, and determining the threshold is an open problem. We show that for $m = (1 - \varepsilon) n$ and $m = (1 + \varepsilon) n$ the threshold is $p = \frac{\log n}{n}$. The techniques for $m < n$ and $m > n$ are quite different. In the former case we rely on bounds on the permanent of $(0,1)$-matrices and in the latter on an analysis of the random greedy packing algorithm in random hypergraphs.
Joint work with Zur Luria