Publications and Preprints

Tibor Szabó

Institute of Mathematics
Freie Universität Berlin

Slow bootstrap percolation II: Accelerating properties (with D. Fabian and P. Morris), submitted.

Slow bootstrap percolation I: Cycles (with D. Fabian and P. Morris), submitted.

Improved integrality gap in max-min allocation: or Topology at the North Pole (with P. Haxell), submitted. An extended abstract appeared at the ACM-SIAM Symposium on Discrete Algorithms (SODA 2023).

New Ramsey-multiplicity bounds and search heuristics (with O. Parczyk, S. Pokutta, and Ch. Spiegel), submitted. An extended abstract appeared at the 37th AAAI Conference on Artificial Intelligence (presentation), 2023.

Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets (with M. Anastos, D. Fabian, A. Müyesser), Electronic Journal of Combinatorics, 30 (2023), Article P3.10.

The automorphism group of projective norm graphs (with T. Bayer T. Mészáros, L. Rónyai), Applicable Algebra in Engineering, Communication and Computation (2023). https://doi.org/10.1007/s00200-022-00590-3.

Subgraphs of the projective norm graph (with T. Bayer T. Mészáros, L. Rónyai), submitted.

Oriented cycles in digraphs of large outdegree (with L. Gishboliner, R. Steiner), Combinatorica, 42, (2022), 1145-1187.

Dichromatic number and forced subdivisions (with L. Gishboliner, R. Steiner), Journal of Combinatorial Theory, Series B, 153 (2022), 1-30.

Majority colorings of sparse digraphs (with M. Anastos, A. Lamaison, R. Steiner), Electronic Journal of Combinatorics, 28 (2021), Article P2.31.

The maximum length of Kr-bootstrap percolation (with J. Balogh, G. Kronenberg, A. Pokrovskiy), Proceedings of the American Mathematical Society to appear.

On the Odd Cycle Game and Connected Rules (with J. Corsten, A. Mond, A. Pokrovskiy, Ch. Spiegel), European Journal of Combinatorics, 89 (2020), Article 103140.

Ryser's Conjecture for t-intersecting hypergraphs (with A. Bishnoi, S. Das, P. Morris), Journal of Combinatorial Theory (Series A) 179 (2021), Article 105366.

List Ramsey numbers (with N. Alon, M. Bucić, T. Kalvari, E. Kuperwasser), Journal of Graph Theory 96(1) (2021), 109-128.

Enumerating extensions of mutually orthogonal Latin squares (with S. Boyadzhiyska, S. Das), Designs Codes and Cryptography 88 (2020), 2187-2206.

On the optimality of the uniform random strategy (with Ch. Kusch, J. Rue, Ch. Spiegel), Random Structures and Algorithms 55 (2019), 371-401.

A family of extremal hypergraphs for Ryser's conjecture (with A. Abu-Khazneh, J. Barát, A. Pokrovskiy), Journal of Combinatorial Theory, Series A 161 (2019), 164-177.

Extremal hypergraphs for Ryser's conjecture (with P. Haxell, L. Narins), Journal of Combinatorial Theory, Series A, 158 (2018), 492-547.

Vertex Folkman numbers and the minimum degree of minimal Ramsey graphs (with H. Hàn, V. Rödl), SIAM Journal on Discrete Mathematics, 32(2) (2018), 826-838.

Graphs without proper subgraphs of minimum degree 3 and short cycles (with L. Narins, A. Pokrovskiy), Combinatorica 37(3) (2017), 495-519.

Sharp thresholds for half-random games II. (with J. Groschwitz) Graphs and Combinatorics 33 (2017), 387-401.

On the minimum degree of minimal Ramsey graphs for multiple colours (with J.Fox, A. Grinshpun, A. Liebenau, Y. Person), Journal of Combinatorial Theory (Series B), 120 (2016), 64-82.

The Local Lemma is tight for SAT (with H. Gebauer, G. Tardos), Journal of the ACM 63(5) (2016), No. 43.
An extended abstract appeared in 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)(2011), 664-674.

Sharp thresholds for half-random games I. (with J. Groschwitz), Random Structures and Algorithms, 49(4) (2016), 766-794.

