CaltechAUTHORS
  A Caltech Library Service

Set Systems with No Singleton Intersection

Keevash, Peter and Mubayi, Dhruv and Wilson, Richard M. (2006) Set Systems with No Singleton Intersection. SIAM Journal on Discrete Mathematics, 20 (4). pp. 1031-1041. ISSN 0895-4801. doi:10.1137/050647372. https://resolver.caltech.edu/CaltechAUTHORS:KEEsiamjd06

[img]
Preview
PDF
See Usage Policy.

178kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:KEEsiamjd06

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/050647372DOIUNSPECIFIED
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.
Subject Keywords:extremal set theory, restricted intersections
Issue or Number:4
DOI:10.1137/050647372
Record Number:CaltechAUTHORS:KEEsiamjd06
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:KEEsiamjd06
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7484
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:03 Mar 2007
Last Modified:08 Nov 2021 20:43

Repository Staff Only: item control page