Skip to content
Preprint

Fractional clique decompositions in random hypergraphs

Sep 2026 · 1 citation · 24 references
Mathematics

Abstract

We prove that, whenever $ p \ge n^{-1/2 + o(1)} $, with high probability $ G(n, p) $ admits a fractional triangle decomposition, that is, a non-negative weight function on its triangles for which the total weight of all triangles containing each edge is equal to 1. This bound on $ p $ is optimal up to the asymptotic error term, improving upon the recent state of the art, due to Mahabaduge and Simkin, that $ p \ge n^{-4/11 + o(1)} $ suffices. Our main tool is a deterministic theorem guaranteeing the existence of fractional clique decompositions in all hypergraphs satisfying suitable `clique-regularity'properties. We prove this by analysing an extension (and generalisation to hypergraphs) of an algorithm proposed by Mahabaduge and Simkin, in which, at each time step, the discrepancy at each edge is spread among its containing triangles. By showing the concentration of the relevant quantities in random $ k $-uniform hypergraphs, we obtain for all $ k \ge 2 $ and $ r \ge k + 1 $ that w.h.p. $ G^{(k)}(n, p) $ admits a fractional $ K^{(k)}_r $-decomposition whenever $ p \ge n^{-\frac{r - k}{\binom{r}{k} - 1} + o(1)} $, which improves upon results of Delcourt, Kelly, and Postle, and is best possible up to subpolynomial factors.

View source

Similar papers

Preprint Sep 2026

Extremal hypergraphs without generalized 4-cycles

In 1977, Erd\H{o}s posed the problem of determining the maximum number $f_r(n)$ of edges in an $n$-vertex $r$-uniform hypergraph in which all disjoint pairs of edges have distinct unions. F\"uredi later conjectured that, for every fixed $r\ge 4$ and all sufficiently large $n$, $f_r(n)=\binom{n-1}{r-1}+\lfloor \frac{n-1...

Hao-Wei Huang, Jie Ma, Tian-Chi Yang · 2 citations · ⚡1
Preprint Sep 2026

Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts. For every fixed $0<\gamma\le1/10$ and every $p=p(n)\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta(H)\ge(1/3+\gamma)pn...

Guo-Rong Gao, Jia-Lin He · 0 citations
Preprint Oct 2026

Optimal Bounds on Spanning Tree Embeddings

We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....

Csongor Beke, V. Boskovic, Nina Kamčev et al. · 0 citations
Preprint Sep 2026

Variance of random greedy independent sets in triangle-free graphs

Inspect the vertices of a finite simple graph in uniformly random order, accepting each vertex if none of its neighbors has previously been accepted. Let $X_G$ be the number of accepted vertices. For every triangle-free graph with $n\ge2$ vertices and $e$ edges, we prove $\operatorname{Var}(X_G)\le e((n-2)/n)^2$, with...

Mubin Shaikh · 0 citations
Preprint Aug 2026

A Local Central Limit Theorem for Clique Counts in Sparse Random Graphs

Let $X_H$ denote the number of copies of a fixed graph $H$ in $G_{n, p}$. Gilmer and Kopparty conjectured that $X_H$ satisfies a local central limit theorem (LCLT) provided that $H$ is connected, $p \gg n^{-1/m(H)}$, and $n^2 (1-p) \gg 1$, where $m(H)$ is the maximum density. Following the work of Berkowitz, Sah and Sa...

Asaf Cohen Antonir, Ilay Hoshen, M. Zhukovskii · 1 citation
Preprint Sep 2026

Hamiltonicity of mildly pseudorandom regular graphs

We show that if an $(n,d,\lambda)$-graph satisfies $\lambda\leq (1-\delta)d$ and $d\gg \delta^{-6}(\log n)^{3}$ for some $\delta>0$, then it is Hamiltonian. A qualitatively similar result was recently proven by Brada\v{c} and Janzer. Our proof here is shorter and gives better quantitative bounds. \par In our proof, as...

Alp Muyesser · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.