Free edge lengths in plane graphs (with Z. Abel, R. Connelly, S. Eisenstat, R. Fulek, F. Morić, Y. Okamoto, Cs. Tóth), Discrete \& Computational Geometry, 54(1) (2015), 259-289.
An extended abstract appeared in Proc. 30th Annual Symposium on Computational Geometry (SoCG 2014, Kyoto), ACM Press, 426-435.

On the concentration of the domination number of the random graph (with R. Glebov, A. Liebenau), SIAM Journal of Discrete Mathematics, 29(3) (2015), 1186-1206.

What is Ramsey equivalent to a clique? (with J. Fox, A. Grinshpun, A. Liebenau, Y. Person), Journal of Combinatorial Theory (Series B), 109 (2014), 120-133.

On the rank of higher inclusion matrices (with C. Grosu, Y. Person), Journal of the London Mathematical Society, 90 (2014) 333-349.

Positional Games (with D. Hefetz, M. Krivelevich, M. Stojaković), Oberwolfach Seminars, Volume 44, Springer, 2014.

How many colors guarantee a rainbow matching? (with R. Glebov, B. Sudakov), Electronic Journal of Combinatorics 21(1) (2014), P1.27.

On conflict-free coloring of graphs (with R. Glebov, G. Tardos), Combinatorics, Probability, and Computing, 23(2014), 434-448.

On covering expander graphs with Hamilton cycles (with R. Glebov, M. Krivelevich), Random Structures and Algorithms, 44(2014), 183-200.

Sharp threshold for the appearance of certain spanning trees in random graphs (with D. Hefetz, M. Krivelevich), Random Structures and Algorithms 41(2012), 391-412.

Bounded transversals in multipartite graphs (with R. Berke, P. Haxell), Journal of Graph Theory 70(2012) 318-331.

Global Maker-Breaker games on sparse graphs (with D. Hefetz, M. Krivelevich, M. Stojaković), European Journal of Combinatorics, 32(2011), 162-177.

On the minimum degree of minimal Ramsey graphs (with P. Zumstein, S. Zürcher), Journal of Graph Theory, 64(2010), 150-164.

Avoider-Enforcer: the rules of the game (with D. Hefetz, M. Krivelevich, M. Stojaković), Journal of Combinatorial Theory (Series A), 117 (2010), 152-163.

Asymptotic random graph intuition for the biased connectivity game (with H. Gebauer), Random Structures and Algorithms , 35 (2009), 431-443.

A sharp threshold for the Hamilton cycle Maker-Breaker game (with D. Hefetz, M. Krivelevich, M. Stojaković), Random Structures and Algorithms, 34 (2009) 112-122.

Vizing's Conjecture for chordal graphs (with R. Aharoni) Discrete Mathematics, 309 (2009), 1766-1768.

Hamilton cycles in highly connected and expanding graphs (with D. Hefetz, M. Krivelevich), Combinatorica ,29 (2009), 547-568.

Deciding relaxed two-colorability --- a hardness jump (with R. Berke), Combinatorics, Probability, and Computing, 18 (2009), 53-81.
An extended abstract appeared in Proc. 14th Annual European Symposium on Algorithms (ESA), (2006) 124-135.

Fast winning strategies in Maker-Breaker games (with D. Hefetz, M. Krivelevich, M. Stojaković), Journal of Combinatorial Theory (Series B), 99 (2009), 39-47.

Fast winning strategies in Avoider-Enforcer games (with D. Hefetz, M. Krivelevich, M. Stojaković) Graphs and Combinatorics, 25(2009), 533-544.

How long can a graph be kept planar? (with V. Anuradha, C. Jain, J. Snoeyink), Electronic Journal of Combinatorics, 15(1) (2008), N14.
An extended abstract appeared at the 17th Fall Workshop on Computational and Combinatorial Geometry.

Biased positional games and small hypergraphs with large covers (with M. Krivelevich) Electronic Journal of Combinatorics, 15(1) (2008), R70.

Planarity, coloring and minor games (with D. Hefetz, M. Krivelevich, M. Stojaković), SIAM Journal on Discrete Mathematics, 22 (2008), 194-212.

