Martin Balko

---

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

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

• Winter term 2024/2025 (Zimní semestr 2024/2025):
  • Algorithmic game theory - lecture, Friday, 10:40am, S3
  • Algorithmic game theory - tutorial, Monday, 12:20pm, S11
  • Geometric seminar - seminar, Tuesday, 10:40am, S8
  • Kombinatorika a grafy 1 - cvičení, pátek, 9:00, S11

• Ročníkové projekty a práce

• Past teaching (Minulá výuka)

Short CV:	up

• Associate professor at the Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague (2023+),
• Assistant professor at the Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague (2018-2023),
• Postdoctoral researcher at the Department of Computer Science, Faculty of Natural Sciences, Ben Gurion University of the Negev, Beer Sheva (2017-2018),
• Postdoctoral researcher at the Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Budapest (2016-2017),
• Part-time researcher at the Center of Excellence - Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Prague (2013-2018),
• University: Faculty of Mathematics and Physics, Charles University in Prague,
  • Examen rigorosum (RNDr., 2017),
  • Doctoral degree (Ph.D., 2012-2016): Discrete Models and Algorithms,
  • Master's degree (Mgr., 2010-2012): Discrete Models and Algorithms,
  • Bachelor's degree (Bc., 2007-2010): General Computer Science,
• Secondary school (2003-2007): Gymnázium Žatec.

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

• Implementation of Sprouts: a graph drawing game (with Tomáš Čížek), in preparation.
  • Conference version to appear in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (Graph Drawing 2021), 2021.
• 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), in preparation.
  • 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 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), submitted, 2021.
  • 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), submitted.
  • 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), to appear in Combinatorica, 2021. [preliminary version]
• On ordered Ramsey numbers of tripartite 3-uniform hypergraphs (with Máté Vizer), submitted.
  • 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), to appear in Random Structures & Algorithms, 2021. [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), to appear in Graphs and Combinatorics, 2021. [preliminary version]
• Big Ramsey degrees of 3-uniform hypergraphs (with David Chodounský, Jan Hubička, Matěj Konečný, and Lluís Vena), in preparation. [preliminary version]
  • Extended abstract in Acta Mathematica Universitatis Comenianae 88(3), pages 415–422, 2019. [link]
• Edge-ordered Ramsey numbers (with Máté Vizer), European Journal of Combinatorics 87, pages 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, pages 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), the Journal of Graph Algorithms and Applications 24(4), pages 551–572, 2020. [DOI]
  • Conference version in the Proceedings of 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, pages 729–754, 2020. [DOI | supplementary 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, Issue 4, P4.24, 22 pages, 2017. [link | 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, pages 105236, 2020. [DOI | supplementary 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]
• Covering lattice points by subspaces and counting point-hyperplane incidences (with Josef Cibulka and Pavel Valtr), Discrete and Computational Geometry 62(1), 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, Birgit Vogtenhuber, and Pavel Valtr), 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 32th 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 and Computational Geometry 59(1), pages 143–164, 2018. [DOI | presentation]
  • Conference version in the Proceedings of 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 K_n 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 | supplementary data | presentation]
• A SAT attack on the Erdős–Szekeres conjecture (with Pavel Valtr), European Journal of Combinatorics 66, pages 13–23, 2017. [DOI | supplementary 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 and 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, Issue 1, P1.16, 32 pages, 2020. [link | supplementary data | presentation].
  • Extended abstract in Electronic Notes in Discrete Mathematics 49, pages 419–424, 2015. [DOI]
• Crossing numbers and combinatorial characterization of monotone drawings of K_n (with Radoslav Fulek and Jan Kynčl), Discrete and 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), Lecture Notes in Computer Science, ISAAC, pages 8283-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 in the Proceedings of the 12th International Symposium on Graph Drawing (Graph Drawing 2012), Lecture Notes in Computer Science 7704, pages 315–326, 2013. [DOI]

ORCID®: orcid.org/0000-0001-9688-9489