Maximum hitting for n sufficiently large

DOI10.1007/S00373-012-1281-9zbMATH Open1298.05311arXiv1203.4188OpenAlexW3099179426MaRDI QIDQ742567FDOQ742567

Authors: Ben Barber 

Publication date: 19 September 2014

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: For a left-compressed intersecting family A contained in [n]^(r) and a set X contained in [n], let A(X) = {A in A : A intersect X is non-empty}. Borg asked: for which X is |A(X)| maximised by taking A to be all r-sets containing the element 1? We determine exactly which X have this property, for n sufficiently large depending on r.

Full work available at URL: https://arxiv.org/abs/1203.4188

Recommendations

• Classification of maximum hittings by large families
• Compressions and probably intersecting families
• Maximum hitting of a set by compressed intersecting families
• On the maximum number of distinct intersections in an intersecting family
• EKR sets for large \(n\) and \(r\)

zbMATH Keywords

compressionintersecting familygenerating setErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• Title not available (Why is that?)
• Maximum hitting of a set by compressed intersecting families

Cited In (5)

• Compressions and probably intersecting families
• EKR sets for large \(n\) and \(r\)
• Maximum hitting of a set by compressed intersecting families
• Characterizing maximal shifted intersecting set systems and short injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
• Classification of maximum hittings by large families

This page was built for publication: Maximum hitting for \(n\) sufficiently large

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742567)