REVIEW 1 cited by
A bandwidth theorem for graph transversals
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Given a collection $\mathcal{G}=(G_1,\dots, G_h)$ of graphs on the same vertex set $V$ of size $n$, an $h$-edge graph $H$ on the vertex set $V$ is a $\mathcal{G}$-transversal if there exists a bijection $\lambda : E(H) \rightarrow [h]$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The conditions on the minimum degree $\delta(\mathcal{G})=\min_{i\in[h]}\{ \delta(G_i)\}$ for finding a spanning $\mathcal{G}$-transversal isomorphic to a graph $H$ have been actively studied when $H$ is a Hamilton cycle, an $F$-factor, a spanning tree with maximum degree $o(n/\log n)$ and a power of a Hamilton cycle, etc. In this paper, we determined the asymptotically tight threshold on $\delta(\mathcal{G})$ for finding a $\mathcal{G}$-transversal isomorphic to $H$ when $H$ is a general $n$-vertex graph with bounded maximum degree and $o(n)$-bandwidth. This provides a transversal generalization of the celebrated Bandwidth theorem by B\"ottcher, Schacht and Taraz.
Forward citations
Cited by 1 Pith paper
-
Transversal packings in families of percolated hypergraphs
For any strictly 1-balanced k-graph F, k-graph systems above the transversal Dirac threshold with high probability contain a transversal F-factor after independent random sparsification at p = Ω(n^{-1/d1(F)-1} (log n)^{1/t}).
Discussion (0). Sign in to comment.