Matching Thresholds for Pseudorandom Clique Factors

Definitions and mathematical statement

For a positive integer $r$, let $K_r$ denote the complete graph on $r$ vertices. In the usual finite simple undirected graph setting, a $K_r$-factor of a graph $G=(V,E)$ is a collection of vertex-disjoint copies of $K_r$ whose vertex sets partition $V$. Thus, writing $n=|V|$, a necessary condition is $r\mid n$, and a factor consists of $n/r$ copies. The copies need not be induced components of $G$.

The supplied record attributes to Patrick Morris sufficient conditions for the existence of $K_r$-factors in sparse pseudorandom graphs for every fixed $r$, and reports tightness for $r=3$. Its question concerns larger cliques: for fixed integers $r\geq 4$, do constructions of sparse pseudorandom graphs without $K_r$-factors match the sufficient bounds attributed to Morris? Any obstruction relevant to the substantive threshold question must satisfy $r\mid |V(G)|$, so that the absence of a factor is not merely a divisibility obstruction.

Here "matching" asks whether the sufficient bounds are sharp in the intended parameter regimes. The supplied record does not state those bounds, define its notion of pseudorandomness, specify the sparse density regime, or specify whether matching means equality up to constants, matching exponents, or a sharper asymptotic comparison. Consequently, this is a qualified formulation of the recorded question; a fully quantified threshold conjecture cannot be recovered from the supplied text alone.

Short English statement

For each fixed clique size $r\geq 4$, the question asks whether sparse pseudorandom graphs without a $K_r$-factor demonstrate the sharpness of the sufficient bounds attributed to Morris. The record omits the quantitative bounds and pseudorandomness assumptions needed for a precise threshold statement.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $30005099$, title "Matching Thresholds for Pseudorandom Clique Factors," exact source code catalogue entry. The record gives proposed year 2022 and does not identify a proposer.
• Supplied report citation: Combinatorics, Probability and Computing (2023), Oberwolfach Reports, pp. 1165--1237, DOI 10.4171/owr/2022/22. https://doi.org/10.4171/owr/2022/22. The supplied passage attributes the clique-factor results to Patrick Morris and identifies the triangle-factor conjecture as one of Krivelevich, Sudakov and Szabó.
• Supplied literature source: "Morris, clique factors in pseudorandom graphs." https://doi.org/10.4171/JEMS/1388.
• Supplied literature source: "Oberwolfach Report 22/2022." https://doi.org/10.4171/owr/2022/22.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open, attributes sufficient conditions for every fixed $r$ and tightness for $r=3$ to Morris, and describes matching obstructions for larger cliques as unresolved. This is supplied dated curation, not an independently verified literature assessment.
• The registry labels the statement corrected_verified and reports that the official report was checked directly. Those are supplied verification claims; no source visit or independent verification is asserted in this draft.