Patrick Morris

activity

20152023

most citedFinding any given 2-factor in sparse pseudorandom graphs efficiently

4 citations · 6 across the 9 of their papers we have counts for

collaborators

14 papers

math.CO2023

Slow graph bootstrap percolation I: Cycles

David Fabian, Patrick Morris, Tibor Szabó

Given a fixed graph $H$ and an $n$ -vertex graph $G$ , the $H$ \emph{-bootstrap percolation process} on $G$ is defined to be the sequence of graphs $G_{i}$ , $i \geq 0$ which starts with…

math.CO2023

Two-round Ramsey games on random graphs

Yahav Alon, Patrick Morris, Wojciech Samotij

Motivated by the investigation of sharpness of thresholds for Ramsey properties in random graphs, Friedgut, Kohayakawa, Rödl, Ruciński and Tetali introduced two variants of a singl…

math.PR2022

Speeding up random walk mixing by starting from a uniform vertex

Alberto Espuny Díaz, Patrick Morris, Guillem Perarnau +1

The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initia…

math.CO2022

Schur properties of randomly perturbed sets

Shagnik Das, Charlotte Knierim, Patrick Morris

A set $A$ of integers is said to be \emph{Schur} if any two-colouring of $A$ results in monochromatic $x, y$ and $z$ with $x + y = z$ . We study the following problem: how many random in…

math.CO2021

A Ramsey-Turán theory for tilings in graphs

Jie Han, Patrick Morris, Guanghui Wang +1

For a $k$ -vertex graph $F$ and an $n$ -vertex graph $G$ , an $F$ -tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ . For $r \in N$ , the $r$ -independence nu…

math.CO2021

Clique factors in pseudorandom graphs

Patrick Morris

An $n$ -vertex graph is said to to be $(p, β)$ -bijumbled if for any vertex sets $A, B \subseteq V (G)$ , we have \[e(A,B)=p|A||B|\pm β\sqrt{|A||B|}.\] We prove that for any $3\leq r\in \…

math.CO2020★ 1 cited

Factors in randomly perturbed hypergraphs

Yulin Chang, Jie Han, Yoshiharu Kohayakawa +2

We determine, up to a multiplicative constant, the optimal number of random edges that need to be added to a $k$ -graph $H$ with minimum vertex degree $Ω (n^{k - 1})$ to ensure an $F$ -…

math.CO2020

Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs

Hiep Hàn, Jie Han, Patrick Morris

We investigate the emergence of spanning structures in sparse pseudo-random $k$ -uniform hypergraphs, using the following comparatively weak notion of pseudo-randomness. A $k$ -unifo…

math.CO2020

Ryser's Conjecture for $t$ -intersecting hypergraphs

Anurag Bishnoi, Shagnik Das, Patrick Morris +1

A well-known conjecture, often attributed to Ryser, states that the cover number of an $r$ -partite $r$ -uniform hypergraph is at most $r - 1$ times larger than its matching number.…

math.CO2019

Vertex Ramsey properties of randomly perturbed graphs

Shagnik Das, Patrick Morris, Andrew Treglown

Given graphs $F, H$ and $G$ , we say that $G$ is $(F, H)_{v}$ -Ramsey if every red/blue vertex colouring of $G$ containsa red copy of $F$ or a blue copy of $H$ . Results of Łuczak, Rucińs…

math.CO2019

Tilings in randomly perturbed graphs: bridging the gap between Hajnal-Szemerédi and Johansson-Kahn-Vu

Jie Han, Patrick Morris, Andrew Treglown

A perfect $K_{r}$ -tiling in a graph $G$ is a collection of vertex-disjoint copies of $K_{r}$ that together cover all the vertices in $G$ . In this paper we consider perfect $K_{r}$ -tiling…

math.CO2019★ 4 cited

Finding any given 2-factor in sparse pseudorandom graphs efficiently

Jie Han, Yoshiharu Kohayakawa, Patrick Morris +1

Given an $n$ -vertex pseudorandom graph $G$ and an $n$ -vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$ , i.e.\ an embedding $φ\colon V(H)\to V(…

math.CO2018

Clique-factors in sparse pseudorandom graphs