Articles published by the members of the Combinatorics Group


2024

  • Reinhard Diestel, Christian Elbracht, Joshua Erde, and Max Teegen, Duality and tangles of set separations, Journal of Combinatorics 15 (1) (2024).

  • Sahar Diskin, Joshua Erde, Mihyun Kang, and Michael Krivelevich, Percolation on irregular high-dimensional product graphs, Combinatorics, Probability and Computing, 33(3):377-403, 2024.

  • Sahar Diskin, Joshua Erde, Mihyun Kang, and Michael Krivelevich, Isoperimetric inequalities and supercritical percolation on high-dimensional product graphs, Combinatorica (2024), to appear.

  • Tuan Anh Do, Joshua Erde, and Mihyun Kang, A note on the width of sparse random graphs, Journal of Graph Theory (2024), to appear.

  • Joshua Erde, Mihyun Kang, Florian Lehner, Bojan Mohar, and Dominik Schmid, Catching a robber on a random k-uniform hypergraph, Canadian Journal of Mathematics (2024), to appear.


2023

  • Ben Barber, Joshua Erde, Peter Keevash, and Alexander Roberts, Isoperimetric stability in lattices, Proceedings of the American Mathematical Society 151 (2023).

  • Nathan Bowler, Christian Elbracht, Joshua Erde, J. Pascal Gollin, Karl Heuer, Max Pitz and Max Teegen, Ubiquity of graphs with nowhere-linear end structure, Journal of Graph Theory 103 (3) (2023), 564-598.

  • Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, and Jean Bernoulli Ravelomanana, The sparse parity matrix, Advances in Combinatorics 2023:5, 68pp.

  • Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, and Maurice Rolvien, The k-XORSAT threshold revisited, In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (EuroComb'23), 298-304.

  • Tuan Anh Do, Joshua Erde, Mihyun Kang, and Michael Missethan, Component behaviour and excess of random bipartite graphs near the critical point, Electron. J. Combin. 30 (2023), #P3.7.

  • Joshua Erde, Mihyun Kang, and Michael Krivelevich, Expansion in supercritical random subgraphs of the hypercube and its consequences, Annals of Probability 51 (1) (2023), 127-156.

  • Joshua Erde, Mihyun Kang, Florian Lehner, Bojan Mohar, and Dominik Schmid, Cop number of random k-uniform hypergraphs, In Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications (EuroComb'23), 416-424.

  • Mikhail Isaev and Mihyun Kang, On the chromatic number in the stochastic block model, Electron. J. Combin. 30 (2023), #P2.56.

  • Mihyun Kang and Michael Missethan, The early evolution of the random graph process in planar graphs and related classes, SIAM J. Discrete Math. 37-1 (2023), 146-162.


2022

  • Nathan Bowler, Christian Elbracht, Joshua Erde, J. Pascal Gollin, Karl Heuer, Max Pitz and Max Teegen, Topological ubiquity of trees, Journal of Combinatorial Theory, Series B 157 (2022), 70-95.

  • Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, and Jean Bernoulli Ravelomanana, The sparse parity matrix, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), 822-833.

  • Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel, Phase transition in cohomology groups of non-uniform random simplicial complexes, Electron. J. Combin. 29(2022), #P3.27.

  • Oliver Cooley, Mihyun Kang, and Oleg Pikhurko, On a question of Vera T Sos about size forcing of graphons, Acta Math. Hungar. 168 (2022), 1-26.

  • Oliver Cooley, Mihyun Kang, and Julian Zalla, Loose cores and cycles in random hypergraphs, Electron. J. Combin. 29 (2022), #P4.13.

  • Tuan Anh Do, Joshua Erde, and Mihyun Kang, Planarity and genus of sparse random bipartite graphs, SIAM Journal on Discrete Mathematics 36-2 (2022), 1394-1415.

  • Joshua Erde, and Florian Lehner, Hamiltonian decompositions of 4-regular Cayley graphs of infinite abelian groups, Journal of Graph Theory 101 (3) (2022), 559-571.

  • Mihyun Kang and Michael Missethan, Concentration of maximum degree in random planar graphs, Journal of Combinatorial Theory, Series B (2022), 1394-1415.

  • Mihyun Kang and Michael Missethan, The early evolution of the random graph process in planar graphs and related classes, SIAM J. Discrete Math. 37-1 (2023), 146-162.

  • Mihyun Kang and Michael Missethan, Longest and shortest cycles in random planar graphs, Random Structures and Algorithms 60 (2022), 462-505.


2021

  • Nathan Bowler, Joshua Erde, Florian Lehner, and Max Pitz, Bounding the cop number of a graph by its genus, SIAM Journal on Discrete Mathematics 35-4 (2021), 2459-2489.

  • Oliver Cooley, Nemanja Draganic, Mihyun Kang, and Benny Sudakov, Large induced matchings in random graphs, SIAM J. Discrete Math. 35-1 (2021), 267-280.

  • Oliver Cooley, Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicolas Sanhueza-Matamala, and Julian Zalla, Longest paths in random hypergraphs, SIAM J. Discrete Math. 35-4 (2021), 2430-2458.

  • Oliver Cooley, Mihyun Kang, and Oleg Pikhurko, On a question of Vera T. Sos about size forcing of graphons (extended abstract), Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.

  • Oliver Cooley, Mihyun Kang, and Julian Zalla, Loose cores and cycles in random hypergraphs (extended abstract), Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.

  • Tuan Anh Do, Joshua Erde, and Mihyun Kang, Component behaviour of random bipartite graphs, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.

  • Chris Dowden, Mihyun Kang, Mirjana Mikalacki, and Milos Stojakovic, The game of Toucher and Isolator, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.

  • Joshua Erde, J. Pascal Gollin, Attila Joó, Enlarging vertex-flames in countable digraphs, Journal of Combinatorial Theory, Series B 151 (2021), 263-281.

  • Joshua Erde, J. Pascal Gollin, Attila Joó, Paul Knappe, and Max Pitz, Base partition for finitary-cofinitary matroid families, Combinatorica 41 (2021), 31-52.

  • Joshua Erde, J. Pascal Gollin, Atilla Joó, Paul Knappe, and Max Pitz, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs, Journal of Combinatorial Theory, Series B 149 (2021), 1-12.

  • Joshua Erde and Florian Lehner, Improved bounds on the cop number of a graph drawn on a surface, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.

  • Joshua Erde, Mihyun Kang, and Michael Krivelevich, Large complete minors in random subgraphs, Combinatorics, Probability and Computing 30 (2021), 619-630.

  • Wenjie Fang, Hsien-Kuei Hwang, and Mihyun Kang, Phase transitions from exp(n^{1/2}) to exp(n^{2/3}) in the asymptotics of banded plane partitions, Journal of Combinatorial Theory, Series A 178 (2021), 105363.

  • Mihyun Kang and Michael Missethan, Cut vertices in random planar graphs, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.


2020

  • Oliver Cooley, Wenjie Fang, Nicola Del Giudice, and Mihyun Kang, Subcritical random hypergraphs, high-order components, and hypertrees, SIAM Journal on Discrete Mathematics SIAM Journal on Discrete Mathematics 34 (2020), 2033-2062.

  • Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel, Vanishing of cohomology groups of random simplicial complexes, Random Structures and Algorithms 56 (2020), 461-500.

  • Oliver Cooley and Abraham Gutiérrez, Multi-coloured jigsaw percolation on random graphs, Journal of Combinatorics 11 (2020), 603-624.

  • Chris Dowden, Mihyun Kang, and Michael Krivelevich, The genus of the Erdos-Renyi random graph and the fragile genus property, Random Structures and Algorithms 56 (2020), 97-121.

  • Joshua Erde, Directed path-decompositions, SIAM Journal on Discrete Mathematics 34 (2020), 415–430.

  • Joshua Erde, Florian Lehner, and Max Pitz, Hamilton decompositions of one-ended Cayley graphs, Journal of Combinatorial Theory, Series B, Volume 140, (2020) 171-191.

  • Nikolaos Fountoulakis, Mihyun Kang, and Tamas Makai, Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs, Random Structures and Algorithms 57 (2020), 1134-1156.

  • Jason Gao and Mihyun Kang, Counting cubic maps with large genus, Proceedings of the 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), Leibniz International Proceedings in Informatics 159 (2020), pp. 3:1-3:14.

  • Mihyun Kang, Tamas Makai, and Oleg Pikhurko, Supersaturation problem for the bowtie, European Journal on Combinatorics 88 (2020), 103107.

  • Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel, Phase transitions in graphs on orientable surfaces, Random Structures and Algorithms 56 (2020), 1117-1170.

  • Mihyun Kang and Michael Missethan, The giant component and 2-core in sparse random outerplanar graphs, Proceedings of the 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), Leibniz International Proceedings in Informatics 159 (2020), pp. 4:1-4:17.


