We establish a tensor spectral stability theorem for uniform hypergraphs with bounded matching number. More precisely, for fixed integers $k\geq 3$ and $\beta\geq2$, and sufficiently large $n$, we prove that every $n$-vertex $k$-uniform hypergraph $H$ with matching number at most $\beta$ and tensor spectral radius close to the maximum possible value among all such hypergraphs must be structurally close to the extremal hypergraph $S_{n,k,\beta}$, whose edges consist of all $k$-sets intersecting a fixed set of $\beta$ vertices. Furthermore, we show that every edge of $H$ intersects this distinguished vertex set and that $H$ contains all but a small proportion of the edges of $S_{n,k,\beta}$. As an application, we obtain a new proof of the spectral version of the Erd\H{o}s matching conjecture for sufficiently large $n$.
A nonempty subfamily of a $k$-uniform hypergraph is an \emph{even cover} if every vertex lies in an even number of its hyperedges; for $k=2$ these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants $A$ and $C$ (independent of $k$) such that for every $k\ge3$ and every $1\le\ell\le n$, any $k$-uniform hypergraph on $n$ vertices with more than $C\,n^{k/2}/\ell^{k/2-1}$ hyperedges contains an even cover of size at most $A\,\ell\log(en/\ell)$. Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.
Alexander Schmidhuber, Matthew B. Hastings· arXiv.org· 0 citations
The spectral Erd\H{o}s--Ko--Rado problem asks for the largest adjacency-tensor spectral radius of a $t$-intersecting $k$-uniform family. Keevash, Lenz and Mubayi proved that, for fixed $k,t$ and sufficiently large $n$, the unique extremal family is a full $t$-star, and asked whether such a theorem extends to all $n$. Let $\mathcal{A}_r=\{F\in\binom{[n]}k:|F\cap[t+2r]|\ge t+r\}$ be the Frankl families and write $\rho_r$ for their spectral radii. For $2\le t2k-t$, we prove that $\mathcal{A}_0$ is spectrally extremal if and only if $\rho_0\ge\rho_1$; it is unique up to permutation when the inequality is strict, whereas $\mathcal{A}_0$ and $\mathcal{A}_1$ are both extremal at equality. The layerwise pull used in the Ahlswede--Khachatrian cardinality proof is not applicable here: applied directly, it may decrease the spectral radius. Our proof instead pulls all boundary layers simultaneously and applies Perron tail symmetrization. It follows that $\mathcal{A}_0$ is uniquely extremal for $n\ge (t+1)(k-t+1)+\lceil(t+1)\log(t+1)\rceil$; the leading coefficient $t+1$ is best possible for fixed $t$. We also determine all extremal structures for $t=1$ throughout the range $n\ge2k$.
For a fixed integer $k\ge2$, we establish a sharp adjacency-spectral upper bound for sufficiently large $m$-edge $kK_3$-free graphs. We prove \[ \lambda(G)\le (k-1)+\sqrt{m-k(k-1)}. \] Moreover, equality holds precisely when $(2k-1)\mid m$ and, up to isolated vertices, $G$ is the join of $K_{2k-1}$ with an independent set of $m/(2k-1)-(k-1)$ vertices. The case $k=2$ was previously known; our argument establishes every fixed $k\ge3$. The proof requires information beyond first-order spectral stability. We derive an exact nonnegative defect identity at a maximum Perron vertex, use it to bound the entire outer layer by a constant, and reduce the remaining graph to a bounded core with finitely many independent twin classes. A Perron-vector concentration identity and the Erd\H{o}s--Gallai matching theorem then force the unique extremal core. A nearly extremal family lies only $\Theta(m^{-1/2})$ below the target, showing why an exact second-order analysis is necessary.
In a $k$-uniform hypergraph, the minimum $d$-degree for some $0\le d\le k-1$ is the minimum number of edges containing any given $d$-set of vertices. An extension of the classical Dirac theorem guarantees that whenever the minimum $d$-degree of a $k$-uniform $n$-vertex hypergraph, $k\mid n$, is larger than a certain Dirac threshold, it contains at least one perfect matching. Moreover, it has been known for some time, due to Kwan, Safavi, and Wang, that for $d\ge k/2$ such hypergraphs contain not only one, but ``many''perfect matchings, that is, at least as many as are expected in a random hypergraph with the same edge density. However, it has also been known that such a result could not be hoped for in general, as it already fails for $(d,k)=(1,3)$. In this paper we introduce new notions of the \emph{counting thresholds} and \emph{approximate counting thresholds}, above which a hypergraph is guaranteed to have at least this many perfect matchings. We show that these thresholds are well-defined and nontrivial for all $d,k,n$, that they are asymptotically related, and finally, we derive improved upper bounds by reducing to cases with smaller $d$ and $k$.
For an integer $k\ge3$, a $k$-angulation is a simple $2$-connected outerplane graph whose interior faces are bounded by $k$-cycles, and a closed $k$-angulation is a simple $2$-connected plane graph all of whose faces, the outer face included, are bounded by $k$-cycles; the face hypergraph of either is the $k$-uniform hypergraph whose edges are the vertex sets of those faces. For $k=3$ these are the outerplanar and planar hypergraphs of Ellingham, Lu and Wang, who determined the outerplanar extremal hypergraph for large $n$ and conjectured the planar one. In this paper, we determine the extremal hypergraphs in both classes for every $k$. In the outerplanar case, for all sufficiently large admissible $n$, it is the fan, in which a single vertex lies on every face, and the maximum equals $(4f)^{1/k}(1+o(1))$ with $f=(n-2)/(k-2)$. In the planar problem the maximum has order $n^{1/3}$ when $k=3$ and order $n^{2/k}$ when $k\ge4$. For $k\ge4$ the extremal hypergraphs are the face hypergraphs of the balanced theta graphs, in which two vertices are joined by internally disjoint paths and every face is a $k$-cycle through both: for $k=4$, where the closed $4$-angulations are the quadrangulations of the sphere, this holds for every $n\ge5$, the extremal hypergraph being $\mathcal{H}(K_{2,n-2})$, and for $k\ge5$ for all sufficiently large admissible $n$. For $k\ge6$ the extremal hypergraph is not unique: when the number of faces is even there are exactly $\lfloor(k-2)/2\rfloor$ of them up to isomorphism. For $k=3$ two vertices of a plane triangulation lie on at most two common faces, the balanced theta graphs are unavailable, and the extremal hypergraph is instead, for all sufficiently large $n$, the face hypergraph of $K_2+P_{n-2}$; this confirms a conjecture of Ellingham, Lu and Wang.
Let $1\leq k\leq n$. We prove that $k$-dimensional intrinsic Lipschitz graphs in the Heisenberg group $\mathbb{H}^n$ satisfy a geometric lemma $\mathrm{GLem}(\beta_{2,\mathcal{V}_k},p)$ for horizontal $\beta$-numbers with an exponent $p=p(k)$. Previously, this result was known only in the case $k=1$; our proof recovers the sharp exponent $p=4$ in this setting. For $k>1$, we adapt an integral geometric approach originally developed by Orponen for Euclidean and parabolic Lipschitz functions. In addition, for $k=n$, we show how to deduce a geometric lemma directly from an isotropic Dorronsoro theorem in $\mathbb{R}^{2n}$ using a Morrey-type inequality. Building on the new geometric lemmas, we establish a necessary condition for $k$-regular sets in $\mathbb{H}^n$ to admit corona decompositions by intrinsic Lipschitz graphs. The condition is known to be sufficient by earlier work of the last two authors together with Pinamonti. It involves additional flatness coefficients besides $\beta_{2,\mathcal{V}_k}$. Along the way, we therefore extend the known stability results for geometric lemmas under the"big pieces''functor to a larger class of coefficients.
Yi-Bo Chen, Katrin Fässler, Kilian Zambanini University of Jyväskylä et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
