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.


CONTACT       PUBLICATIONS       GRANTS       EDITORIAL WORK       SERVICE       STUDENTS       TEACHING

Book chapter:

  1. Tree containment and degree conditions, Discrete Mathematics and Applications (Editors: A. Raigoroskii, M. Rassias), Springer (January 2021), ISBN 978-3-030-55856-7 PDF

Preprints:

  1. Antipaths in oriented graphs (with Tereza Klimošóva) arXiv
  2. Antidirected subgraphs of oriented graphs (with Camila Zárate-Guerén) arXiv
  3. Monochromatic paths in graphs and hypergraphs arXiv
  4. 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
  5. Towards a hypergraph version of the Pósa-Seymour conjecture (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé) PDF
  6. Dirac-type conditions for spanning bounded degree hypertrees (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé) PDF

Refereed journal publications:

  1. 3-colouring in P_t-free graphs without short cycles (with Alberto Rojas Anríquez), in press, Algorithmica PDF
  2. Kalai's conjecture for r-partite r-graphs, in press, European Journal on Combinatorics PDF
  3. Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Approximate Asymptotic Result (with Bruce Reed), in press Journal of Graph Theory PDF
  4. Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex II: A Tight Result (with Bruce Reed), in press, Journal of Graph Theory PDF
  5. Clique immersions and independence number (with Sebastián Bustamante, José Zamora and Daniel Quiroz), European Journal of Combinatorics, Volume 106, December 2022, 103550 arXiv
  6. 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
  7. 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 Theoretical Computer Science Volume 850, p. 98-115, 2021 PDF
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. Partitioning 2-coloured complete k-uniform hypergraphs intp monochromatic l-cycles (with Sebastián Bustamante), European Journal of Combinatorics 71 (2018), 213-221 PDF
  17. The domino problem on groups of polynomial growth (with Alexis Ballier), Groups, Geometry and Dynamics 12 (2018), 1-13 PDF
  18. Monochromatic tree covers for multicoloured graphs (with Sebastián Bustamante), Discrete Mathematics 341(1) (January 2018) 266-276 PDF
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. Clique coloring B1-EPG graphs (with Flavia Bonomo and Pia Mazzoleni), Discrete Mathematics, Volume 340, Issue 5, May 2017, pages 1008-1011 PDF
  25. Local colourings and monochromatic partitions in complete bipartite graphs (with R. Lang), European Journal of Combinatorics, Volume 60, February 2017, pages 42-54 PDF
  26. Convex p-partitions of bipartite graphs (with L. Grippo, M. Matamala, M. Safe), Theoretical Computer Science, Volume 609 (2016), pp. 511-514 PDF
  27. Monochromatic Cycle Partitions in Local Edge Colourings (with David Conlon), Journal of Graph Theory, Volume 81, Issue 2 (2016), pages 134-145 PDF
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. Cycles are strongly Ramsey unsaturated (with J. Skokan), Combinatorics, Probability and Computing, 2014, Volume 23, Issue 04, pp 607-630 PDF
  35. Minimal bricks have many vertices of small degree (with H. Bruhn), European Journal of Combinatorics, 2014, Volume 36, pp.261-269 PDF
  36. Connectivity and tree structure in finite graphs (with J. Carmesin, R. Diestel, F. Hundertmark), Combinatorica, 2014, Volume 34, Issue 1, pp 11-46 PDF
  37. Forcing large complete minors in infinite graphs (with J. Zamora), SIAM Journal on Discrete Mathematics , 27(2), 2013, 697-707 PDF
  38. 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
  39. On claw-free t-perfect graphs (with H. Bruhn), Mathematical Programming , June 2012, Volume 133, Issue 1-2, pp 461-480 PDF
  40. Extremal infinite graph theory, Discrete Mathematics 311 (Special Volume on Infinite Graphs), 2011, p. 1472-1496 PDF
  41. 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
  42. t-perfection is always strong for claw-free graphs (with H. Bruhn) SIAM Journal on Discrete Mathematics , 24 (3), 2010, p.770-781 PDF
  43. Duality of ends (with H. Bruhn), Combinatorics, Probability and Computing , 12 (1), 2010, p.47-60 PDF
  44. 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
  45. On end degrees and infinite circuits in locally finite graphs (with H. Bruhn), Combinatorica, 27, 2007, p.269-291 PDF
  46. Forcing highly connected subgraphs, Journal of Graph Theory 54, 2007, p.331-349 PDF
  47. Arboricity and tree-packing in locally finite graphs, Journal of Combinatorial Theory (Series B) 96, 2006, p.302-312 PDF
  48. MacLane's planarity criterion for locally finite graphs (with H. Bruhn), Journal of Combinatorial Theory (Series B) 96, 2006, p.225-239 PDF
  49. Menger's theorem for infinite graphs with ends (with H. Bruhn and R. Diestel), Journal of Graph Theory 50, 2005, p.199-211 PDF
  50. 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 proceedings:

  1. Active clustering for labeling training data (with Quentin Lutz, Élie de Panafieu, Alex Scott), Proceedings of NeurIPS 2021, PDF
  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.