Martin Balko

Teaching (In Czech)  |  Short CV  |  Contact  |  Publications

photo
I am an associate professor (docent) at the Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University in Prague. Before that, I was a postdoctoral researcher at the Department of Computer Science, Faculty of Natural Sciences, Ben Gurion University of the Negev, Beer Sheva, Israel. I was also a postdoctoral researcher at Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary. I obtained my PhD degree at Charles University in Prague, Czech Republic, under the supervision of Pavel Valtr.

My research interests include graph theory, classical combinatorics, Ramsey theory, and combinatorial geometry.

Office hours: by e-mail appointment
Teaching (Výuka):
up
Short CV:
up
Contact:
up
 
Department of Applied Mathematics
Faculty of Mathematics and Physics, Charles University in Prague
Malostranské nám. 25, 118 00 Praha 1
Czech Republic

Room S 125, 1st floor, Malá Strana
e-mail: balko (AT) kam.mff.cuni.cz
Publications:
up
  • Approximating Nash equilibria in sparse multiplayer games (with Tomáš Čížek), submitted, 2026.
  • Proof of the Harary–Hill conjecture: an exposition in preparation, 2026. [preliminary version]
  • On edge-ordered Ramsey numbers of hypergraphs (with Jelena Glišić), submitted, 2026. [preliminary version]
  • A general upper bound on multicolor ordered Ramsey numbers (with Klára Grinerová), submitted, 2026. [preliminary version]
  • Massively Parallel Proof-Number Search for Impartial Games and Beyond (with Tomáš Čížek and Martin Schmid), in preparation. [preliminary version | poster | code | data]
    • Conference version in the Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2026) 40(43), pages 36838–36846, 2026. [DOI]
  • Estimating multicolor ordered Ramsey numbers (with Klára Grinerová), Discrete Mathematics 349(11), Article 115286, 2026. [DOI]
    • Conference version in the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2025), HUN-REN Alfréd Rényi Institute of Mathematics, pages 81–89, 2025. [booklet of abstracts]
  • Crossing and non-crossing families (with Todor Antić and Birgit Vogtenhuber). In the Proceedings of the 33rd International Symposium on Graph Drawing and Network Visualization (Graph Drawing 2025), Leibniz International Proceedings in Informatics (LIPIcs) 357, pages 19:1–19:15, 2025. [DOI]
  • A survey on ordered Ramsey numbers, Sum(m)it280: Surveys in Extremal Combinatorics and Combinatorial Geometry, Bolyai Society Mathematical Studies 32, Springer, Cham, pages 71–96, 2026. [DOI]
  • On forbidden configurations in point-line incidence graphs (with Nóra Frankl), SIAM Journal on Discrete Mathematics 39(4), pages 2296–2310, 2025. [DOI | presentation]
  • The Erdős–Szekeres conjecture revisited (with Jineon Baek), Journal of Combinatorial Theory, Series A 222, Article 106195, 2026. [DOI | presentation]
    • Conference version in the Proceedings of the 41st International Symposium on Computational Geometry (SoCG 2025), Leibniz International Proceedings in Informatics (LIPIcs) 332, pages 13:1–13:15, 2025. [DOI]
  • On the uncrossed number of graphs (with Petr Hliněný, Tomáš Masařík, Joachim Orthaber, Birgit Vogtenhuber, and Mirko H. Wagner), submitted, 2024. [preliminary version]
    • Conference version in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (Graph Drawing 2024), Leibniz International Proceedings in Informatics (LIPIcs) 320, pages 18:1–18:13, 2024. [DOI]
  • Faces in rectilinear drawings of complete graphs (with Anna Brötzner, Fabian Klute, and Josef Tkadlec), European Journal of Combinatorics 130, Article 104217, 2025. [DOI | presentation]
    • Extended abstract in the (informal) proceedings of the 40th European Workshop on Computational Geometry (EuroCG 2024), pages 8:1–8:7, 2024. [extended abstract]
  • On ordered Ramsey numbers of matchings versus triangles (with Marian Poljak), The Electronic Journal of Combinatorics 31(2), P2.23, 16 pages, 2024. [DOI]
    • Extended abstract in the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2023), MUNI Press, pages 94–100, 2023. [DOI]
  • On Helly numbers of exponential lattices (with Gergely Ambrus, Nóra Frankl, Attila Jung, and Márton Naszódi), European Journal of Combinatorics 116, Article 103884, 2024. [DOI | presentation]
    • Conference version in the Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023), Leibniz International Proceedings in Informatics (LIPIcs) 258, pages 8:1–8:16, 2023. [DOI]
  • The constant of point–line incidence constructions (with Adam Sheffer and Ruiwen Tang), Computational Geometry: Theory and Applications 114, Article 102009, 2023. [DOI]
  • Ramsey theorem for trees with successor operation (with David Chodounský, Natasha Dobrinen, Jan Hubička, Matěj Konečný, Jaroslav Nešetřil, and Andy Zucker), submitted, 2023. [preliminary version]
  • Erdős–Szekeres-type problems in the real projective plane (with Manfred Scheucher and Pavel Valtr), Discrete & Computational Geometry 72(4), pages 1545–1578, 2024. [DOI]
    • Conference version in the Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022), Leibniz International Proceedings in Informatics (LIPIcs) 224, pages 10:1–10:15, 2022. [DOI]
  • Bounding and computing obstacle numbers of graphs (with Steven Chaplick, Robert Ganian, Siddharth Gupta, Michael Hoffmann, Pavel Valtr, and Alexander Wolff), SIAM Journal on Discrete Mathematics 38(2), pages 1537–1565, 2024. [DOI]
    • Conference version in the Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022), Leibniz International Proceedings in Informatics (LIPIcs) 244, pages 11:1–11:13, 2022. [DOI]
  • Exact big Ramsey degrees for finitely constrained binary free amalgamation classes (with David Chodounský, Natasha Dobrinen, Jan Hubička, Matěj Konečný, Lluís Vena, and Andy Zucker), Journal of the European Mathematical Society 28(5), pages 2101–2150, 2026. [DOI]
  • Implementation of Sprouts: a graph drawing game (with Tomáš Čížek), Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (Graph Drawing 2021), Lecture Notes in Computer Science 12868, pages 391–405, 2021. [DOI]
  • Characterisation of the big Ramsey degrees of the generic partial order (with David Chodounský, Natasha Dobrinen, Jan Hubička, Matěj Konečný, Lluís Vena, and Andy Zucker), Transactions of the American Mathematical Society 379(10), pages 6921–6951, 2026. [DOI]
    • Extended abstract Big Ramsey degrees of the generic partial order in the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol. 14, Springer, Cham, pages 637–643, 2021. [DOI]
  • Big Ramsey degrees and forbidden cycles (with David Chodounský, Jan Hubička, Matěj Konečný, Jaroslav Nešetřil, and Lluís Vena), the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol. 14, Springer, Cham, pages 436–441, 2021. [DOI]
  • On off-diagonal ordered Ramsey numbers of nested matchings (with Marian Poljak), Discrete Mathematics 346(2), Article 113223, 2023. [DOI | presentation]
    • Extended abstract in the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol. 14, Springer, Cham, pages 241–247, 2021. [DOI]
  • Tight bounds on the expected number of holes in random point sets (with Manfred Scheucher and Pavel Valtr), Random Structures & Algorithms 62(1), pages 29–51, 2023. [DOI]
    • Extended abstract in the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol. 14, Springer, Cham, pages 411–416, 2021. [DOI]
    • Extended abstract in the proceedings of the 37th European Workshop on Computational Geometry (EuroCG 2021), pages 2:1–2:7, 2021. [booklet of abstracts]
  • Big Ramsey degrees of 3-uniform hypergraphs are finite (with David Chodounský, Jan Hubička, Matěj Konečný, and Lluís Vena), Combinatorica 42(5), pages 659–672, 2022. [DOI | preliminary version]
  • On ordered Ramsey numbers of tripartite 3-uniform hypergraphs (with Máté Vizer), SIAM Journal on Discrete Mathematics 36(1), pages 214–228, 2022. [DOI]
    • Extended abstract in the proceedings of the European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2021), Trends in Mathematics, vol. 14, Springer, Cham, pages 142–147, 2021. [DOI]
  • Holes and islands in random point sets (with Manfred Scheucher and Pavel Valtr), Random Structures & Algorithms 60(3), pages 308–326, 2022. [DOI | preliminary version | presentation]
    • Conference version in the Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), Leibniz International Proceedings in Informatics (LIPIcs) 164, pages 14:1–14:16, 2020. [DOI]
    • Extended abstract in the proceedings of the 36th European Workshop on Computational Geometry (EuroCG 2020), pages 19:1–19:6, 2020. [booklet of abstracts]
  • Hypergraph based Berge hypergraphs (with Dániel Gerbner, Dong Yeap Kang, Younjin Kim, and Cory Palmer), Graphs and Combinatorics 38(1), Article 11, 2022. [DOI | preliminary version]
  • Big Ramsey degrees of 3-uniform hypergraphs (with David Chodounský, Jan Hubička, Matěj Konečný, and Lluís Vena), Acta Mathematica Universitatis Comenianae 88(3), pages 415–422, 2019. [link | preliminary version]
  • Edge-ordered Ramsey numbers (with Máté Vizer), European Journal of Combinatorics 87, Article 103100, 2020. [DOI]
    • Extended abstract in Acta Mathematica Universitatis Comenianae 88(3), pages 409–414, 2019. [link]
  • On Erdős–Szekeres-type problems for k-convex point sets (with Sujoy Bhore, Leonardo Martínez-Sandoval, and Pavel Valtr), European Journal of Combinatorics 89, Article 103157, 2020. [DOI]
    • Conference version in the Proceedings of the 30th International Workshop on Combinatorial Algorithms (IWOCA 2019), Lecture Notes in Computer Science, vol. 11638, Springer, Cham, pages 35–47, 2019. [DOI]
  • Minimal representations of order types by geometric graphs (with Oswin Aichholzer, Michael Hoffmann, Jan Kynčl, Wolfgang Mulzer, Irene Parada, Alexander Pilz, Manfred Scheucher, Pavel Valtr, Birgit Vogtenhuber, and Emo Welzl), Journal of Graph Algorithms and Applications 24(4), pages 551–572, 2020. [DOI]
    • Conference version in the Proceedings of the 27th International Symposium on Graph Drawing & Network Visualization (Graph Drawing 2019), Lecture Notes in Computer Science, pages 101–113, 2019. [DOI]
    • Extended abstract in the proceedings of the 34th European Workshop on Computational Geometry (EuroCG 2018), pages 21:1–21:6, 2018. [booklet of abstracts]
  • Ramsey numbers and monotone colorings, Journal of Combinatorial Theory, Series A 163, pages 34–58, 2019. [DOI | presentation]
  • Almost-equidistant sets (with Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr), Graphs and Combinatorics 36(3), pages 729–754, 2020. [DOI | data]
    • Extended abstract in the proceedings of the 34th European Workshop on Computational Geometry (EuroCG 2018), pages 19:1–19:6, 2018. [booklet of abstracts]
  • Induced Ramsey-type results and binary predicates for point sets (with Jan Kynčl, Stefan Langerman, and Alexander Pilz), The Electronic Journal of Combinatorics 24(4), P4.24, 22 pages, 2017. [DOI | presentation]
    • Extended abstract in Electronic Notes in Discrete Mathematics 61, pages 77–83, 2017. [DOI]
  • A superlinear lower bound on the number of 5-holes (with Oswin Aichholzer, Thomas Hackl, Jan Kynčl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber), Journal of Combinatorial Theory, Series A 173, Article 105236, 2020. [DOI | data | presentation]
    • Conference version in the Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Leibniz International Proceedings in Informatics (LIPIcs) 77, pages 8:1–8:16, 2017. [DOI]
    • Extended abstract in the (informal) proceedings of the 33rd European Workshop on Computational Geometry (EuroCG 2017), pages 69–72, 2017.
  • Covering lattice points by subspaces and counting point-hyperplane incidences (with Josef Cibulka and Pavel Valtr), Discrete & Computational Geometry 61(2), pages 325–354, 2019. [DOI | presentation]
    • Conference version in the Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Leibniz International Proceedings in Informatics (LIPIcs) 77, pages 12:1–12:16, 2017. [DOI]
  • Holes in 2-convex point sets (with Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr, and Birgit Vogtenhuber), Computational Geometry: Theory and Applications 74, pages 38–49, 2018. [DOI | presentation]
    • Conference version in the Proceedings of the 28th International Workshop on Combinatorial Algorithms (IWOCA 2017), Lecture Notes in Computer Science, vol. 10765, Springer, Cham, pages 169–181, 2018. [DOI]
    • Extended abstract in the proceedings of the 32nd European Workshop on Computational Geometry (EuroCG 2016), pages 263–266, 2016. [booklet of abstracts]
  • On ordered Ramsey numbers of bounded-degree graphs (with Vít Jelínek and Pavel Valtr), Journal of Combinatorial Theory, Series B 134, pages 179–202, 2019. [DOI | presentation]
  • Drawing graphs using a small number of obstacles (with Josef Cibulka and Pavel Valtr), Discrete & Computational Geometry 59(1), pages 143–164, 2018. [DOI | presentation]
    • Conference version in the Proceedings of the 23rd International Symposium on Graph Drawing & Network Visualization (Graph Drawing 2015), Lecture Notes in Computer Science, pages 360–372, 2015. [DOI | best paper award]
  • Bounding the pseudolinear crossing number of Kn via simulated annealing (with Jan Kynčl), extended abstract in the (informal) Proceedings of the XVI Spanish Meeting on Computational Geometry, pages 37–40, 2015. [booklet of abstracts | data | presentation]
  • A SAT attack on the Erdős–Szekeres conjecture (with Pavel Valtr), European Journal of Combinatorics 66, pages 13–23, 2017. [DOI | data | presentation]
    • Extended abstract in Electronic Notes in Discrete Mathematics 49, pages 425–431, 2015. [DOI]
  • On the Beer index of convexity and its variants (with Vít Jelínek, Pavel Valtr, and Bartosz Walczak), Discrete & Computational Geometry 57(1), pages 179–214, 2017. [DOI | presentation]
    • Conference version in the Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015), Leibniz International Proceedings in Informatics (LIPIcs) 34, pages 406–420, 2015. [DOI]
  • Ramsey numbers of ordered graphs (with Josef Cibulka, Karel Král, and Jan Kynčl), The Electronic Journal of Combinatorics 27(1), P1.16, 32 pages, 2020. [DOI | presentation]
    • Extended abstract in Electronic Notes in Discrete Mathematics 49, pages 419–424, 2015. [DOI]
  • Crossing numbers and combinatorial characterization of monotone drawings of Kn (with Radoslav Fulek and Jan Kynčl), Discrete & Computational Geometry 53(1), pages 107–143, 2015. [DOI | presentation]
    • Monotone crossing number of complete graphs (with Radoslav Fulek and Jan Kynčl), extended abstract in the (informal) Proceedings of the XV Spanish Meeting on Computational Geometry, pages 127–130, 2013. [booklet of abstracts]
  • Bounded representations of interval and proper interval graphs (with Pavel Klavík and Yota Otachi), Algorithms and Computation (ISAAC 2013), Lecture Notes in Computer Science 8283, pages 535–546, 2013. [DOI]
  • Grid representations and the chromatic number, Computational Geometry: Theory and Applications 46(8), pages 990–1002, 2013. [DOI]
    • Reprint in Computational Geometry: Theory and Applications 47(3), pages 480–492, 2014. [DOI]
    • Extended abstract in the proceedings of the 28th European Workshop on Computational Geometry (EuroCG 2012), pages 45–48, 2012. [booklet of abstracts]
    • Conference version Grid drawings and the chromatic number in the Proceedings of the 20th International Symposium on Graph Drawing (Graph Drawing 2012), Lecture Notes in Computer Science 7704, pages 315–326, 2013. [DOI]
Valid XHTML 1.0 Transitional