Published December 15, 2006 | Version public
Journal Article Open

Set Systems with No Singleton Intersection

Abstract

Let $\mathcal{F}$ be a $k$-uniform set system defined on a ground set of size $n$ with no singleton intersection; i.e., no pair $A,B\in\mathcal{F}$ has $|A\cap B|=1$. Frankl showed that $|\mathcal{F}|\leq\binom{n-2}{k-2}$ for $k\geq4$ and $n$ sufficiently large, confirming a conjecture of Erdős and Sós. We determine the maximum size of $\mathcal{F}$ for $k=4$ and all $n$, and also establish a stability result for general $k$, showing that any $\mathcal{F}$ with size asymptotic to that of the best construction must be structurally similar to it.

Additional Information

©2006 Society for Industrial and Applied Mathematics. Received by the editors December 12, 2005; accepted for publication (in revised form) June 5, 2006; published electronically December 15, 2006. The first author's [PK] research was supported in part by NSF grant DMS-0555755. This author's [D.M.] research was supported in part by NSF grant DMS-0400812 and by an Alfred P. Sloan fellowship.

Files

KEEsiamjdm06.pdf

Files (178.7 kB)

Name Size Download all
md5:8a4d2a559ee06a6362e793fe0989cb0e
178.7 kB Preview Download

Additional details

Identifiers

Eprint ID
7484
Resolver ID
CaltechAUTHORS:KEEsiamjd06

Dates

Created
2007-03-03
Created from EPrint's datestamp field
Updated
2021-11-08
Created from EPrint's last_modified field