Turán's theorem in the hypercube (with N. Alon, A. Krech), SIAM Journal on Discrete Mathematics, 21 (2007), 66-72.

Bart-Moe games, JumbleG and Discrepancy (with D. Hefetz, M. Krivelevich), European Journal of Combinatorics, 28, (2007), 1131-1143.

Avoider-Enforcer games (with D. Hefetz, M. Krivelevich), Journal of Combinatorial Theory (Series A), 114 (2007), 840-853.

Relaxed two-coloring of cubic graphs (with R. Berke), Journal of Combinatorial Theory (Series B), 97 (2007), 652-668.
An extended abstract appeared in European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB) (2005) 341-344.

RANDOM EDGE can be exponential on abstract cubes, (with J. Matoušek) Advances in Mathematics, 204(2006) 262-277.
An extended abstract appeared in Proc. 45nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), (2004), 92-100.

Odd independent transversals are odd, (with P. Haxell) Combinatorics, Probability and Computing, 15 (2006), 193-211.

Extremal problems for transversals in graphs with bounded degree, (with G. Tardos), Combinatorica, 26 (2006) 333-351.

The game of JumbleG, (with A. Frieze, M. Krivelevich, O. Pikhurko), Combinatorics, Probability and Computing, 14 (2005) 783-793.

Jumping doesn't help in abstract cubes, (with I. Schurr) Eleventh Conference on Integer Programming and Combinatorial Optimization (IPCO) (2005), 225-235.

Discrepancy games (with N. Alon, M. Krivelevich, J. Spencer), Electronic Journal of Combinatorics, 12(2005), R51.

Positional games on random graphs, (with M. Stojaković) Random Structures & Algorithms, 26 (2005) 204--223.

A generalization of Turán's theorem, (with B. Sudakov and V.H. Vu), Journal of Graph Theory, 49 (2005), 187-195.

Exact k-wise intersection theorems, (with V.H. Vu), Graphs and Combinatorics, 21 (2005), 247-261.

Triangle factors in sparse pseudorandom graphs, (with M. Krivelevich, B. Sudakov), Combinatorica, 24 no.3. (2004) 403-426.

Finding the sink takes some time, (with I. Schurr), Discrete and Computational Geometry, 31 (2004) 627-642.
An extended abstract appeared in Proc. 10th European Symposium on Algorithms (ESA), Lecture Notes in Computer Science 2461 (2002) 833-844.

On the spectrum of projective norm-graphs, Information Processing Letters, 86 no. 2. (2003) 71-74.

Bounded size components -- partitions and transversals, (with P. Haxell, G. Tardos), Journal of Combinatorial Theory, (Series B), 88 no.2. (2003) 281-297.

Turán's theorem in sparse random graphs, (with V.H. Vu) Random Structures & Algorithms, 23 no.3. (2003) 225-234.

Unique sink orientations of cubes, (with E. Welzl), Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science (FOCS), (2001) 547-555.

A multidimensional generalization of the Erdős-Szekeres lemma on monotone subsequences, (with G. Tardos), Combinatorics, Probability and Computing, 10 (2001), 557-565.

Norm-graphs: Variations and Applications, (with N. Alon and L. Rónyai) Journal of Combinatorial Theory, (Series B), 76 (1999), 280-290.

On Erdős' Eulerian Trail Game, (with Á. Seress) Graphs and Combinatorics, 15 (1999), 233-237.

Intersection Properties of Subsets of Integers, European Journal of Combinatorics, 20 (1999), 429-444.

On Nearly Regular Co-critical Graphs, Discrete Mathematics, 160 (1996) 279-281.

Norm-graphs and Bipartite Turán Numbers (with J. Kollár and L. Rónyai), Combinatorica, 16 (1996), no. 3, 399-406.
An extended abstract appeared in Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs, (with L. Babai, A. Gál, J. Kollár, L. Rónyai and A. Wigderson) Proc. of the twenty-eighth Annual ACM Symposium on the Theory of Computing (STOC), (1996), 603-611.

Dense Graphs with Cycle Neighborhoods (with Á. Seress), Journal of Combinatorial Theory (Series B), 63 (1995) 281-293.

Last modified: Sat Feb 4 18:01:15 CET 2023