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. Monochromatic path in graphs and hypergraphs arXiv
  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
  3. Active clustering for labeling training data (with Quentin Lutz, Élie de Panafieu, Alex Scott), accepted in NeurIPS 2021, PDF
  4. Towards a hypergraph version of the Pósa-Seymour conjecture (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé) PDF
  5. Dirac-type conditions for spanning bounded degree hypertrees (with Nicolás Sanhueza-Matamala and Matías Pavez-Signé) PDF
  6. 3-colouring in P_t-free graphs without short cycles (with Alberto Rojas Anríquez) PDF
  7. Kalai's conjecture for r-partite r-graphs PDF
  8. Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Approximate Asymptotic Result (with Bruce Reed) PDF
  9. Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex II: A Tight Result (with Bruce Reed) PDF

Refereed journal publications:

  1. Clique immersions and independence number (with Sebastián Bustamante, José Zamora and Daniel Quiroz), European Journal of Combinatorics, accepted 2022 arXiv
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. Partitioning 2-coloured complete k-uniform hypergraphs intp monochromatic l-cycles (with Sebastián Bustamante), European Journal of Combinatorics 71 (2018), 213-221 PDF
  13. The domino problem on groups of polynomial growth (with Alexis Ballier), Groups, Geometry and Dynamics 12 (2018), 1-13 PDF
  14. Monochromatic tree covers for multicoloured graphs (with Sebastián Bustamante), Discrete Mathematics 341(1) (January 2018) 266-276 PDF
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. Clique coloring B1-EPG graphs (with Flavia Bonomo and Pia Mazzoleni), Discrete Mathematics, Volume 340, Issue 5, May 2017, pages 1008-1011 PDF
  21. Local colourings and monochromatic partitions in complete bipartite graphs (with R. Lang), European Journal of Combinatorics, Volume 60, February 2017, pages 42-54 PDF
  22. Convex p-partitions of bipartite graphs (with L. Grippo, M. Matamala, M. Safe), Theoretical Computer Science, Volume 609 (2016), pp. 511-514 PDF
  23. Monochromatic Cycle Partitions in Local Edge Colourings (with David Conlon), Journal of Graph Theory, Volume 81, Issue 2 (2016), pages 134-145 PDF
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. Cycles are strongly Ramsey unsaturated (with J. Skokan), Combinatorics, Probability and Computing, 2014, Volume 23, Issue 04, pp 607-630 PDF
  31. Minimal bricks have many vertices of small degree (with H. Bruhn), European Journal of Combinatorics, 2014, Volume 36, pp.261-269 PDF
  32. Connectivity and tree structure in finite graphs (with J. Carmesin, R. Diestel, F. Hundertmark), Combinatorica, 2014, Volume 34, Issue 1, pp 11-46 PDF
  33. Forcing large complete minors in infinite graphs (with J. Zamora), SIAM Journal on Discrete Mathematics , 27(2), 2013, 697-707 PDF
  34. 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
  35. On claw-free t-perfect graphs (with H. Bruhn), Mathematical Programming , June 2012, Volume 133, Issue 1-2, pp 461-480 PDF
  36. Extremal infinite graph theory, Discrete Mathematics 311 (Special Volume on Infinite Graphs), 2011, p. 1472-1496 PDF
  37. 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
  38. t-perfection is always strong for claw-free graphs (with H. Bruhn) SIAM Journal on Discrete Mathematics , 24 (3), 2010, p.770-781 PDF
  39. Duality of ends (with H. Bruhn), Combinatorics, Probability and Computing , 12 (1), 2010, p.47-60 PDF
  40. 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
  41. On end degrees and infinite circuits in locally finite graphs (with H. Bruhn), Combinatorica, 27, 2007, p.269-291 PDF
  42. Forcing highly connected subgraphs, Journal of Graph Theory 54, 2007, p.331-349 PDF
  43. Arboricity and tree-packing in locally finite graphs, Journal of Combinatorial Theory (Series B) 96, 2006, p.302-312 PDF
  44. MacLane's planarity criterion for locally finite graphs (with H. Bruhn), Journal of Combinatorial Theory (Series B) 96, 2006, p.225-239 PDF
  45. Menger's theorem for infinite graphs with ends (with H. Bruhn and R. Diestel), Journal of Graph Theory 50, 2005, p.199-211 PDF
  46. 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. Dirac-type conditions for spanning bounded-degree hypertrees. M. Pavez-Signé, N. Sanhueza-Matamala, M. Stein Extended Abstracts EuroComb 2021, 586-592
  2. 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
  3. 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
  4. 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
  5. Local colourings and monochromatic partitions in complete bipartite graphs (with Richard Lang), Eurocomb 2015, Electronic Notes in Discrete Mathematics, Volume 49, 2015, pp757-763
  6. 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
  7. 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
  8. 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
  9. Small degree vertices in minimal bricks (with H. Bruhn), LAGOS 2013, Electronic Notes in Discr. Math., 2013, Volume 44, pp. 95-100
  10. Complexity of Splits Reconstruction for Low Degree Trees (with S. Gaspers, M. Liedloff, K. Suchan), WG 2011, LNCS 6986, 2011, pp.167-178 arXiv
  11. 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
  12. 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
  13. Degree and Substructure in infinite graphs, Midsummer Combinatorial Workshop 2010, Charles University, Preprint KAM-Series 2011PDF
  14. Characterising claw-free t-perfect graphs, extended abstract, Eurocomb '09 (with Henning Bruhn), Electr. Notes in Discr. Math., 34 (2009), pp.501-507 PDF
  15. 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.