Structure and supersaturation for intersecting families
dc.contributor.author
Balogh, József
dc.contributor.author
Das, Shagnik
dc.contributor.author
Liu, Hong
dc.contributor.author
Sharifzadeh, Maryam
dc.contributor.author
Tran, Tuan
dc.date.accessioned
2019-06-19T09:26:49Z
dc.date.available
2019-06-19T02:13:02Z
dc.date.available
2019-06-19T09:26:49Z
dc.date.issued
2019-05-31
dc.identifier.issn
1097-1440
dc.identifier.issn
1077-8926
dc.identifier.other
10.37236/7683
dc.identifier.uri
http://hdl.handle.net/20.500.11850/348406
dc.identifier.doi
10.3929/ethz-b-000348406
dc.description.abstract
The extremal problems regarding the maximum possible size of intersecting families of various combinatorial objects have been extensively studied. In this paper, we investigate supersaturation extensions, which in this context ask for the minimum number of disjoint pairs that must appear in families larger than the extremal threshold. We study the minimum number of disjoint pairs in families of permutations and in k-uniform set families, and determine the structure of the optimal families. Our main tool is a removal lemma for disjoint pairs. We also determine the typical structure of k-uniform set families without matchings of size s when n≥2sk+38s4, and show that almost all k-uniform intersecting families on vertex set [n] are trivial when n≥(2+o(1))k.
en_US
dc.format
application/pdf
dc.language.iso
en
en_US
dc.publisher
Electronic Journal of Combinatorics
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.title
Structure and supersaturation for intersecting families
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2019-05-31
ethz.journal.title
The Electronic Journal of Combinatorics
ethz.journal.volume
26
en_US
ethz.journal.issue
2
en_US
ethz.journal.abbreviated
J. comb.
ethz.pages.start
P2.34
en_US
ethz.size
38 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.wos
ethz.publication.place
Clemson, SC
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
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
ethz.date.deposited
2019-06-19T02:13:08Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-06-19T09:27:00Z
ethz.rosetta.lastUpdated
2022-03-28T23:07:09Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Structure%20and%20supersaturation%20for%20intersecting%20families&rft.jtitle=The%20Electronic%20Journal%20of%20Combinatorics&rft.date=2019-05-31&rft.volume=26&rft.issue=2&rft.spage=P2.34&rft.issn=1097-1440&1077-8926&rft.au=Balogh,%20J%C3%B3zsef&Das,%20Shagnik&Liu,%20Hong&Sharifzadeh,%20Maryam&Tran,%20Tuan&rft.genre=article&rft_id=info:doi/10.37236/7683&
Files in this item
Publication type
-
Journal Article [133584]