Cores in random hypergraphs and Boolean formulas

DOI10.1002/rsa.20061zbMath1068.05063OpenAlexW4243384247MaRDI QIDQ5311914

No author found.

Publication date: 29 August 2005

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1807/9523

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Combinatorial probability (60C05)

Related Items (46)

Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Sharp load thresholds for cuckoo hashing ⋮ Maximum matchings in random bipartite graphs and the space utilization of Cuckoo Hash tables ⋮ Satisfiability Thresholds beyond k −XORSAT ⋮ How does the core sit inside the mantle? ⋮ On the phase transition in random simplicial complexes ⋮ Sandwiching a densest subgraph by consecutive cores ⋮ Small cores in 3-uniform hypergraphs ⋮ Sets that are connected in two random graphs ⋮ Load Thresholds for Cuckoo Hashing with Overlapping Blocks ⋮ Minimal and Monotone Minimal Perfect Hash Functions ⋮ Xor Filters ⋮ Singularity of the \(k\)-core of a random graph ⋮ Load Thresholds for Cuckoo Hashing with Overlapping Blocks ⋮ Phase transition in count approximation by count-min sketch with conservative updates ⋮ Abelian groups from random hypergraphs ⋮ A central limit theorem for diffusion in sparse random graphs ⋮ On Random Betweenness Constraints ⋮ Random Simplicial Complexes: Around the Phase Transition ⋮ The Satisfiability Threshold fork-XORSAT ⋮ The Multiple-Orientability Thresholds for Random Hypergraphs ⋮ Cores of random \(r\)-partite hypergraphs ⋮ Asymptotic normality of the \(k\)-core in random graphs ⋮ \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph ⋮ Birth of a giant \((k_{1},k_{2})\)-core in the random digraph ⋮ Finite size scaling for the core of large random hypergraphs ⋮ Coloring graphs from random lists of fixed size ⋮ The satisfiability threshold for random linear equations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Stripping Process Can be Slow: Part II ⋮ The threshold for d-collapsibility in random complexes* ⋮ Thek-Core and Branching Processes ⋮ On the robustness of random \(k\)-cores ⋮ Largest Components in Random Hypergraphs ⋮ Minors of a random binary matroid ⋮ The set of solutions of random XORSAT formulae ⋮ Core forging and local limit theorems for the \(k\)-core of random graphs ⋮ The solution space geometry of random linear equations ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ On the rank of a random binary matrix ⋮ Loose cores and cycles in random hypergraphs ⋮ Unnamed Item ⋮ The rank of sparse random matrices ⋮ Walksat Stalls Well Below Satisfiability ⋮ Cores of random graphs are born Hamiltonian

Cites Work

• Unnamed Item
• Unnamed Item
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• A sharp threshold in proof complexity

This page was built for publication: Cores in random hypergraphs and Boolean formulas