Sharp Concentration of Hitting Size for Random Set Systems

Jessie D. Jamieson; Anant Godbole; William Jamieson; Lucia Catherine Petito

doi:10.1007/s00373-014-1405-5

Sharp Concentration of Hitting Size for Random Set Systems

Jessie D. Jamieson, Anant Godbole^*, William Jamieson, Lucia Catherine Petito

^*Corresponding author for this work

Preventive Medicine

Research output: Contribution to journal › Article › peer-review

Abstract

Consider the random set system (Formula presented.), where (Formula presented.) and Ajselected with probabilityp=pn}. A set H⊆[n] is said to be a hitting set for (Formula presented.). The second moment method is used to exhibit the sharp concentration of the minimal size of H for a variety of values of p.

Original language	English (US)
Pages (from-to)	639-648
Number of pages	10
Journal	Graphs and Combinatorics
Volume	31
Issue number	3
DOIs	https://doi.org/10.1007/s00373-014-1405-5
State	Published - May 1 2015

Keywords

Hitting set
Probabilistic method
Random set system

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-014-1405-5

Cite this

@article{41e77fbb9cf04f709cba0ad33979571f,

title = "Sharp Concentration of Hitting Size for Random Set Systems",

abstract = "Consider the random set system (Formula presented.), where (Formula presented.) and Ajselected with probabilityp=pn}. A set H⊆[n] is said to be a hitting set for (Formula presented.). The second moment method is used to exhibit the sharp concentration of the minimal size of H for a variety of values of p.",

keywords = "Hitting set, Probabilistic method, Random set system",

author = "{D. Jamieson}, Jessie and Anant Godbole and William Jamieson and Petito, {Lucia Catherine}",

note = "Funding Information: The research of all the authors was supported by NSF Grant 1004624. We thank the referee, whose suggestions have greatly improved and streamlined the paper. Publisher Copyright: {\textcopyright} 2014, Springer Japan.",

year = "2015",

month = may,

day = "1",

doi = "10.1007/s00373-014-1405-5",

language = "English (US)",

volume = "31",

pages = "639--648",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - Sharp Concentration of Hitting Size for Random Set Systems

AU - D. Jamieson, Jessie

AU - Godbole, Anant

AU - Jamieson, William

AU - Petito, Lucia Catherine

N1 - Funding Information: The research of all the authors was supported by NSF Grant 1004624. We thank the referee, whose suggestions have greatly improved and streamlined the paper. Publisher Copyright: © 2014, Springer Japan.

PY - 2015/5/1

Y1 - 2015/5/1

N2 - Consider the random set system (Formula presented.), where (Formula presented.) and Ajselected with probabilityp=pn}. A set H⊆[n] is said to be a hitting set for (Formula presented.). The second moment method is used to exhibit the sharp concentration of the minimal size of H for a variety of values of p.

AB - Consider the random set system (Formula presented.), where (Formula presented.) and Ajselected with probabilityp=pn}. A set H⊆[n] is said to be a hitting set for (Formula presented.). The second moment method is used to exhibit the sharp concentration of the minimal size of H for a variety of values of p.

KW - Hitting set

KW - Probabilistic method

KW - Random set system

UR - http://www.scopus.com/inward/record.url?scp=84896059236&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84896059236&partnerID=8YFLogxK

U2 - 10.1007/s00373-014-1405-5

DO - 10.1007/s00373-014-1405-5

M3 - Article

AN - SCOPUS:84896059236

SN - 0911-0119

VL - 31

SP - 639

EP - 648

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

Sharp Concentration of Hitting Size for Random Set Systems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this