Classification of Maximum Hittings by Large Families

Candida Bowtell, Richard Mycroft

Research output: Contribution to journalArticlepeer-review

Abstract

For integers $r$ and $n$, where $n$ is sufficiently large, and for every set $X \subseteq [n]$ we determine the maximal left-compressed intersecting families $A \subseteq \binom{[n]}{r}$ which achieve maximum hitting with $X$ (i.e. have the most members which intersect $X$). This answers a question of Barber, who extended previous results by Borg to characterise those sets $X$ for which maximum hitting is achieved by the star.

Original languageEnglish
Pages (from-to)27-39
Number of pages13
JournalGraphs and Combinatorics
Volume36
DOIs
Publication statusPublished - 16 Nov 2019

Keywords

  • Compressions
  • Intersecting families
  • Set systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Classification of Maximum Hittings by Large Families'. Together they form a unique fingerprint.

Cite this