The probabilistic method

ABSTRACT

The use of randomness is now an accepted tool in Theoretical Computer Science but not everyone is aware of the underpinnings of this methodology in Combinatorics - particularly, in what is now called the probabilistic Method as developed primarily by Paul Erdo&huml;s over the past half century. Here I will explore a particular set of problems - all dealing with “good” colorings of an underlying set of points relative to a given family of sets. A central point will be the evolution of these problems from the purely existential proofs of Erdo&huml;s to the algorithmic aspects of much interest to this audience.

REFERENCES

• 1: N. Alon, A Parallel Algorithmic Version of the Local Lemma, Random Structures g; Algorithms 2 (1991), pp 367-378
• 2: N. Alon, J. Spencer, The Probabilistic Method, John Wiley, New York, 1991
• 3: J. Beck, On 3-chromatic hypergraphs, Discrete Math 24 (1978), pp 127-137
• 4: J. Beck, An Algorithmic Approach to the Lovdsz Local Lemma, L, Random Structures g; Algorithms 2 (1991), pp 343-366
• 5: P. Erdfis, On a Combinatorial Problem, L, Nordist. Mat. Tidskr. 11 (1963), pp 5-10
• 6: P. Erd6s, On a combinatorial problem, II, Acts. Math. Hungar. 15 (1964), pp 445-447
• 7: P. Erd6s, L. Lov&sz, Problems and results on 3- chromatic hypergraphs and some related questions, in Infinite and Finite Sets, North-Holland, Amsterdam- New York, 1975
• 8: P. ErdSs and J. Selfridge, On a combinatorial game, J. Combinatorial Theory (Ser. A) 14 (1973), pp 298-301
• 9: Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, Journal of Computer and System Sciences, v.37 n.2, p.130-143, October 1988 [doi>10.1016/0022-0000(88)90003-7]
• 10: J. Spencer, Ten Lectures on the Probabilistic Method, SIAM, Philadelphia, 1987
• 11: J. Spencer, Six Standard Deviations Sujfice, Trans. Amer. Math. Soc. 289 (1985), pp 679-706
• 12: J Spencer, Balancing vectors in the max norm, Combinatorica, v.6 n.1, p.55-65, 1986 [doi>10.1007/BF02579409]
• 13: P. Tetali, private correspondence

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Theory, Verification