The pure literal rule threshold and cores in random hypergraphs

ABSTRACT

We describe a technique for determining the thresholds for the appearance of cores in random structures. We use it to determine (i) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r-SAT, r ≥ 3, and (ii) the threshold for the appearance of a k-core in a random r-uniform hypergraph for all r, k ≥ 2, r + k > 4.

REFERENCES

• 1: Dimitris Achlioptas , Paul Beame , Michael Molloy, A sharp threshold in proof complexity, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.337-346, July 2001, Hersonissos, Greece [doi>10.1145/380752.380820]
• 2: D. Achlioptas , M. Molloy, The analysis of a list-coloring algorithm on a random graph, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.204, October 19-22, 1997
• 3: K. Azuma. Weighted Sums of Certain Dependent Random Variables. Tokuku Math. Journal 19 (1967), 357--367.
• 4: E. A. Bender and E. R. Canfield, The asymptotic number of labelled graphs with given degree sequences. Journal of Combinatorial Theory (A) 24 (1978), 296--307.
• 5: B. Bollobás. The evolution of sparse graphs. In "Graph Theory and Combinatorics", editor: B. Bollobas, 35--57 (1984).
• 6: B. Bollobás, Martingales, Isoperimetric Inequalities and Random Graphs. Colloq. Math. Soc. Janos Bolyai 52 (1987), 113--139.
• 7: B. Bollobas and G. Brightwell. The width of random graph orders. The Mathematical Scientist 20, 69--90 (1995).
• 8: Andrei Z. Broder , Alan M. Frieze , Eli Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.322-330, January 25-27, 1993, Austin, Texas, United States
• 9: V. Chvatal. Almost All Graphs With 1.44n Edges are 3-Colourable. Random Structures and Algorithms 2 (1991), 11 - 28.
• 10: Vašek Chvátal , Endre Szemerédi, Many hard examples for resolution, Journal of the ACM (JACM), v.35 n.4, p.759-768, Oct. 1988 [doi>10.1145/48014.48016]
• 11: C. Cooper, A. Frieze, M. Molloy and B. Reed. Perfect matchings in random r-regular, s-uniform hypergraphs. Combinatorics, Probability and Computing 5 1--14 (1996).
• 12: P. Erdos and A. Rényi. On the Evolution of Random Graphs. Magayr Tud. Akad. Mat. Kutato Int. Kozl. 5 (1960), 17--61.
• 13: J. Franco Probabilistic analysis of the pure literal heuristic for the satisfiability problem. Annals of Operations Research 1 (1984), 273 - 289.
• 14: Andreas Goerdt , Michael Molloy, Analysis of Edge Deletion Processes on Faulty Random Regular Graphs, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.38-47, April 10-14, 2000
• 15: S. Janson, T. Luczak and A. Ruciñski. Random Graphs. Wiley, New York (2000).
• 16: J. Kim, in preparation.
• 17: Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi, Analysis of random processes via And-Or tree evaluation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.364-373, January 25-27, 1998, San Francisco, California, United States
• 18: Tomasz Łuczak, Size and connectivity of the k-core of a random graph, Discrete Mathematics, v.91 n.1, p.61-68, Aug. 7 1991 [doi>10.1016/0012-365X(91)90162-U]
• 19: B. Majewski, N. Wormald, G. Havas, Z. Czech. A Family of Perfect Hashing Methods. The Computer Journal 39(6), 547--554 (1996).
• 20: M. Mitzenmacher. Tight thresholds for the pure literal rule. Technical Note 1997--011, Digital Systems Research Center, Palo Alto, CA (1997).
• 21: M. Molloy. A gap between the appearance of a k-core and a k-chromatic graph. Random Structures & Algorithms 8, 159 - 160 (1996).
• 22: Boris Pittel , Joel Spencer , Nicholas Wormald, Sudden emergence of a giant k-core in a random graph, Journal of Combinatorial Theory Series B, v.67 n.1, p.111-151, May 1996 [doi>10.1006/jctb.1996.0036]
• 23: J. Plotkin and J. Rosenthal. Probabilistic analysis of the pure literal for the satisfiability problem. Abstracts of the AMS 6 (1995), p. 267.
• 24: J. Rosenthal, J. Plotkin and J. Franco. The probability of pure literals. Journal of Computational Logic 9 (1999), 501 - 513.
• 25: N. C. Wormald. Some Problems in the Enumeration of Labelled Graphs. Doctoral thesis, Newcastle University (1978).