1 citations · 1 across the 12 of their papers we have counts for
20 papers
Improved bounds on completion of partial Latin squares
Jack Allsop, Candida Bowtell, Thomas Lesgourgues +1
A Latin square of order is an array filled with symbols so that each symbol appears exactly once in every row and column. A partial Latin square of order i…
On constructing small subgraphs in the budget-constrained random graph process
Sylwia Antoniuk, Alberto Espuny Díaz, Kalina Petrova +1
Consider the budget-constrained random graph process introduced by Frieze, Krivelevich and Michaeli, where each time an edge is offered through the (standard) random graph process…
Ramsey number of a cycle versus a graph of a given size
Stijn Cambie, Andrea Freschi, Patryk Morawski +2
In this paper, we prove that for every and every graph with edges and no isolated vertices, the Ramsey number is at most ,…
Odd-Ramsey numbers of Hamilton cycles
Simona Boyadzhiyska, Shagnik Das, Thomas Lesgourgues +1
The odd-Ramsey number of a graph , as introduced by Alon in his work on graph-codes, is the minimum number of colours needed to edge-colour so that ev…
Extending Thomassen's conjecture to directed graphs
Micha Christoph, Barnabás Janzer, Kalina Petrova +1
A famous conjecture by Thomassen from 1983 asserts that for any given there exists some such that every graph of minimum degree at leas…
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 Latin square, the ro…
Packing subdivisions into regular graphs
Richard Montgomery, Kalina Petrova, Arjun Ranganathan +1
We show that, for any graph and , there exists a such that every -vertex -regular graph with has a collection of vertex-disjoint -subd…
Sharp thresholds for higher powers of Hamilton cycles in random graphs
Tamás Makai, Matija Pasch, Kalina Petrova +1
For , we establish that is a sharp threshold for the existence of the -th power of a Hamilton cycle in the binomial random graph model. Our proof…
Odd-Ramsey numbers of complete bipartite graphs
Simona Boyadzhiyska, Shagnik Das, Thomas Lesgourgues +1
In his study of graph codes, Alon introduced the concept of the odd-Ramsey number of a family of graphs in , defined as the minimum number of colours needed to c…
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…
Improved bounds for polylogarithmic graph distances in scale-free percolation and related models
Kostas Lakis, Johannes Lengler, Kalina Petrova +1
In this paper, we study graph distances in the geometric random graph models scale-free percolation SFP, geometric inhomogeneous random graphs GIRG, and hyperbolic random graphs HR…
The Hamilton space of pseudorandom graphs
Micha Christoph, Rajko Nenadov, Kalina Petrova
We show that if is odd and , then with high probability Hamilton cycles in span its cycle space. More generally, we show this holds for a class of…
A note on digraph splitting
Micha Christoph, Kalina Petrova, Raphael Steiner
A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 2006, asks whether for every pair of integers there exists a finite number s…
Size-Ramsey numbers of structurally sparse graphs
Nemanja Draganić, Marc Kaufmann, David Munhá Correia +2
Size-Ramsey numbers are a central notion in combinatorics and have been widely studied since their introduction by Erdős, Faudree, Rousseau and Schelp in 1978. Research has mainly…
Randomly perturbed digraphs also have bounded-degree spanning trees
Patryk Morawski, Kalina Petrova
We show that a randomly perturbed digraph, where we start with a dense digraph and add a small number of random edges to it, will typically contain a fixed orientation of a b…
On Connectivity in Random Graph Models with Limited Dependencies
Johannes Lengler, Anders Martinsson, Kalina Petrova +4
For any positive edge density , a random graph in the Erdős-Renyi model is connected with non-zero probability, since all edges are mutually independent. We consider r…
Embedding loose spanning trees in 3-uniform hypergraphs
Yanitsa Pehova, Kalina Petrova
In 1995, Komlós, Sárközy and Szemerédi showed that every large -vertex graph with minimum degree at least contains all spanning trees of bounded degree. We consider…
Size-Ramsey numbers of graphs with maximum degree three
Nemanja Draganić, Kalina Petrova
The size-Ramsey number of a graph is the smallest number of edges a (host) graph can have, such that for any red/blue colouring of , there is a monochromati…
Transference for loose Hamilton cycles in random -uniform hypergraphs
Kalina Petrova, Miloš Trujić
A loose Hamilton cycle in a hypergraph is a cyclic sequence of edges covering all vertices in which only every two consecutive edges intersect and do so in exactly one vertex. With…
Optimal strategies for patrolling fences
Bernhard Haeupler, Fabian Kuhn, Anders Martinsson +2
A classical multi-agent fence patrolling problem asks: What is the maximum length of a line that agents with maximum speeds can patrol if each point on the…