On the random greedy F-free hypergraph process

Daniela Kühn, Deryk Osthus, Amelia Taylor

Research output: Contribution to journalArticlepeer-review

141 Downloads (Pure)

Abstract

Let F be a strictly k-balanced k-uniform hypergraph with e(F) ≥ |F|- k+ 1 and maximum co-degree at least two. The random greedy F-free process constructs a maximal F-free hypergraph as follows. Consider a random ordering of the hyper-edges of the complete k-uniform hypergraph Kk n on n vertices. Start with the empty hypergraph on n vertices. Successively consider the hyperedges e of Kk n in the given ordering and add e to the existing hypergraph provided that e does not create a copy of F. We show that asymptotically almost surely this process terminates at a hypergraph with Õ(nk-(|F|-k)/(e(F)-1)) hyperedges. This is best possible up to logarithmic factors.

Original languageEnglish
Pages (from-to)73-77
Number of pages5
JournalElectronic Notes in Discrete Mathematics
Volume49
Early online date12 Nov 2015
DOIs
Publication statusPublished - Nov 2015

Keywords

  • F-free process
  • Hypergraph
  • Random greedy

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the random greedy F-free hypergraph process'. Together they form a unique fingerprint.

Cite this