@article{20422, abstract = {We show that if n is odd and p>=Clog n/n, then with high probability Hamilton cycles in G(n,p) span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with odd n vertices and minimum degree n/2+C for sufficiently large constant C, span its cycle space. }, author = {Christoph, Micha and Nenadov, Rajko and Petrova, Kalina H}, issn = {1096-0902}, journal = {Journal of Combinatorial Theory Series B}, pages = {254--267}, publisher = {Elsevier}, title = {{The Hamilton space of pseudorandom graphs}}, doi = {10.1016/j.jctb.2025.09.002}, volume = {176}, year = {2026}, } @article{20482, abstract = {In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs H in Kn, defined as the minimum number of colours needed to colour the edges of K so that every copy of a graph H E H intersects some colour class in an odd number of edges. In this paper, we focus on complete bipartite graphs. First, we completely resolve the problem when H is the family of all spanning complete bipartite graphs on n vertices. We then focus on its subfamilies, that is, {Kt,n-t : t E T} for a fixed set of integers T c [[n/2]]. We prove that the odd-Ramsey problem is equivalent to determining the maximum dimension of a linear binary code avoiding codewords of given weights, and leverage known results from coding theory to deduce asymptotically tight bounds in our setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is, non-spanning) complete bipartite subgraphs.}, author = {Boyadzhiyska, Simona and Das, Shagnik and Lesgourgues, Thomas and Petrova, Kalina H}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Odd-Ramsey numbers of complete bipartite graphs}}, doi = {10.1016/j.ejc.2025.104235}, volume = {131}, year = {2026}, } @article{19418, abstract = {The size-Ramsey number r^(H) of a graph H is the smallest number of edges a (host) graph G can have, such that for any red/blue colouring of G, there is a monochromatic copy of H in G. Recently, Conlon, Nenadov and Trujić showed that if H is a graph on n vertices and maximum degree three, then r^(H)=O(n8/5), improving upon the upper bound of n5/3+o(1) by Kohayakawa, Rödl, Schacht and Szemerédi. In this paper we show that r^(H)≤n3/2+o(1). While the previously used host graphs were vanilla binomial random graphs, we prove our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods.}, author = {Draganić, Nemanja and Petrova, Kalina H}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {3}, publisher = {Wiley}, title = {{Size‐Ramsey numbers of graphs with maximum degree three}}, doi = {10.1112/jlms.70116}, volume = {111}, year = {2025}, } @article{19503, abstract = {A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 1996 and again in 2006, asks whether for every pair of integers s,t≥1 there exists a finite number F(s,t) such that the vertex set of every digraph of minimum out-degree at least F(s,t) can be partitioned into non-empty parts A and B such that the subdigraphs induced on A and B have minimum out-degree at least s and t , respectively. In this short note, we prove that if F(2,2) exists, then all the numbers F(s,t) with s,t≥1 exist and satisfy F(s,t)=Θ(s+t) . In consequence, the problem of Alon and Stiebitz reduces to the case s=t=2 . Moreover, the numbers F(s,t) with s,t≥2 either all exist and grow linearly, or all of them do not exist.}, author = {Christoph, Micha and Petrova, Kalina H and Steiner, Raphael}, issn = {1469-2163}, journal = {Combinatorics Probability and Computing}, number = {4}, pages = {559--564}, publisher = {Cambridge University Press}, title = {{A note on digraph splitting}}, doi = {10.1017/S0963548325000045}, volume = {34}, year = {2025}, } @article{19603, abstract = {MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famousEdwards-Erdös bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2 + n−1/4 . Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdös bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f (k) · O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdös bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of weight at least w(G)/2 + wMSF (G)/4 , where w(G) denotes the total weight of G, and wMSF (G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f (k) · O(m + n).}, author = {Lill, Jonas and Petrova, Kalina H and Weber, Simon}, issn = {1432-0541}, journal = {Algorithmica}, pages = {983--1007}, publisher = {Springer Nature}, title = {{Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound}}, doi = {10.1007/s00453-025-01306-y}, volume = {87}, year = {2025}, } @unpublished{21211, abstract = {We show that, for any graph F and η > 0, there exists a d0 = d0(F, η) such that every nvertex d-regular graph with d ≥ d0 has a collection of vertex-disjoint F-subdivisions covering at least (1 − η)n vertices. This verifies a conjecture of Verstraëte from 2002 and improves a recent result of Letzter, Methuku and Sudakov which additionally required d to be at least polylogarithmic in n. }, author = {Montgomery, Richard and Petrova, Kalina H and Ranganathan, Arjun and Tan, Jane}, booktitle = {arXiv}, title = {{Packing subdivisions into regular graphs}}, doi = {10.48550/arXiv.2508.00480}, year = {2025}, } @inproceedings{18758, abstract = {MaxCut is a classical NP-complete problem and a crucial building block in many combinatorial algorithms. The famous Edwards-Erdős bound states that any connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4. Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem on simple connected graphs admits an FPT algorithm, where the parameter k is the difference between the desired cut size c and the lower bound given by the Edwards-Erdős bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively, graphs with positive integer weights). Secondly, we change the parameter; instead of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound can be larger and thus yield a smaller parameter k. Our algorithm also runs in parameterized linear time, i.e., f(k)⋅ O(m+n).}, author = {Lill, Jonas and Petrova, Kalina H and Weber, Simon}, booktitle = {19th International Symposium on Parameterized and Exact Computation}, isbn = {9783959773539}, issn = {1868-8969}, location = {Egham, United Kingdom}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound}}, doi = {10.4230/LIPIcs.IPEC.2024.2}, volume = {321}, year = {2024}, }