2019

  • Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch, Core forging and local limit theorems for the k-core of random graphs, Journal of Combinatorial Theory, Series B 137 (2019), 178-231.

  • Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel, Cohomology groups of non-uniform random simplicial complexes, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2019), Acta Math. Univ. Comenianae Vol. LXXXVIII, 3 (2019), pp. 553-560.

  • Oliver Cooley, Wenjie Fang, Nicola Del Giudice, and Mihyun Kang, Subcritical random hypergraphs, high-order components, and hypertrees, Proceedings of Analytic Algorithmics and Combinatorics (ANALCO), SIAM 2019, pp. 111-118.

  • Oliver Cooley, Tobias Kapetanopoulos, and Tamás Makai, The sharp threshold for jigsaw percolation in random graphs, Advances in Applied Probability, 51 (2019), 378-407.

  • Oliver Cooley, Mihyun Kang, and Christoph Koch, The size of the giant component in random hypergraphs: a short proof, Electronic Journal of Combinatorics 26 (2019), #P3.6.

  • Reinhard Diestel, Joshua Erde, Daniel Weissauer, Structural submodularity and tangles in abstract separation systems, Journal of Combinatorial Theory, Series A 167 (2019), pp. 155-180.

  • Chris Dowden, Mihyun Kang, Mirjana Mikalacki, and Milos Stojakovic, The Toucher-Isolator game, Electronic Journal of Combinatorics (2019), #P4.6.

  • Chris Dowden, Mihyun Kang, Michael Mosshammer, and Philipp Sprüssel, The evolution of random graphs on surfaces of non-constant genus, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2019), Acta Math. Univ. Comenianae Vol. LXXXVIII, 3 (2019), pp. 631-636.

  • Joshua Erde, Daniel Weissauer, A short derivation of the structure theorem for graphs with excluded topological minors, SIAM Journal on Discrete Mathematics 33(4) (2019), pp. 1654-1661.


