___

Andrzej Ruciński

Published papers

1981-84

  1. The r-connectedness of k-partite random graphs, Bull.de l'Acad. Pol. des Sci., 29/7-8 (1981) 321-330.
  2. Matchings and k-factors in a random graph, Studia Sci.Math.Hung. 17(1982) 335-340.
  3. On the number of strictly balanced subgraphs of a random graph (with M.Karo\'nski), Graph Theory, Lag\'ow 1981. Lectures Notes in Mathematics, 1018 (1983) 79-83.
  4. The behaviour of $\binom{n}{k,...,k,n-ik}c^i/i!$ is asymptotically normal, Discrete Mathematics 49 (1984) 287-290.

    5. 1985

  5. Subgraphs of random graphs: a general approach, Random Graphs'83, Annals of Discrete Math. 28(1985) 221-229.
  6. Every graph is contained in a sparsest possible balanced graph (with E.Gy\H ori and B.Rothschild), Math.Proc.Cambr.Phil.Soc. 98(1985) 397-401.
  7. Balanced graphs and the problem of subgraphs of a random graph with A.Vince),  Proc.16th Southeastern Conf. on Comb. Graph Th. and Comp., Congressus Numerantium 49 (1985) 181-190.

    8. 1986

  8. Random graphs of binomial type with sparsely edged initial graphs, Acta Math.Hung. 47(1986) 81-87.
  9. Strongly balanced graphs and random graphs (with A.Vince), J.Graph Theory 10(1986) 251-264.
  10. On a method for random graphs (with Z.Palka and J.Spencer), Discr.Math. 61(1986), 253-258.
  11. On the order of the largest induced tree in a random graph (with Z.Palka), Discr. Appl. Math. 15(1986) 75-83.

    12. 1987

  12. Poisson convergence and semi-induced properties of random graphs ( with M.Karo\'n\-ski ), Math.Proc.Cambr.Phil.Soc. 101(1987), 291-300.
  13. Induced subgraphs of a random graph, Annals Discr.Math. 33(1987) 275-296.

    14. 1988

  14. Balanced extensions of graphs and hypergraphs (with A.Vince),  Combinatorica 8 (3) (1988) 279-291.
  15. When are small subgraphs of a random graph normally distributed? Prob.Theory and Related Fields 78(1988) 1-10.
  16. Enumeration of the ``up-and-down" labellings of a cycle, Graph Theory Notes of New York, The New York Academy of Sciences XVI (1988) 20-22.

    17. 1989

  17. Small subgraphs of k-partite random graphs (with M.Karo\'nski),  Annals of the New York Acad. of Sci., 555(1989), 230-240.
  18. Balanced extensions of graphs (with A.Vince), Annals of the New York Acad.of Sci., 555(1989), 347-351.
  19. A central limit theorem for decomposable random variables with applications to random graphs (with A.Barbour and M.Karo\'nski),  JCT-B, 47 (2)(1989) 125-145.

    20. 1990

  20. A local theorem for generalized Stirling numbers (with B.Voigt), Rev. Roum. Math., 35(1990) 161-172.
  21. An exponential bound for the probability of nonexistence of a specified subgraph in a random graph (with S.Janson and T.\L uczak), Random Graphs, Karonski et al., eds, 1990 Wiley 73-88.
  22. Small subgraphs of random graphs-a survey, Random Graphs, Karonski et al., eds, 1990 Wiley 283-303
  23. Small cliques in random graphs (with A.Barbour, S.Janson and M.Karo\'nski), Random Structures \& Algorithms., 1(1990)(4) 403-434.
  24. Maximal graphs with bounded maximum degree: structure, asymptoticenumeration, randomness, Proceedings III of 7th Fischland Colloquium, Rostock. Math. Kolloq. 41(1990) 47-58.
  25. Vertex degrees in a random subgraphs of a regular graph (with Z.Palka), Studia Sci.Math.Hung. 25 (1990) 209-214.

    26. 1991

  26. From random graphs to graph theory: Ramsey properties (extended abstract) Graph Theory Notes of New York  XX (1991) 8-16
  27. Tree-matchings in random graph processes (with T.\L uczak), SIAM J.Discr.Math. 4 (1991) 107-120.
  28. On convex hulls of graphs,  Ars Combinatoria 32 (1991) 293-300.

    29. 1992

  29. Proving normality in combinatorics Random Graphs, A.Frieze and T.Luczak, eds, 1992 Wiley 215-231.
  30. Convex hulls of dense balanced graphs (with T.\L uczak) J. of Comput. Appl. Math. 41 (1992) 205-213.
  31. Balanced extensions of sparse graphs (with T.\L uczak), IV Czechoslovakian Symp. on Combinatorics, Graphs and Complexity, J.Nesetril and M.Fiedler, eds.,1992 Elsevier Science Publ. 191-203.
  32. Matching and covering the vertices of a random graph by copies of a given graph, Discrete Mathematics 105 (1992) 185-197.
  33. Ramsey properties of random graphs (with T.\L uczak and B.Voigt), JCT-B. 56 (1992) 55-68.
  34. Random graph processes with degree restrictions (with N. Wormald) Combinatorics, Probability and Computing 1 (1992) 169-180.

    35. 1993

  35. From random graphs to graph theory (survey paper) Quo Vadis, Graph Theory?, Annals of Discrete Mathematics 55 (1993) 265-274
  36. The solution to an extremal problem on balanced extensions of graphs (with A.Vince)  JGT 17 (1993) 417-431.
  37. Lower bounds on probability thresholds for Ramsey properties (with V. R\"odl) Combinatorics, Paul Erd\H os is Eighty, Vol.1, Bolyai Soc. Math. Studies, (1993), 317-346.

    38. 1994

  38. Globally sparse vertex-Ramsey graphs (with A.Kurek)  J.Graph Theory 18 (1994), 73-81.
  39. Random graphs with monochromatic triangles in every edge coloring (with V. R\"odl) Random Structures Algorithms 5(2) (1994), 253-270.
  40. On random graphs (with Z. Palka) Wiadomosci Matematyczne XXX, (1994) 175-197. (In Polish).

    41. 1995

  41. Threshold functions for Ramsey properties (with V.R\"odl)  J. Americ. Mathem. Soc 8(4) 1995, 917-942. pdf

    42. 1996

  42. On the evolution of a random tournament (with T.\L uczak and J. Gruszka) Discrete Mathematics 148 (1996) 311-316.
  43. Recent developments in random graphs, 35 pages, Proceedings of the International Summer School on Probability and Statistics, Varna 1994 pdf
  44. On Schur properties of random subsets of integers (with R. Graham and V. R\"odl) Journal of Number Theory, 61(2) (1996) 388-408 pdf

    45. 1997

  45. The origins of the theory of random graphs (with M. Karonski) in: Mathematics of Paul Erd\H os; Graham, Ne\v set\v ril, eds., Springer, 1997, 311-336. pdf
  46. A note on local colorings of graphs (with M. Truszczynski) Discrete Mathematics [ Proceedings of Graph Theory, Zakopane 1994; eds. P. Wojda, M. Wo\'zniak; Discrete Mathematics] 164 1-3 (1997) 251-255. pdf
  47. Rado partition theorem for random subsets of integers (with V. R\"odl) Proceedings of the London Mathematical Society 74(3) (1997) 481-502. pdf
  48. Bipartite coverings of graphs (with V. R\"odl) Combinatorics, Probability and Computing 6(3) (1997) 349-353. pdf
  49. Random graph processes with maximum degree 2 (with N. Wormald) The Annals of Applied Probability 7(1) (1997) 183-199 pdf

    50. 1998

  50. Endomorphisms of partially ordered sets (with D.Duffus, T.\L uczak and V.R\"odl) Combinatorics, Probability and Computing 7 (1998) 1-14 pdf
  51. Ramsey properties of random hypergraphs (with V. R\"odl) Journal Combin. Theory, Series A 81 (1998) 1-33 pdf
  52. Perfect matchings in $\epsilon$-regular graphs (with N. Alon and V. R\"odl) The Electr. J. of Combin. 5(1) (1998) #R13 pdf
  53. An algorithmic embedding of graphs via perfect matchings (extended abstract) (with V. R\"odl and M.Wagner) Randomization and Approximation Techniques in Computer Science (M. Luby, J. Rolim, and M. Serna, eds.) -- Proc. Second Inter. Workshop RANDOM'98, Barcelona, Spain, October, 1998, LNCS, vol. ~ 1518 (1998), 25-34, Springer, Berlin. pdf

    54. 1999

  54. Perfect matching in $\epsilon$-regular graphs and the Blow-up Lemma (with V. R\"odl) Combinatorica 19 (3) (1999) 437-452 pdf
  55. Hypergraph packing and graph embedding (with V. R\"odl and A. Taraz) Combinatorics, Probability and Computing 8 (1999) 363-376. pdf

    56. 2000

  56. Solitary subgraphs of random graphs (with J. Kurkowiak) Discrete Mathematics 213 (2000) 195-209 pdf
  57. UNIVERSALITY AND TOLERANCE (Extended Abstract) (with N. Alon, M. Capalbo, Y. Kohayakawa V. R\"odl and E. Szemer\'edi) In Proceedings of the 41st IEEE Annual Symposium on FOCS 14-21, (2000) pdf
  58. On graphs with linear ramsey numbers (with R. Graham and V. R\"odl) J. Graph Theory 35 (2000) 176-192 pdf

    59. 2001

  59. On minimal vertex-Folkman graphs (with T. \L uczak and S. Urba\'nski) Discrete Mathematics 236 (1-3) (2001) 245-262 pdf
  60. On bipartite graphs with linear ramsey numbers (with R. Graham and V. R\"odl) Combinatorica 21 (2) (2001) 199-209 pdf
  61. Near-optimum universal graphs for graphs with bounded degrees (Extended Abstract) (with N. Alon, M. Capalbo, Y. Kohayakawa V. R\"odl and E. Szemer\'edi) APPROX-RANDOM 2001, LNCS 3139 (2001) 170-180 pdf

    62. 2002

  62. Holes in graphs (with Y. Peng and V. R\"odl)The Electr. J. of Combin. 9(1) (2002) #R1 pdf
  63. Matchings Meeting Quotas and Their Impact on the Blow-up Lemma (with V. R\"odl and M.Wagner) SIAM J. of Computing, 31(2) (2001*) 428-446 pdf

    * According to SIAM new policy, the year of publication is the year of electronic publication, and not the year of the print issue.

  64. Connectedness of graphs generated by a random $d$-process (with N. Wormald) Australian J. Math.72(1) (2002) 67-85 pdf
  65. The infamous upper tail (with S. Janson), Random Structures Algorithms 20(3) (2002) pdf
  66. Janson inequality Suplement III, Encyclopedia of Mathematics, ed: M. Hazewinkel Kluwer Academic Publisher (2002) 216-218 pdf
  67. Vertex-Ramsey properties of families of graphs (with T. \L uczak and S. Urba\'nski) JCT B 84 (2002) 240-248 pdf
  68. Ramsey properties of families of graphs (with R.L.Graham, T.{\L}uczak, V.R{\"o}dl, A.Ruci\'{n}ski) JCT B 86 (2002) 413-419 pdf

    69. 2003

  69. Connectedness of the degree bounded star process (with C. Greenhill and N. Wormald) Combinatorics Probability and Computing 12 (2003) 269-283 pdf
  70. Ramsey games against a one-armed bandit (with E.Friedgut, Y. Kohayakawa, V. Rödl and P. Tetali) Combinatorics, Probability and Computing12 (2003) 515-545 pdf

    71. 2004

  71. Random hypergraph processes with degree restrictions (with C. Greenhill and N. Wormald) Graphs and Combinatorics20 (2004), issue 3, 319-332 pdf
  72. The deletion method for upper tails (with S. Janson) Combinatorica 24/4 (2004) 615-640 pdf
  73. Upper tails for subgraph counts in random graphs(with S. Janson and K. Oleszkiewicz) Israel J. Math.142 (2004) 61-92 pdf

    74. 2005

  74. Two variants of the size Ramsey number (with A. Kurek) Discuss. Math. Graph Th. 25 (2005) 141-149 pdf
  75. Planar Ramsey number for small graphs(with A. Dudek) Congr. Numer.(Boca Raton)pdf
  76. The generalization of Dirac's theorem for hypergraphs (with V. R\"odl and E. Szemerédi) Proceedings of the 30th International Symposium MFCS, Gda\'nsk 2005 Springer-Verlag, LNCS 3618, (2005) 52-56 pdf

    77. 2006

  77. A sharp threshold for random graphs with a monochromatic triangle in every edge coloring (with E. Friedgut, V. Rödl and P. Tetali) Memoirs of the AMS, Vol. 179, No. 845, January 2006, 66 pages pdf
  78. The Ramsey number for hypergraph cycles I (with P. Haxell, T. \L uczak, Y. Peng, V. Rödl, M. Simonovits, J. Skokan) JCT A, 113(2006) 67-83 pdf
  79. A Dirac-type theorem for 3-uniform hypergraphs (with V. Rödl and E. Szemerédi) Combinatorics, Probability and Computing pdf
  80. Short Paths in Quasi-Random Triple Systems with Sparse Underlying Graphs (with J. Polcyn, V. Rödl and E. Szemerédi)JCT B 96 (2006) 584-607 pdf
  81. Neighbour-distinguishing edge colorings of random regular graphs (with C. Greenhill) The Electr. J. Combin. 13(1) (2006) pdf
  82. Perfect matchings in uniform hypergraphs with large minimum degree (with V. Rödl and E. Szemerédi) Europ. J. Combin., special volume (Sudakov) 27 (2006) 1333-1349 pdf

    83. 2007

  83. Ramsey properties of random $k$-partite, $k$-uniform hypergraphs (with V. Rödl and M. Schacht) SIAM J. of Discrete Math. 21(2) (2007) 442-460 pdf

    84. 2008

  84. An approximate Dirac theorem for $k$-uniform hypergraphs (with V. R\"odl and E. Szemer\'edi) Combinatorica 28(2) (2008) 229-260.pdf
  85. Universality of random graphs (with D. Dellamonica, Jr., Y. Kohayakawa and V. R\"odl) Proceedings of the nineteenth annual ACM-SIAM Symposium on Discrete Algorithms San Francisco, CA - 2008 (2008) 782--788. pdf
  86. Planar Ramsey numbers for cycles (with I. Gorgol) Discrete Mathematics 308 (2008) 4389-4395 pdf
  87. A note on perfect matchings in uniform hypergraphs with large minimum collective degree (with V. R\"odl, M. Schacht and E. Szemeredi) Commentationes Mathematicae Universitatis Carolinae 49,4 (2008) 633-636. ps

    88. 2009

  88. The Ramsey number for 3-uniform tight hypergraph cycles(with P. Haxell, T. \L uczak, Y. Peng, V. R\"odl, J. Skokan)CPC18 (2009), 165-204. pdf
  89. Perfect matchings in large uniform hypergraphs with large minimum collective degree(with V. R\"odl and E. Szemer\'edi) JCT A 116(3) (2009) 613-636. pdf

Papers in print

  1. Subhypergraph counts in extremal and random hypergraphs and the fractional q-independence (with A. Dudek and J. Polcyn) Journal of Combinatorial Optimization DOI10.1007/s10878-008-9174-9, Published online: 17 July 2008 pdf
  2. Short paths in $\epsilon$-regular pairs and small diameter decompositions of dense graphs (with J. Polcyn) Discrete Mathematics pdf

Submitted papers

  1. The Complexity of Perfect Matching Problems on Dense Hypergraphs (with M. Karpinski, E. Szymanska) pdf
    2. (expanded version)

Books

  1. Random Graphs'83, North-Holland, 1985, Annals of Discrete Mathematics 28, 363+viii pages (M. Karo\'nski and A. Ruci\'nski, eds.)
  2. Random Graphs, Wiley, 1990, 368+viii pages (M. Karo\'nski, J. Jaworski and A. Ruci\'nski, eds.)
  3. On Nondeterministic Methods In Discrete Mathematics (with Z. Palka), Wydawnictwo Naukowo-Techniczne, Warszawa 1996, 120 pages (in Polish).
  4. Enumerative Combinatorics (with Z. Palka), Wydawnictwo Naukowo-Techniczne, Warszawa 1998, 200 pages (in Polish).
  5. Random Graphs (with S. Janson and T. \L uczak), monograph, Wiley, 2000, xii+333 pages.