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. Antidirected trees in dense digraphs (with A. L. Trujillo-Negrete) arXiv
  2. Monochromatic partitions in 2-edge-coloured bipartite graphs (with C. Fernández and M. Pavez-Signé) arXiv
  3. An exact upper bound for the minimum size of a path system that weakly separates a clique (with G. Kontogeorgiou) PDF
  4. On the Ramsey number of the double star (with Freddy Flores Dubó) PDF
  5. Oriented trees and paths in digraphs arXiv

Publications:

  1. Antidirected subgraphs of oriented graphs (with Camila Zárate-Guerén) arXiv accepted for publication in Combinatorics, Probability and Computing
  2. 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 to appear in European Journal of Combinatorics
  3. Dirac-type conditions for spanning bounded degree hypertrees (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé), to appear in Journal of Combinatorial Theory, Series B PDF
  4. Towards a hypergraph version of the Pósa-Seymour conjecture (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé), Advances in Combinatorics, here
  5. Antipaths in oriented graphs (with Tereza Klimošóva), Discrete Mathematics 346 (9), 113515, 2023 arXiv
  6. Monochromatic paths in graphs and hypergraphs, Electronic Journal of Combinatorics, P1.53, 2023 arXiv
  7. 3-colouring in P_t-free graphs without short cycles (with Alberto Rojas Anríquez), Algorithmica 85(4), 831-853, 2023 PDF
  8. Kalai's conjecture for r-partite r-graphs, European Journal on Combinatorics, special issue for Eurocomb 2019, 103827 PDF
  9. 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
  10. 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
  11. Clique immersions and independence number (with Sebastián Bustamante, José Zamora and Daniel Quiroz), European Journal of Combinatorics, Volume 106, December 2022, 103550 arXiv
  12. Active clustering for labeling training data (with Quentin Lutz, Élie de Panafieu, Alex Scott), NeurIPS 2021, 8469-8480 PDF
  13. 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
  14. 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
  15. Tree containment and degree conditions, Discrete Mathematics and Applications (Editors: A. Raigoroskii, M. Rassias), Springer (January 2021), ISBN 978-3-030-55856-7 PDF
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. Partitioning 2-coloured complete k-uniform hypergraphs intp monochromatic l-cycles (with Sebastián Bustamante), European Journal of Combinatorics 71 (2018), 213-221 PDF
  25. The domino problem on groups of polynomial growth (with Alexis Ballier), Groups, Geometry and Dynamics 12 (2018), 1-13 PDF
  26. Monochromatic tree covers for multicoloured graphs (with Sebastián Bustamante), Discrete Mathematics 341(1) (January 2018) 266-276 PDF
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. Clique coloring B1-EPG graphs (with Flavia Bonomo and Pia Mazzoleni), Discrete Mathematics, Volume 340, Issue 5, May 2017, pages 1008-1011 PDF
  33. Local colourings and monochromatic partitions in complete bipartite graphs (with R. Lang), European Journal of Combinatorics, Volume 60, February 2017, pages 42-54 PDF
  34. Convex p-partitions of bipartite graphs (with L. Grippo, M. Matamala, M. Safe), Theoretical Computer Science, Volume 609 (2016), pp. 511-514 PDF
  35. Monochromatic Cycle Partitions in Local Edge Colourings (with David Conlon), Journal of Graph Theory, Volume 81, Issue 2 (2016), pages 134-145 PDF
  36. 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
  37. 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
  38. 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
  39. 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
  40. 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
  41. 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
  42. Cycles are strongly Ramsey unsaturated (with J. Skokan), Combinatorics, Probability and Computing, 2014, Volume 23, Issue 04, pp 607-630 PDF
  43. Minimal bricks have many vertices of small degree (with H. Bruhn), European Journal of Combinatorics, 2014, Volume 36, pp.261-269 PDF
  44. Connectivity and tree structure in finite graphs (with J. Carmesin, R. Diestel, F. Hundertmark), Combinatorica, 2014, Volume 34, Issue 1, pp 11-46 PDF
  45. Forcing large complete minors in infinite graphs (with J. Zamora), SIAM Journal on Discrete Mathematics , 27(2), 2013, 697-707 PDF
  46. 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
  47. On claw-free t-perfect graphs (with H. Bruhn), Mathematical Programming , June 2012, Volume 133, Issue 1-2, pp 461-480 PDF
  48. Extremal infinite graph theory, Discrete Mathematics 311 (Special Volume on Infinite Graphs), 2011, p. 1472-1496 PDF
  49. 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
  50. t-perfection is always strong for claw-free graphs (with H. Bruhn) SIAM Journal on Discrete Mathematics , 24 (3), 2010, p.770-781 PDF
  51. Duality of ends (with H. Bruhn), Combinatorics, Probability and Computing , 12 (1), 2010, p.47-60 PDF
  52. 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
  53. On end degrees and infinite circuits in locally finite graphs (with H. Bruhn), Combinatorica, 27, 2007, p.269-291 PDF
  54. Forcing highly connected subgraphs, Journal of Graph Theory 54, 2007, p.331-349 PDF
  55. Arboricity and tree-packing in locally finite graphs, Journal of Combinatorial Theory (Series B) 96, 2006, p.302-312 PDF
  56. MacLane's planarity criterion for locally finite graphs (with H. Bruhn), Journal of Combinatorial Theory (Series B) 96, 2006, p.225-239 PDF
  57. Menger's theorem for infinite graphs with ends (with H. Bruhn and R. Diestel), Journal of Graph Theory 50, 2005, p.199-211 PDF
  58. 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.