8 papers
The critical probability for percolation on finite graphs
Micha Christoph, Patryk Morawski, Yuval Wigderson
We determine the critical probability for Bernoulli bond percolation on essentially any finite graph. Namely, letting denote the spectral radius (maximum eigenvalue) of ,…
Nearly tight bounds for induced subdivisions
Zach Hunter, Aleksa Milojević, Patryk Morawski +1
Subdivisions of complete graphs play a central role in combinatorics, having deep connections to structural, extremal, and topological aspects of graph theory. A celebrated conject…
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 ,…
Ramsey numbers of digraphs with local edge structure
Domagoj Bradač, Patryk Morawski, Benny Sudakov +1
One of the classical topics in graph Ramsey theory is the study of which -vertex graphs have Ramsey numbers that are linear in . In this paper, we consider this problem in th…
Hamilton cycles in regular graphs perturbed by a random 2-factor
Cicely, Henderson, Sean Longbrake +2
In this paper, we prove that for each , the union of a -regular graph with a uniformly random -factor on the same vertex set is Hamiltonian with high probability. T…
Ordered Ramsey numbers of graphs with edges
Domagoj Bradač, Patryk Morawski, Benny Sudakov +1
Given a vertex-ordered graph , the ordered Ramsey number is the minimum integer such that every -coloring of the edges of the complete ordered graph contai…
Oriented Ramsey numbers of graded digraphs
Patryk Morawski, Yuval Wigderson
We show that any graded digraph on vertices with maximum degree has an oriented Ramsey number of at most for some absolute constant , improving upon a rec…
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…