Skip to Main content Skip to Navigation
Conference papers

Pairwise Intersections and Forbidden Configurations

Abstract : Let $f_m(a,b,c,d)$ denote the maximum size of a family $\mathcal{F}$ of subsets of an $m$-element set for which there is no pair of subsets $A,B \in \mathcal{F}$ with $|A \cap B| \geq a$, $|\bar{A} \cap B| \geq b$, $|A \cap \bar{B}| \geq c$, and $|\bar{A} \cap \bar{B}| \geq d$. By symmetry we can assume $a \geq d$ and $b \geq c$. We show that $f_m(a,b,c,d)$ is $\Theta (m^{a+b-1})$ if either $b > c$ or $a,b \geq 1$. We also show that $f_m(0,b,b,0)$ is $\Theta (m^b)$ and $f_m(a,0,0,d)$ is $\Theta (m^a)$. This can be viewed as a result concerning forbidden configurations and is further evidence for a conjecture of Anstee and Sali. Our key tool is a strong stability version of the Complete Intersection Theorem of Ahlswede and Khachatrian, which is of independent interest.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184383
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:38:47 AM
Last modification on : Friday, December 18, 2020 - 5:30:03 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:04:39 AM

File

dmAE0104.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184383, version 1

Collections

Citation

Richard P. Anstee, Peter Keevash. Pairwise Intersections and Forbidden Configurations. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.17-20. ⟨hal-01184383⟩

Share

Metrics

Record views

314

Files downloads

934