Sharp Concentration of Hitting Size for Random Set Systems

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

*Corresponding author for this work

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)639-648
Number of pages10
JournalGraphs and Combinatorics
Volume31
Issue number3
DOIs
StatePublished - May 1 2015

Keywords

  • Hitting set
  • Probabilistic method
  • Random set system

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Sharp Concentration of Hitting Size for Random Set Systems'. Together they form a unique fingerprint.

  • Cite this