maya stein              






Full professor (profesora titular) at the Department of Mathematical Engineering and deputy director of the Center for Mathematical Modeling (CNRS IRL 2807), Universidad de Chile, Santiago.

We launched a new open access journal, Innovations in Graph Theory !


CONTACT       PUBLICATIONS       GRANTS       EDITORIAL WORK       SERVICE       STUDENTS       TEACHING

Preprints:

  1. Oriented Trees in Digraphs without Oriented 4-cycles (with Ana Trujillo-Negrete) arXiV
  2. Packing large balanced trees into bipartite graphs (with C.G. Fernandes, T. Naia, G. Santos) arXiv
  3. A bounded diameter strengthening of König's Theorem (with Louis DeBiasio, António Girão, Penny Haxell) arXiv
  4. Embedding nearly spanning trees (with Bruce Reed) arXiv
  5. Antidirected trees in dense digraphs (with A. L. Trujillo-Negrete) arXiv
  6. Monochromatic partitions in 2-edge-coloured bipartite graphs (with C. Fernández and M. Pavez-Signé) arXiv
  7. An exact upper bound for the minimum size of a path system that weakly separates a clique (with G. Kontogeorgiou) PDF

Publications:

  1. Degree conditions for trees in undirected and directed graphs, to appear in the volume "Women in Mathematics in Latin America," part of the Springer-Birkhäuser Trends in Mathematics Series PDF
  2. On the Ramsey number of the double star (with Freddy Flores Dubó) PDF Discrete Mathematics, Volume 348, Issue 1, January 2025, 114227
  3. Oriented trees and paths in digraphs, In: Fischer, F., Johnson, R. eds, Surveys in Combinatorics 2024. London Mathematical Society Lecture Note Series. Cambridge University Press; 2024:271-295. arXiv
  4. Antidirected subgraphs of oriented graphs (with Camila Zárate-Guerén) arXiv Combinatorics, Probability and Computing, Volume 33 , Issue 4 , July 2024 , pp. 446 - 466
  5. Partitioning a 2-edge-coloured graph of minimum degree 2n/3 + o(n) into three monochromatic cycles (with Peter Allen, Julia Böttcher, Richard Lang, and Jozef Skokan) arXiv European Journal of Combinatorics, Volume 121, October 2024, 103838
  6. Dirac-type conditions for spanning bounded degree hypertrees (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé), Journal of Combinatorial Theory, Series B, Volume 165, March 2024, Pages 97-141 PDF
  7. Towards a hypergraph version of the Pósa-Seymour conjecture (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé), Advances in Combinatorics, here
  8. Antipaths in oriented graphs (with Tereza Klimošóva), Discrete Mathematics 346 (9), 113515, 2023 arXiv
  9. Monochromatic paths in graphs and hypergraphs, Electronic Journal of Combinatorics, P1.53, 2023 arXiv
  10. 3-colouring in P_t-free graphs without short cycles (with Alberto Rojas Anríquez), Algorithmica 85(4), 831-853, 2023 PDF
  11. Kalai's conjecture for r-partite r-graphs, European Journal on Combinatorics, Volume 117, March 2024, 103827 (Special issue for Eurocomb 2019) PDF
  12. Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Approximate Asymptotic Result (with Bruce Reed), Journal of Graph Theory 102(4), 737-783, 2023 PDF
  13. Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex II: A Tight Result (with Bruce Reed), Journal of Graph Theory, 102(4), 797-821, 2023 PDF
  14. Clique immersions and independence number (with Sebastián Bustamante, José Zamora and Daniel Quiroz), European Journal of Combinatorics, Volume 106, December 2022, 103550 arXiv
  15. Active clustering for labeling training data (with Quentin Lutz, Élie de Panafieu, Alex Scott), NeurIPS 2021, 8469-8480 PDF
  16. The Erdős-Sós conjecture for bounded degree trees (with Guido Besomi and Matías Pavez-Signé), Combinatorics, Probability and Computing 30(5), 741-761, 2021 PDF
  17. Better 3-colouring algorithms: triangle and a seven vertex path (with Flavia Bonomo-Braberman, Maria Chudnovsky, Jan Goedgebeur, Peter Maceli, Oliver Schaudt and Mingxian Zhong), Theoretical Computer Science Volume 850, p. 98-115, 2021 PDF
  18. Tree containment and degree conditions, Discrete Mathematics and Applications (Editors: A. Raigoroskii, M. Rassias), Springer (January 2021), ISBN 978-3-030-55856-7 PDF
  19. Maximum and minimum degree conditions for embedding trees (with Guido Besomi and Matías Pavez-Signé), SIAM Journal on Discrete Mathematics, Volume 34, Issue 4, p. 2108-2123, 2020 PDF
  20. Regularity inheritance in pseudorandom graphs (with Peter Allen, Julia Böttcher, Jozef Skokan), Random Structures and Algorithms, Volume 56, Issue 2, p. 306-338, 2020 PDF
  21. A Variant of the Erdős-Sós conjecture (with Fred Havet, Bruce Reed, David Wood), Journal of Graph Theory, Volume 94, Issue 1, p. 131-158, 2020 PDF
  22. Degree conditions for embedding trees (with Guido Besomi and Matías Pavez-Signé), SIAM Journal on Discrete Mathematics , Volume 33, Issue 3, p. 1521-1555, 2019 PDF
  23. Approximately coloring graphs without long induced paths (with Maria Chudnovsky, Oliver Schaudt, Sophie Spirkl, Mingxian Zhong), Algorithmica, Volume 81, Issue 8, p. 3186-3199, 2019 PDF
  24. Almost partitioning 2-coloured complete 3-uniform hypergraphs into monochromatic tight and loose cycles (with Hiệp Hàn and Sebastián Bustamante), Journal of Graph Theory, Volume 91, Issue 1, May 2019 PDF
  25. Partitioning two-coloured complete multipartite graphs into monochromatic paths (with Oliver Schaudt), Journal of Graph Theory, Volume 91, Issue 2, June 2019, pages 122-147 PDF
  26. Three-coloring and list-three-coloring of graphs without induced paths on seven vertices (with F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Zhong), Combinatorica 28 (4) (August 2018), 779-801 PDF
  27. Partitioning 2-coloured complete k-uniform hypergraphs intp monochromatic l-cycles (with Sebastián Bustamante), European Journal of Combinatorics 71 (2018), 213-221 PDF
  28. The domino problem on groups of polynomial growth (with Alexis Ballier), Groups, Geometry and Dynamics 12 (2018), 1-13 PDF
  29. Monochromatic tree covers for multicoloured graphs (with Sebastián Bustamante), Discrete Mathematics 341(1) (January 2018) 266-276 PDF
  30. Almost partitioning a 3-edge coloured K_n,n into 5 monochromatic cycles (with Richard Lang, Oliver Schaudt), SIAM Journal on Discrete Mathematics, Vol. 31, Issue 2 (2017), pp. 1374-1402 PDF
  31. The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition (with J. Hladký, J. Komlós, D. Piguet, M. Simonovits, E. Szemerédi), SIAM Journal on Discrete Mathematics 31-2 (2017), pages 945-982 PDF
  32. The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs (with J. Hladký, J. Komlós, D. Piguet, M. Simonovits, E. Szemerédi), SIAM Journal on Discrete Mathematics 31-2 (2017), pages 983-1016 PDF
  33. The approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs (with J. Hladký, J. Komlós, D. Piguet, M. Simonovits, E. Szemerédi), SIAM Journal on Discrete Mathematics 31-2 (2017), pages 1017-1071 PDF
  34. The approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result (with J. Hladký, J. Komlós, D. Piguet, M. Simonovits, E. Szemerédi), SIAM Journal on Discrete Mathematics 31-2 (2017), pages 1072-1148 PDF
  35. Clique coloring B1-EPG graphs (with Flavia Bonomo and Pia Mazzoleni), Discrete Mathematics, Volume 340, Issue 5, May 2017, pages 1008-1011 PDF
  36. Local colourings and monochromatic partitions in complete bipartite graphs (with R. Lang), European Journal of Combinatorics, Volume 60, February 2017, pages 42-54 PDF
  37. Convex p-partitions of bipartite graphs (with L. Grippo, M. Matamala, M. Safe), Theoretical Computer Science, Volume 609 (2016), pp. 511-514 PDF
  38. Monochromatic Cycle Partitions in Local Edge Colourings (with David Conlon), Journal of Graph Theory, Volume 81, Issue 2 (2016), pages 134-145 PDF
  39. List edge colouring and total colouring in graphs of low treewidth (with Henning Bruhn, Richard Lang), Journal of Graph Theory, Volume 81, Issue 3 (2016), pages 272-282 PDF
  40. The approximate Loebl-Komlós-Sós conjecture and embedding treees in sparse graphs (with J. Hladký, D. Piguet, M. Simonovits, E. Szemerédi), Electronic Research Announcements in Mathematical Sciences , Volume 22, pp 1-11, 2015 PDF
  41. b-colouring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs (with Flavia Bonomo, Oliver Schaudt, Mario Valencia-Pabon), Algorithmica , Volume 73, Issue 2 (2015) pp 289 - 305 PDF
  42. Geodesic stability for memoryless binary long-lived consensus (with C. G. Fernandes), Journal of Computer and System Sciences, Volume 81, Issue 7, November 2015, pp 1210-120 PDF
  43. Linear and projective boundaries in HNN-extensions and distortion phenomena (with J. Lehnert, B. Kroen), Journal of Group Theory, Volume 18, Issue 3, pp 455-488, February 2015 PDF
  44. Complexity of Splits Reconstruction for Low-Degree Trees (with Serge Gaspers, Mathieu Liedloff, Karol Suchan), Discrete Applied Mathematics , January 2015, Vol. 180, p. 89-100 PDF
  45. Cycles are strongly Ramsey unsaturated (with J. Skokan), Combinatorics, Probability and Computing, 2014, Volume 23, Issue 04, pp 607-630 PDF
  46. Minimal bricks have many vertices of small degree (with H. Bruhn), European Journal of Combinatorics, 2014, Volume 36, pp.261-269 PDF
  47. Connectivity and tree structure in finite graphs (with J. Carmesin, R. Diestel, F. Hundertmark), Combinatorica, 2014, Volume 34, Issue 1, pp 11-46 PDF
  48. Forcing large complete minors in infinite graphs (with J. Zamora), SIAM Journal on Discrete Mathematics , 27(2), 2013, 697-707 PDF
  49. An approximate version of the Loebl-Komlós-Sós conjecture (with D. Piguet), Journal of Combinatorial Theory, Series B , 102(1) 2012, p. 102-125 PDF
  50. On claw-free t-perfect graphs (with H. Bruhn), Mathematical Programming , June 2012, Volume 133, Issue 1-2, pp 461-480 PDF
  51. Extremal infinite graph theory, Discrete Mathematics 311 (Special Volume on Infinite Graphs), 2011, p. 1472-1496 PDF
  52. Ends and vertices of small degree in infinite minimally k-(edge)-connected graphs, SIAM Journal on Discrete Mathematics, 24 (4), 2010, p.1584-1596 PDF
  53. t-perfection is always strong for claw-free graphs (with H. Bruhn) SIAM Journal on Discrete Mathematics , 24 (3), 2010, p.770-781 PDF
  54. Duality of ends (with H. Bruhn), Combinatorics, Probability and Computing , 12 (1), 2010, p.47-60 PDF
  55. The Loebl-Komlós-Sós conjecture for trees of diameter 5 and certain caterpillars (with D. Piguet), Electronic Journal of Combinatorics , 15, 2008, R106 PDF
  56. On end degrees and infinite circuits in locally finite graphs (with H. Bruhn), Combinatorica, 27, 2007, p.269-291 PDF
  57. Forcing highly connected subgraphs, Journal of Graph Theory 54, 2007, p.331-349 PDF
  58. Arboricity and tree-packing in locally finite graphs, Journal of Combinatorial Theory (Series B) 96, 2006, p.302-312 PDF
  59. MacLane's planarity criterion for locally finite graphs (with H. Bruhn), Journal of Combinatorial Theory (Series B) 96, 2006, p.225-239 PDF
  60. Menger's theorem for infinite graphs with ends (with H. Bruhn and R. Diestel), Journal of Graph Theory 50, 2005, p.199-211 PDF
  61. Cycle-cocycle partitions and faithful cycle covers for locally finite graphs (with H. Bruhn and R. Diestel), Journal of Graph Theory 50, 2005, p.150-161 PDF

