Small doubling, atomic structure and $\ell$-divisible set families
dc.contributor.author
Gishboliner, Lior
dc.contributor.author
Sudakov, Benny
dc.contributor.author
Tomon, István
dc.date.accessioned
2023-01-16T08:06:04Z
dc.date.available
2023-01-13T13:42:15Z
dc.date.available
2023-01-16T08:06:04Z
dc.date.issued
2022-09-30
dc.identifier.issn
2397-3129
dc.identifier.other
10.19086/da.38586
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/592228
dc.identifier.doi
10.3929/ethz-b-000592228
dc.description.abstract
Let $\mathcal{F}\subset 2^{[n]}$ be a set family such that the intersection of any two members of $\mathcal{F}$ has size divisible by $\ell$. The famous Eventown theorem states that if $\ell=2$ then $|\mathcal{F}|\leq 2^{\lfloor n/2\rfloor}$, and this bound can be achieved by, e.g., an `atomic' construction, i.e. splitting the ground set into disjoint pairs and taking their arbitrary unions. Similarly, splitting the ground set into disjoint sets of size $\ell$ gives a family with pairwise intersections divisible by $\ell$ and size $2^{\lfloor n/\ell\rfloor}$. Yet, as was shown by Frankl and Odlyzko, these families are far from maximal. For infinitely many $\ell$, they constructed families $\mathcal{F}$ as above of size $2^{Ω(n\log \ell/\ell)}$. On the other hand, if the intersection of any number of sets in $\mathcal{F}\subset 2^{[n]}$ has size divisible by $\ell$, then it is easy to show that $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}$. In 1983 Frankl and Odlyzko conjectured that $|\mathcal{F}|\leq 2^{(1+o(1)) n/\ell}$ holds already if one only requires that for some $k=k(\ell)$ any $k$ distinct members of $\mathcal{F}$ have an intersection of size divisible by $\ell$. We completely resolve this old conjecture in a strong form, showing that $|\mathcal{F}|\leq 2^{\lfloor n/\ell\rfloor}+O(1)$ if $k$ is chosen appropriately, and the $O(1)$ error term is not needed if (and only if) $\ell \, | \, n$, and $n$ is sufficiently large. Moreover the only extremal configurations have `atomic' structure as above. Our main tool, which might be of independent interest, is a structure theorem for set systems with small 'doubling'.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Alliance of Diamond Open Access Journals
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Eventown
en_US
dc.subject
l-divisible set family
en_US
dc.subject
Frankl-Odlyzko conjecture
en_US
dc.title
Small doubling, atomic structure and $\ell$-divisible set families
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.journal.title
Discrete Analysis
ethz.journal.volume
11
en_US
ethz.pages.start
38586
en_US
ethz.size
16 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.grant
Problems in Extremal and Probabilistic Combinatorics
en_US
ethz.identifier.arxiv
2103.16479v3
ethz.publication.place
Cambridge
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02500 - Forschungsinstitut für Mathematik / Institute for Mathematical Research
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03993 - Sudakov, Benjamin / Sudakov, Benjamin
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02500 - Forschungsinstitut für Mathematik / Institute for Mathematical Research
ethz.grant.agreementno
196965
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2023-01-13T13:42:16Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2023-01-16T08:06:05Z
ethz.rosetta.lastUpdated
2023-02-07T09:52:38Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Small%20doubling,%20atomic%20structure%20and%20$%5Cell$-divisible%20set%20families&rft.jtitle=Discrete%20Analysis&rft.date=2022-09-30&rft.volume=11&rft.spage=38586&rft.issn=2397-3129&rft.au=Gishboliner,%20Lior&Sudakov,%20Benny&Tomon,%20Istv%C3%A1n&rft.genre=article&rft_id=info:doi/10.19086/da.38586&
Files in this item
Publication type
-
Journal Article [131618]