Maximum Hitting for n Sufficiently Large

Ben Barber

doi:10.1007/s00373-012-1281-9

Maximum Hitting for n Sufficiently Large

Ben Barber

Research output: Contribution to journal › Article (Academic Journal) › peer-review

2 Citations (Scopus)

308 Downloads (Pure)

Abstract

For a left-compressed intersecting family A⊆[n]^(r) and a set X⊆[n] , let A(X)={A∈A:A∩X≠∅} . 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.

Original language	English
Pages (from-to)	267-274
Number of pages	8
Journal	Graphs and Combinatorics
Volume	30
Issue number	2
Early online date	16 Jan 2013
DOIs	https://doi.org/10.1007/s00373-012-1281-9
Publication status	Published - Mar 2014

Keywords

Intersecting family
Compression
Generating set
Erdős–Ko–Rado theorem

Access to Document

10.1007/s00373-012-1281-9

Full-text PDF (accepted author manuscript)
This is the accepted author manuscript (AAM). The final published version (version of record) is available online via Springer Verlag at http://dx.doi.org/10.1007/s00373-012-1281-9. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 123 KB

Handle.net

Persistent link

Cite this

@article{94faaf34d2254d1cb9f392a56efa36b5,

title = "Maximum Hitting for n Sufficiently Large",

abstract = "For a left-compressed intersecting family A⊆[n](r) and a set X⊆[n] , let A(X)=\{A∈A:A∩X≠∅\} . 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.",

keywords = "Intersecting family, Compression, Generating set, Erd{\H o}s–Ko–Rado theorem",

author = "Ben Barber",

year = "2014",

month = mar,

doi = "10.1007/s00373-012-1281-9",

language = "English",

volume = "30",

pages = "267--274",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "2",

}

TY - JOUR

T1 - Maximum Hitting for n Sufficiently Large

AU - Barber, Ben

PY - 2014/3

Y1 - 2014/3

N2 - For a left-compressed intersecting family A⊆[n](r) and a set X⊆[n] , let A(X)={A∈A:A∩X≠∅} . 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.

AB - For a left-compressed intersecting family A⊆[n](r) and a set X⊆[n] , let A(X)={A∈A:A∩X≠∅} . 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.

KW - Intersecting family

KW - Compression

KW - Generating set

KW - Erdős–Ko–Rado theorem

U2 - 10.1007/s00373-012-1281-9

DO - 10.1007/s00373-012-1281-9

M3 - Article (Academic Journal)

SN - 0911-0119

VL - 30

SP - 267

EP - 274

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 2

ER -

Maximum Hitting for n Sufficiently Large

Abstract

Keywords

Access to Document

Handle.net

Fingerprint

Cite this