Abstract
Let $F$ be a strictly $k$-balanced $k$-uniform hypergraph with $e(F)\geq |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 hyperedges of the complete $k$-uniform hypergraph $K_n^k$ on $n$ vertices.
Start with the empty hypergraph on $n$ vertices. Successively consider the hyperedges $e$ of $K_n^k$ 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 $\tilde{O}(n^{k-(|F|-k)/(e(F)-1)})$ hyperedges. This is best possible up to logarithmic factors.
The random greedy $F$-free process constructs a maximal $F$-free hypergraph as follows.
Consider a random ordering of the hyperedges of the complete $k$-uniform hypergraph $K_n^k$ on $n$ vertices.
Start with the empty hypergraph on $n$ vertices. Successively consider the hyperedges $e$ of $K_n^k$ 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 $\tilde{O}(n^{k-(|F|-k)/(e(F)-1)})$ hyperedges. This is best possible up to logarithmic factors.
| Original language | English |
|---|---|
| Pages (from-to) | 1343-1350 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 30 |
| Issue number | 3 |
| Early online date | 12 Jul 2016 |
| DOIs | |
| Publication status | Published - 2016 |
Fingerprint
Dive into the research topics of 'On the random greedy F-free hypergraph process'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver