Andrzej Ruciñski

Published papers


  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

  6. Subgraphs of random graphs: a general approach, Random Graphs'83, Annals of Discrete Math. 28(1985) 221-229.
  7. 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.
  8. 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.
  9. 1986

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

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

  18. Balanced extensions of graphs and hypergraphs (with A.Vince),  Combinatorica 8 (3) (1988) 279-291.
  19. When are small subgraphs of a random graph normally distributed? Prob.Theory and Related Fields 78(1988) 1-10.
  20. 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.
  21. 1989

  22. Small subgraphs of k-partite random graphs (with M.Karo\'nski),  Annals of the New York Acad. of Sci., 555(1989), 230-240.
  23. Balanced extensions of graphs (with A.Vince), Annals of the New York Acad.of Sci., 555(1989), 347-351.
  24. 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.
  25. 1990

  26. A local theorem for generalized Stirling numbers (with B.Voigt), Rev. Roum. Math., 35(1990) 161-172.
  27. 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.
  28. Small subgraphs of random graphs-a survey, Random Graphs, Karonski et al., eds, 1990 Wiley 283-303 pdf
  29. Small cliques in random graphs (with A.Barbour, S.Janson and M.Karo\'nski), Random Structures \& Algorithms., 1(1990)(4) 403-434.
  30. Maximal graphs with bounded maximum degree: structure, asymptoticenumeration, randomness, Proceedings III of 7th Fischland Colloquium, Rostock. Math. Kolloq. 41(1990) 47-58. pdf
  31. Vertex degrees in a random subgraphs of a regular graph (with Z.Palka), Studia Sci.Math.Hung. 25 (1990) 209-214.
  32. 1991

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

  37. Proving normality in combinatorics Random Graphs, A.Frieze and T.Luczak, eds, 1992 Wiley 215-231.
  38. Convex hulls of dense balanced graphs (with T.\L uczak) J. of Comput. Appl. Math. 41 (1992) 205-213.
  39. 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.
  40. Matching and covering the vertices of a random graph by copies of a given graph, Discrete Mathematics 105 (1992) 185-197.
  41. Ramsey properties of random graphs (with T.\L uczak and B.Voigt), JCT-B. 56 (1992) 55-68.
  42. Random graph processes with degree restrictions (with N. Wormald) Combinatorics, Probability and Computing 1 (1992) 169-180. pdf
  43. 1993

  44. From random graphs to graph theory (survey paper) Quo Vadis, Graph Theory?, Annals of Discrete Mathematics 55 (1993) 265-274
  45. The solution to an extremal problem on balanced extensions of graphs (with A.Vince)  JGT 17 (1993) 417-431.
  46. 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. pdf
  47. 1994

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

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

  54. On the evolution of a random tournament (with T.\L uczak and J. Gruszka) Discrete Mathematics 148 (1996) 311-316.
  55. Recent developments in random graphs, 35 pages, Proceedings of the International Summer School on Probability and Statistics, Varna 1994 pdf
  56. 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
  57. 1997

  58. 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
  59. 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
  60. Rado partition theorem for random subsets of integers (with V. R\"odl) Proceedings of the London Mathematical Society 74(3) (1997) 481-502. pdf
  61. Bipartite coverings of graphs (with V. R\"odl) Combinatorics, Probability and Computing 6(3) (1997) 349-353. pdf
  62. Random graph processes with maximum degree 2 (with N. Wormald) The Annals of Applied Probability 7(1) (1997) 183-199 pdf
  63. 1998

  64. Endomorphisms of partially ordered sets (with D.Duffus, T.\L uczak and V.R\"odl) Combinatorics, Probability and Computing 7 (1998) 1-14 pdf
  65. Ramsey properties of random hypergraphs (with V. R\"odl) Journal Combin. Theory, Series A 81 (1998) 1-33 pdf
  66. Perfect matchings in $\epsilon$-regular graphs (with N. Alon and V. R\"odl) The Electr. J. of Combin. 5(1) (1998) #R13 pdf
  67. 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
  68. 1999

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

  72. Solitary subgraphs of random graphs (with J. Kurkowiak) Discrete Mathematics 213 (2000) 195-209 pdf
  73. 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
  74. On graphs with linear ramsey numbers (with R. Graham and V. R\"odl) J. Graph Theory 35 (2000) 176-192 pdf
  75. 2001

  76. On minimal vertex-Folkman graphs (with T. \L uczak and S. Urba\'nski) Discrete Mathematics 236 (1-3) (2001) 245-262 pdf
  77. On bipartite graphs with linear ramsey numbers (with R. Graham and V. R\"odl) Combinatorica 21 (2) (2001) 199-209 pdf
  78. 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
  79. 2002

  80. Holes in graphs (with Y. Peng and V. R\"odl)The Electr. J. of Combin. 9(1) (2002) #R1 pdf
  81. 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.

  82. Connectedness of graphs generated by a random $d$-process (with N. Wormald) Australian J. Math.72(1) (2002) 67-85 pdf
  83. The infamous upper tail (with S. Janson), Random Structures Algorithms 20(3) (2002) pdf
  84. Janson inequality Suplement III, Encyclopedia of Mathematics, ed: M. Hazewinkel Kluwer Academic Publisher (2002) 216-218 pdf
  85. Vertex-Ramsey properties of families of graphs (with T. \L uczak and S. Urba\'nski) JCT B 84 (2002) 240-248 pdf
  86. 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
  87. 2003

  88. Connectedness of the degree bounded star process (with C. Greenhill and N. Wormald) Combinatorics Probability and Computing 12 (2003) 269-283 pdf
  89. 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
  90. 2004

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

  95. Two variants of the size Ramsey number (with A. Kurek) Discuss. Math. Graph Th. 25 (2005) 141-149 pdf
  96. Planar Ramsey number for small graphs(with A. Dudek) Congr. Numer.(Boca Raton)pdf
  97. 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
  98. 2006

  99. 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
  100. 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
  101. A Dirac-type theorem for 3-uniform hypergraphs (with V. Rödl and E. Szemerédi) Combinatorics, Probability and Computing pdf
  102. 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
  103. Neighbour-distinguishing edge colorings of random regular graphs (with C. Greenhill) The Electr. J. Combin. 13(1) (2006) pdf
  104. 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
  105. 2007

  106. 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
  107. 2008

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

  113. The Ramsey number for 3-uniform tight hypergraph cycles(with P. Haxell, T. \L uczak, Y. Peng, V. Rödl, J. Skokan)CPC18 (2009), 165-204. pdf
  114. Perfect matchings in large uniform hypergraphs with large minimum collective degree(with V. Rödl and E. Szemer\'edi) JCT A 116(3) (2009) 613-636. pdf
  115. Short paths in $\epsilon$-regular pairs and small diameter decompositions of dense graphs (with J. Polcyn) Discrete Mathematics 309(22) 6375-6381 (2009)pdf
  116. The Complexity of Perfect Matching Problems on Dense Hypergraphs (with M. Karpiñski, E. Szymañska) ISAAC 2009 626-636 pdf
  117. 2010

  118. Subhypergraph counts in extremal and random hypergraphs and the fractional q-independence (with A. Dudek and J. Polcyn) Journal of Combinatorial Optimization 19 (2010) 184-199 pdf
  119. Computational complexity of the Hamiltonian cycle problem in dense hypergraphs (with M. Karpiñski and E. Szymañska), LATIN 2010 662-673 pdf
  120. On the number of perfect matchings in random lifts (with C. Greenhill and S. Janson) CPC19(5-6) 791 -817 pdf
  121. Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density (with M. Karpiñski, E. Szymañska) Intern. J. Found. Comp. Sci. 21(6) (2010) 905-924 pdf
  122. Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve) (with V. Rödl), An Irregular Mind (Szemer\'edi is 70), Bolyai Soc. Math. Studies 21 (2010) 561-590 pdf
  123. 2011

  124. Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs (with S. Janson) Arkiv f\"or Matematik 49(1) (2011) 79-96 pdf
  125. Perfect matchings and Hamilton cycles in hypergraphs with large degrees (with Klas Markström) Europ. J. Combin. 32(5) (2011) 677-687 pdf
  126. Dirac-type conditions for hamiltonian paths and cycles in 3-uniform hypergraphs (with V. Rödl and E. Szemer\'edi) Advances in Mathematics 227 (2011) 1225-1299 pdf
  127. 2012

  128. On the maximum number of edges in a triple system not containing a disjoint family of a given size (with P. Frankl and V. Rödl) CPC 21 (2012) 141-148 pdf
  129. An improved upper bound on the density of universal random graphs (extended abstract) (with D. Dellamonica Jr., Y. Kohayakawa, V. Rödl) LATIN 2012, LNCS 7256, pp. 231-242, 2012 (pdf)pdf
  130. Rainbow Hamilton cycles in uniform hypergraphs (with A. Dudek and A. Frieze) Electron. J. Combin. 19 (2012) #P46 pdf
  131. Universality of random graphs (with D. Dellamonica Jr., Y. Kohayakawa, V. Rödl) SIAM J. Discrete Math. 26 (2012) 353-374 pdf
  132. Large matchings in uniform hypergraphs and the conjectures of Erd\H{o}s and Samuels (with N. Alon, P. Frankl, H. Huang, V. Rödl, and B. Sudakov) JCT A 119(6) (2012) 1200-1215. pdf
  133. Approximate counting of matchings in sparse uniform hypergraphs (with M. Karpiñski and E. Szymañska) ANALCO 2013, 71-78 (2012) SIAM pdf
  134. 2013

  135. Hamilton saturated hypergraphs of essentially minimum size (with Andrzej ¯ak) Electron. J. Combin. 20(2) (2013) #P25 pdf
  136. Approximate counting of regular hypergraphs via switchings (with: Andrzej Dudek, Alan Frieze, Matas Sileikis) Inform. Process. Letters 113(19-21) 785-788 pdf
  137. The origins of the theory of random graphs (with M. Karo\'nski, updated) in: The Mathematics of Paul Erd\H os; Second Edition; Graham, Ne\v set\v ril, Butler, eds., Springer, 2013, 371-397. pdf
  138. Regular Hypergraphs: Asymptotic Counting and Loose Hamilton Cycles (with: A. Dudek, A. Frieze, M. \v{S}ileikis), in \textit{The Seventh European Conference on Combinatorics, Graph Theory and Applications. EuroComb 2013}, eds. J. Ne\v{s}et\v{r}il and M. Pellegrini, Pisa, Edizioni della Normale2013, 483-486. pdf
  139. 2014

  140. Families of triples with high minimum degree are Hamiltonian (with V. Rödl) Discuss. Math. -- Graph Th. 34 (2014) 363-383 pdf
  141. Approximate Counting of Matchings in (3,3)-Hypergraphs (with M. Karpinski, A. Dudek, and E. Szymañska) R. Ravi and I.L. Görtz (Eds.): SWAT 2014, LNCS 8503 (2014) 368-379 pdf
  142. 2015

  143. Loose Hamilton Cycles in Regular Hypergraphs (with: A. Dudek, A. Frieze, M. Sileikis) CPC 24(1) (2015) 179 - 194 pdf
  144. An improved upper bound on the density of universal random graphs (with D. Delamonica, Y. Kohayakawa, V. Rödl) RSA 46(2) (2015) 274 - 299 pdf


  145. Tur\'an Numbers for 3-Uniform Linear Paths of Length 3 (with E. Jackowska and J. Polcyn) Electron. J. Combin. 2 (2016) #P2.30 pdf
  146. Upper bounds on the minimum size of Hamilton saturated hypergraphs (with A. {\.Z}ak) Electron. J. Combin. 23(4) (2016) \#P4.12 pdf
  147. 2017

  148. Refined Turan numbers and Ramsey numbers for the loose 3-uniform path of length three (with J. Polcyn) Discrete Math.340 (2017) 107-118 pdf
  149. Embedding the Erdos-Renyi hypergraph into the random regular hypergraph and Hamiltonicity (with A. Dudek, A. Frieze, M. \v{S}ileikis) J. Combin. Th., Ser. B 122 (2017) 719-740 pdf
  150. An exponential-type upper bound for Folkman numbers (with V. Rödl and M. Schacht) Combinatorica 37 (4) (2017) 767{784 pdf
  151. On the Hamiltonicity of triple systems with high minimum degree (with V. Rödl, M. Schacht, and E. Szemeredi) Annals of Combinatorics 21(1) (2017) 95-117 pdf
  152. A hierarchy of maximal intersecting triple systems (with J. Polcyn) Opuscula Math. 37(4) (2017) 597-608pdf
  153. A short proof of Erdõs’ conjecture for triple systems (with P. Frankl and V. R\"odl) Acta Mathematica Hungarica 151(2) (2017) 495-509 pdf
  154. Ramsey properties of random graphs and Folkman numbers (with V. Rödl and M. Schacht) Discuss. Math. Graph Theory 37 (2017) 755–776 pdf
  155. Ramsey numbers and restricted Tur\'an numbers for the loose 3-uniform path of length three (with E. Jackowska and J. Polcyn) Electron. J. Combin. 24(3) (2017) \#P3.5 pdf
  156. 2018

  157. Constructive Ramsey Numbers For Loose Hyperpaths (with A. Dudek) LATIN 2018, LNCS 10807 pdf
  158. On multicolor Ramsey numbers for loose k-paths of length three (with T. {\L}uczak and J. Polcyn) Europ. J. Combin 71 (2018) 43-50 pdf


  1. Random Graphs'83, North-Holland, 1985, Annals of Discrete Mathematics 28, 363+viii pages (M. Karoñski and A. Ruciñski, eds.)
  2. Random Graphs, Wiley, 1990, 368+viii pages (M. Karo\'nski, J. Jaworski and A. Ruciñski, 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.