2018

  • Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang, Tobias Kapetanopoulos, Charting the replica symmetric phase, Communications in Mathematical Physics 359 (2018), 603-698.

  • Oliver Cooley, Mihyun Kang, and Christoph Koch, The size of the giant high-order component in random hypergraphs, Random Structures and Algorithms 53 (2018), 238-288.

  • Oliver Cooley, Mihyun Kang, and Yury Person, Largest components in random hypergraphs, Combinatorics, Probability and Computing 27 (2018), 741-762.

  • Chris Dowden, Mihyun Kang, and Michael Krivelevich, The genus of the Erdos-Renyi random graph and the fragile genus property, Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Leibniz International Proceedings in Informatics 110 (2018), pp. 17:1-17:13.

  • Chris Dowden, Mihyun Kang, Philipp Sprüssel, The evolution of random graphs on surfaces, SIAM Journal on Discrete Mathematics 32 (2018), 695-727.

  • Nikolaos Fountoulakis, Mihyun Kang, Christoph Koch, and Tamas Makai, A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs, Annals of Applied Probability 28 (2018), 990-1051.

  • Hsien-Kuei Hwang, Mihyun Kang, and Guan-Huei Duh, Asymptotic expansions for sub-critical Lagrangean forms, Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Leibniz International Proceedings in Informatics 110 (2018), pp. 29:1-29:13.

  • Wenjie Fang, Mihyun Kang, Michael Mosshammer, and Philipp Sprüssel, Cubic graphs and related triangulations on orientable surfaces, Electronic Journal of Combinatorics 25 (2018), #P1.30.

  • Mihyun Kang, Angélica Pachón, and Pablo Rodriguez, Evolution of a modified binomial random graph by agglomeration, Journal of Statistical Physics 170 (2018), 509-535.
  • Mihyun Kang and Philipp Sprüssel, Symmetries of unlabelled planar triangulations, Electronic Journal of Combinatorics 25 (2018), #P1.34.


