On the random greedy F-free hypergraph process

DOI10.1016/J.ENDM.2015.06.012zbMATH Open1346.05202arXiv1502.00486OpenAlexW2963081352MaRDI QIDQ322193FDOQ322193

Authors: Daniela Kühn, Deryk Osthus, Amelia Taylor 

Publication date: 14 October 2016

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 $ildeO(n^{k-(|F|-k)/(e(F)-1)})$ hyperedges. This is best possible up to logarithmic factors.

Full work available at URL: https://arxiv.org/abs/1502.00486

Recommendations

• On the random greedy \(F\)-free hypergraph process
• scientific article; zbMATH DE number 434917
• scientific article; zbMATH DE number 1890147
• Random hypergraph processes with degree restrictions
• The matching process and independent process in random regular graphs and hypergraphs
• On the structure of random hypergraphs
• On large‐girth regular graphs and random processes on trees
• scientific article; zbMATH DE number 3999977
• Random maximalH-free graphs

zbMATH Keywords

hypergraph\(F\)-free processrandom greedy process

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• The triangle-free process
• Dynamic concentration of the triangle-free process
• Representations of integers as the sum of k terms
• The early evolution of the \(H\)-free process
• Constrainted graph processes
• The diamond-free process
• The Final Size of the $C_{\ell}$-free Process
• On the size of a random maximal graph
• Random maximalH-free graphs
• When does the \(K_{4}\)-free process stop?
• The C_ℓ‐free process

Cited In (10)

• The Final Size of the $C_{\ell}$-free Process
• On the random greedy linear uniform hypergraph packing
• Random maximalH-free graphs
• Title not available (Why is that?)
• On the random greedy \(F\)-free hypergraph process
• Random hypergraph processes with degree restrictions
• A note on the random greedy independent set algorithm
• On the maximum \(F_5\)-free subhypergraphs of a random hypergraph
• The reverse \(H\)-free process for strictly 2-balanced graphs
• The random \(k\)-matching-free process

This page was built for publication: On the random greedy \(F\)-free hypergraph process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322193)