Conference versions (mainly Eurocomb and LAGOS proceedings):

  1. Semidegree, edge density and antidirected subgraphs M. Stein, C. Zárate-Guerén, European Conference on Combinatorics, Graph Theory and Applications
  2. Dirac-type conditions for spanning bounded-degree hypertrees. M. Pavez-Signé, N. Sanhueza-Matamala, M. Stein Extended Abstracts EuroComb 2021, 586-592
  3. Embedding trees with maximum and minimum degree conditions (with G. Besomi and M. Pavez-Signé), Eurocomb 2019, Acta Mathematica Universitatis Comenianae 88 (3), 457-462
  4. Large immersions in graphs with independence number 3 and 4 (with S. Bustamante, J. Zamora, D. Quiroz), LAGOS 2019, Electronic Notes in Theoretical Computer Science 346, 221-228
  5. Almost partitioning 2-edge-colourings of 3-uniform hypergraphs with two monochromatic tight cycles (with Sebastian Bustamante and Hiep Han), (Eurocomb 2017), Electronic Notes in Discrete Mathematics 61 (August 2017) 185-190
  6. Local colourings and monochromatic partitions in complete bipartite graphs (with Richard Lang), Eurocomb 2015, Electronic Notes in Discrete Mathematics, Volume 49, 2015, pp757-763
  7. Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles (with Richard Lang, Oliver Schaudt), Eurocomb 2015, Electronic Notes in Discrete Mathematics, Volume 49, 2015, pp. 787-794
  8. Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles (with O. Schaudt), LAGOS 2015, Electronic Notes in Discrete MAthematics, Volume 50, 2015, pp. 313-318
  9. b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs (with F. Bonomo, M. Valencia-Pabon, O. Schaudt), ISCO 2014, LNCS 8596, 100-111
  10. Small degree vertices in minimal bricks (with H. Bruhn), LAGOS 2013, Electronic Notes in Discr. Math., 2013, Volume 44, pp. 95-100
  11. Complexity of Splits Reconstruction for Low Degree Trees (with S. Gaspers, M. Liedloff, K. Suchan), WG 2011, LNCS 6986, 2011, pp.167-178 arXiv
  12. Stability in geodesics for memoryless binary long-lived consensus (with C. G .Fernandes), Lagos 2011, Electr. Notes in Discr. Math., 37 (2011), pp.351-356 PDF
  13. The relative degree and large complete minors in infinite graphs (with J. Zamora), Lagos 2011, Electr. Notes in Discr. Math, 37 (2011), p.129-134 PDF
  14. Degree and Substructure in infinite graphs, Midsummer Combinatorial Workshop 2010, Charles University, Preprint KAM-Series 2011PDF
  15. Characterising claw-free t-perfect graphs, extended abstract, Eurocomb '09 (with Henning Bruhn), Electr. Notes in Discr. Math., 34 (2009), pp.501-507 PDF
  16. An approximate version of the Loebl-Komlós-Sós conjecture, extended abstract, Eurocomb '07 (with D. Piguet), Electr. Notes in Discr. Math., 29 (2007), 249-253 PDF

Theses:

  1. Extremal graph theory: Degree and substructure in finite and infinite graphs, Habilitationsschrift, Universität Hamburg 2010 PDF
  2. Ends of graphs, Doktorarbeit Universität Hamburg 2005.
  3. Die Erdős-Menger-Vermutung for abzählbare Graphen mit Enden, Diplomarbeit Universität Hamburg 2002.