2017

  • Béla Bollobás, Oliver Cooley, Mihyun Kang, and Christoph Koch, Jigsaw percolation on random hypergraphs, Journal of Applied Probability 54 (2017), 1261-1277.

  • Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch, How does the core sit inside the mantle?, Random Structures and Algorithms 51 (2017), 459-482.

  • Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch, The minimum bisection in the planted bisection model, Theory of Computing 13 (2017), 1-22.

  • Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang and Tobias Kapetanopoulos, Charting the replica symmetric phase, Proceedings of the 21th International Workshop on Randomization and Computation (RANDOM 2017), 40:1-40:17.

  • Oliver Cooley, Penny Haxell, Mihyun Kang and Philipp Sprüssel, Homological connectedness of random hypergraphs, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Electronic Notes in Discrete Mathematics 61 (2017), 279-285.

  • Chris Dowden, Mihyun Kang and Philipp Sprussel, The evolution of random graphs on surfaces, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Electronic Notes in Discrete Mathematics 61 (2017), 367-373.

  • Mihyun Kang, Tamas Makai and Oleg Pikhurko, Supersaturation Problem for the Bowtie, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Electronic Notes in Discrete Mathematics 61 (2017), 679-685.

  • Mihyun Kang, Michael Mosshammer, and Philipp Sprüssel, Evolution of the giant component in graphs on orientable surfaces, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Electronic Notes in Discrete Mathematics 61 (2017), 687-693.


2016

  • Oliver Cooley, Mihyun Kang, and Christoph Koch, Threshold and hitting time for high-order connectivity in random hypergraphs, Electronic Journal of Combinatorics 23 (2016), #P.48.

  • Chris Dowden, Extremal C4-free/C5-free planar graphs Journal of Graph Theory 83(3), 213-230 (2016).

  • Andrea Jiménez, Mihyun Kang, and Martin Loebl, Cubic bridgeless graphs and braces, Graphs and Combinatorics (2016). doi:10.1007/s00373-016-1722-y

  • Christoph Koch and Johannes Lengler, Bootstrap percolation on geometric inhomogeneous random graphs, Proceedings of the 43nd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Vol. 55. LIPIcs, Schloss Dagstuhl, Leibniz-Zent. Inform., 2016, 147:1-147:15.

  • Mihyun Kang and Tamas Makai, Bootstrap percolation on G(n,p) revisited, Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2016), 225-236.


