RMRichard Mycroft

Richard Mycroft

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Richard Mycroft has a total of 28 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Two new results on maximal left-compressed intersecting families

    by Allan Flower, Richard Mycroft

    This paper presents two new results on the theory of maximal left-compressed intersecting families (MLCIFs). First, we answer a question raised by Barber by showing that the number of $k$-uniform MLCIFs on a ground set of size $n$ grows as a doubly-exponential function of $k$, which we identify up to a log factor in the exponent. Among these MLCIFs we identify $k$ specific MLCIFs -- which we call the canonical MLCIFs -- as being in a meaningful way the most important MLCIFs. Specifically, our second main result shows that the canonical MLCIFs are precisely those which can have maximum weight among all $k$-uniform MLCIFs under a non-trivial increasing weight function, and moreover that each canonical MLCIF is the unique $k$-uniform MLCIF of maximum weight for some increasing weight function. This gives an interesting generalisation of the Erdős--Ko--Rado theorem to a notion of size which places greater significance on some elements of the ground set than others.

  • Open Access

    Positive codegree thresholds for perfect matchings in hypergraphs

    by Richard Mycroft, Camila Zárate-Guerén

    We give, for each $k \geq 3$, the precise best possible minimum positive codegree condition for a perfect matching in a large $k$-uniform hypergraph $H$ on $n$ vertices. Specifically we show that, if $n$ is sufficiently large and divisible by $k$, and $H$ has minimum positive codegree $δ^+(H) \geq \frac{k-1}{k}n - (k-2)$ and no isolated vertices, then $H$ contains a perfect matching. For $k=3$ this was previously established by Halfpap and Magnan, who also gave bounds for $k \geq 4$ which were tight up to an additive constant.

  • Open Access

    Perfect tilings of 3-graphs with the generalised triangle

    by Candida Bowtell, Amarja Kathapurkar, Natasha Morrison, Richard Mycroft

    We establish a best-possible minimum codegree condition for the existence of a perfect tiling of a $3$-uniform hypergraph $H$ with copies of the generalised triangle $T$, which is the 3-uniform hypergraph with five vertices $a, b, c, d, e$ and three edges $abc$, $abd$, $cde$. We also give an asymptotically-optimal minimum codegree condition for the rainbow version of the problem.

  • Open Access

    Matchings in multipartite hypergraphs

    by Candida Bowtell, Richard Mycroft


  • Open Access

    Removing induced powers of cycles from a graph via fewest edits

    by Amarja Kathapurkar, Richard Mycroft

    What is the minimum proportion of edges which must be added to or removed from a graph of density $p$ to eliminate all induced cycles of length $h$? The maximum of this quantity over all graphs of density $p$ is measured by the edit distance function, $\text{ed}_{\text{Forb}(C_h)}(p)$, a function which provides a natural metric between graphs and hereditary properties. Martin determined $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [0,1]$ when $h \in \{3, \ldots, 9\}$ and determined $\text{ed}_{\text{Forb}(C_{10})}(p)$ for $p \in [1/7, 1]$. Peck determined $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [0,1]$ for odd cycles, and for $p \in [ 1/\lceil h/3 \rceil, 1]$ for even cycles. In this paper, we fully determine the edit distance function for $C_{10}$ and $C_{12}$. Furthermore, we improve on the result of Peck for even cycles, by determining $\text{ed}_{\text{Forb}(C_h)}(p)$ for all $p \in [p_0, 1/\lceil h/3 \rceil ]$, where $p_0 \leq c/h^2$ for a constant $c$. More generally, if $C_h^t$ is the $t$-th power of the cycle $C_h$, we determine $\text{ed}_{\text{Forb}(C_h^t)}(p)$ for all $p \geq p_0$ in the case when $(t+1) \mid h$, thus improving on earlier work of Berikkyzy, Martin and Peck.

  • Open Access

    Classification of maximum hittings by large families

    by Candida Bowtell, Richard Mycroft

    For integers $r$ and $n$, where $n$ is sufficiently large, and for every set $X \subseteq [n]$ we determine the maximal left-compressed intersecting families $\mathcal{A}\subseteq \binom{[n]}{r}$ which achieve maximum hitting with $X$ (i.e. have the most members which intersect $X$). This answers a question of Barber, who extended previous results by Borg to characterise those sets $X$ for which maximum hitting is achieved by the star.

  • Contagious sets in a degree‐proportional bootstrap percolation process

    by Frederik Garbe, Richard Mycroft, Andrew McDowell

    We study the following bootstrap percolation process: given a connected graph G, a constant ρ ∈ [0,1] and an initial set A⊆V(G) of infected vertices, at each step a vertex v becomes infected if at least a ρ‐proportion of its neighbors are already infected (once infected, a vertex remains infected forever). Our focus is on the size hρ(G) of a smallest initial set which is contagious, meaning that this process results in the infection of every vertex of G. Our main result states that every connected graph G on n vertices has hρ(G) < 2ρn or hρ(G) = 1 (note that allowing the latter possibility is necessary because of the case , as every contagious set has size at least one). This is the best‐possible bound of this form, and improves on previous results of Chang and Lyuu and of Gentner and Rautenbach. We also provide a stronger bound for graphs of girth at least five and sufficiently small ρ, which is asymptotically best‐possible.


  • Triangle-Tilings in Graphs Without Large Independent Sets

    by József Balogh, ANDREW McDOWELL, Theodore Molla, Richard Mycroft

    We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an n-vertex graph G with sublinear independence number. In this setting, we show that if δ(G) ≥ n/3 + o(n), then G has a triangle-tiling covering all but at most four vertices. Also, for every r ≥ 5, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that G is Kr-free and n is divisible by 3.


  • Open Access

    Hamilton cycles in hypergraphs below the Dirac threshold

    by Frederik Garbe, Richard Mycroft

    We establish a precise characterisation of $4$-uniform hypergraphs with minimum codegree close to $n/2$ which contain a Hamilton $2$-cycle. As an immediate corollary we identify the exact Dirac threshold for Hamilton $2$-cycles in $4$-uniform hypergraphs. Moreover, by derandomising the proof of our characterisation we provide a polynomial-time algorithm which, given a $4$-uniform hypergraph $H$ with minimum codegree close to $n/2$, either finds a Hamilton $2$-cycle in $H$ or provides a certificate that no such cycle exists. This surprising result stands in contrast to the graph setting, in which below the Dirac threshold it is NP-hard to determine if a graph is Hamiltonian. We also consider tight Hamilton cycles in $k$-uniform hypergraphs $H$ for $k \geq 3$, giving a series of reductions to show that it is NP-hard to determine whether a $k$-uniform hypergraph $H$ with minimum degree $\delta(H) \geq \frac{1}{2}|V(H)| - O(1)$ contains a tight Hamilton cycle. It is therefore unlikely that a similar characterisation can be obtained for tight Hamilton cycles.