Kalina Petrova

collaborators

3 papers

math.PR2025

Parities in random Latin squares

Matthew Kwan, Kalina Petrova, Mehtaab Sawhney

In a Latin square, every row can be interpreted as a permutation, and therefore has a parity (even or odd). We prove that in a uniformly random $n \times n$ Latin square, the $n$ ro…

cs.DS2024

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound

Jonas Lill, Kalina Petrova, Simon Weber

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 vertice…

math.CO2024

The Hamilton space of pseudorandom graphs

Micha Christoph, Rajko Nenadov, Kalina Petrova

We show that if $n$ is odd and $p \geq C lo g 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…