Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-22T05:57:32.890Z Has data issue: false hasContentIssue false
  • English
  • Français

Deterministic Graph Games and a Probabilistic Intuition

Published online by Cambridge University Press:  12 September 2008

József Beck
József Beck
Affiliation:
Department of Mathematics, Rutgers University, Busch Campus, Hill Center, New Brunswick, New Jersey 08903U.S.A. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

There is a close relationship between biased graph games and random graph processes. In this paper, we develop the analogy and give further interesting instances.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 1 , March 1994 , pp. 13 - 26
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Beck, J. (1981) Van der Waerden and Ramsey type games. Combinatorica 2 103–116.CrossRefGoogle Scholar
[2]Beck, J. (1982) Remarks on positional games – Part I. Ada Math. Acad. Sci. Hungarica 40 65–71.CrossRefGoogle Scholar
[3]Beck, J. (1985) Random graphs and positional games on the complete graph. Annals of Discrete Math. 28 7–13.Google Scholar
[4]Bollobás, B. (1982) Long paths in sparse random graphs. Combinatorica 2 223–228.CrossRefGoogle Scholar
[5]Bollobás, B. (1985) Random Graphs, Academic Press, London 447ff.Google Scholar
[6]Chvátal, V. and Erdős, P. (1978) Biased positional games. Annals of Discrete Math. 2 221–228.CrossRefGoogle Scholar
[7]Chvátal, V., Rödl, V., Szemerédi, E. and Trotter, W. T. (1983) The Ramsey number of a graph with bounded maximum degree. Journal of Combinatorial Theory Series B 34 239–243.CrossRefGoogle Scholar
[8]Erdős, P. and Selfridge, J. (1973) On a combinatorial game. Journal of Combinatorial Theory Series A 14 298–301.CrossRefGoogle Scholar
[9]Friedman, J. and Pippenger, N. (1987) Expanding graphs contain all small trees. Combinatorica 7 71–76.CrossRefGoogle Scholar
[10]Komlós, J. and Szemerédi, E. (1973) Hamilton cycles in random graphs, Proc. of the Combinatorial Colloquium in Keszthely, Hungary, 1003–1010.Google Scholar
[11]Pósa, L. (1976) Hamilton circuits in random graphs. Discrete Math. 14 359–64.CrossRefGoogle Scholar
[12]Székely, L. A. (1981) On two concepts of discrepancy in a class of combinatorial games. Colloq. Math. Soc. János Bolyai 37 “Finite and Infinite Sets” Eger, Hungary. North-Holland, 679–683.Google Scholar