Using Lovász local lemma in the space of random injections

zbMath1183.05088MaRDI QIDQ1010623

László A. Székely, Linyuan Lu

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/117186

zbMATH Keywords

dependency graphpermutation enumerationhzpergraph packingLovasz local lemmanegative dependency graphrandom injectionsTuran-type extremal problems

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Asymptotic enumeration (05A16) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

Counting sparse \(k\)-edge-connected hypergraphs with given number of vertices and edges, Equitable colorings of nonuniform hypergraphs, Bounded colorings of multipartite graphs and hypergraphs, Independent sets in hypergraphs omitting an intersection, Long directed rainbow cycles and rainbow spanning trees, How Many Conflicts Does It Need to Be Unsatisfiable?, Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree, Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles, Unnamed Item, Recent advances on the Hamiltonian problem: survey III, A rainbow blow‐up lemma, Equitable two-colorings of uniform hypergraphs, Properly colored and rainbow copies of graphs with few cherries, The component counts of random injections, Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles, Equitable colorings of hypergraphs with few edges, The Lovász Local Lemma and Satisfiability, Comparison of two convergence criteria for the variable-assignment Lopsided Lovász Local Lemma