2015

  • Ron Aharoni, Eli Berger and Philipp Sprüssel, Two disjoint independent bases in matroid-graph pairs, Graphs and Combinatorics 31 (2015), 1107-1116.

  • Ron Aharoni, Roi Holzma, David Howard and Philipp Sprüssel, Cooperative colorings and independent systems of representatives, Electronic Journal of Combinatorics 22 (2015), 14pp.

  • Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch, The minimum bisection in the planted bisection model, Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM'2015), Leibniz International Proceedings in Informatics (LIPIcs), pp. 710-725, 2015.

  • Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch, How does the core sit inside the mantle?, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb15), Electronic Notes in Discrete Mathematics (2015), pp. 489-496.

  • Oliver Cooley, Mihyun Kang, and Christoph Koch, Evolution of high-order connected components in random hypergraphs, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb15), Electronic Notes in Discrete Mathematics (2015), pp. 569-575.

  • Wenjie Fang, Mihyun Kang, Michael Mosshammer, and Philipp Sprüssel, Enumeration of cubic multigraphs on orientable surfaces, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb15), Electronic Notes in Discrete Mathematics (2015), pp. 603-610.

  • Mihyun Kang, Giant components in random graphs, in Recent Trends in Combinatorics, Andrew Beveridge et al. (eds.), The IMA Volumes in Mathematics and its Applications 159, Springer International Publishing Switzerland, 2015.

  • Mihyun Kang, Michal Karonski, Christoph Koch, and Tamas Makai, Properties of stochastic Kronecker graphs, Journal of Combinatorics 6 (2015), 395-432.

  • Mihyun Kang, Christoph Koch, and Tamas Makai, Bootstrap percolation in random k-uniform hypergraphs, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb15), Electronic Notes in Discrete Mathematics (2015), pp. 595-601.

  • Mihyun Kang, Christoph Koch, and Angélica Pachón, The phase transition in a multi-type binomial random graph, SIAM Journal on Discrete Mathematics 29 (2015), 1042-1064.

  • Mihyun Kang and Philipp Sprüssel, Charaterisation of symmetries of unlabelled triangulations, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb15), Electronic Notes in Discrete Mathematics (2015), pp.587-594.


2014

  • Michael Behrisch, Amin Coja-Oghlan, and Mihyun Kang, The asymptotic number of connected d-uniform hypergraphs, Combinatorics, Probability and Computing 23 (2014), 367-385.

  • Michael Behrisch, Amin Coja-Oghlan, and Mihyun Kang, Local limit theorems for the giant component of random hypergraphs, Combinatorics, Probability and Computing 23 (2014), 331-366.

  • Mihyun Kang, Random Graphs: from Nature to Society to the Brain, a special issue of the Mathematical Intelligencer to SEOUL ICM 2014, Springer, 42-44.

  • Mihyun Kang, Angelica Pachon and Pablo Rodriguez, Connectivity for a modified binomial random graph by agglomeration, Proceedings of the 25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA2014), DMTCS proc. BA, 2014, pp. 217-228.

  • Mihyun Kang and Konstantinos Panagiotou, On the connectivity threshold of Achlioptas processes, Journal of Combinatorics 5 (2014), 291-304.

  • Mihyun Kang and Zdeněk Petrášek, Random Graphs: Theory and Applications from Nature to Society to the Brain, Internationale Mathematische Nachrichten, Nr. 227 (2014), 1-24.


2013

  • Andrea Jiménez, Mihyun Kang and Martin Loebl, Directed cycle double covers: hexagon graphs, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb13), CRM Series 16 (2013), pp. 147-151.

  • Mihyun Kang and Konstantinos Panagiotou, On the connectivity of random graphs from addable classes, Journal of Combinatorial Theory, Series B103 (2013) 306-312.

  • Mihyun Kang, Will Perkins, and Joel Spencer, The Bohman-Frieze process near criticality, Random Structures and Algorithms 43 (2013), 221-250.


2012

  • Reinhard Diestel and Philipp Sprüssel, Locally finite graphs with ends: A topological approach. III. Fundamental group and homology, Discrete Mathematics 312 (2012), 21-29.

  • Mihyun Kang, The 2012 Abel laureate Endre Szemerédi and his celebrated work, Internationale Mathematische Nachrichten, Nr. 221 (2012), 1-19.

  • Mihyun Kang and Tomasz Łuczak, Two critical periods in the evolution of random planar graphs, Transactions of the American Mathematical Society 364 (2012), 4239-4265.