Counting thresholds for perfect matchings in hypergraphs

Abstract

In a $k$-uniform hypergraph, the minimum $d$-degree for some $0\leq d\leq 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 [17], that for $d\geq 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 counting thresholds and 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$.

1 Introduction

Dirac’s theorem, commonly regarded as one of the fundamental results in graph theory, states that any graph $G$ on $n\geq 3$ vertices with minimum degree at least $\frac{n}{2}$ contains a Hamilton cycle (i.e. a cycle that visits each vertex of $G$ exactly once). As this minimum degree condition already appears quite strong, a natural question arises: what is the minimum number of Hamilton cycles that can be guaranteed to exist in such a graph? This question was first raised in the literature by Bondy [2]. Significant progress towards the correct answer was later made by Sárkozy, Selkow and Szemerédi [21], as an application of Szemerédi’s celebrated regularity lemma [23]. They showed that a graph satisfying Dirac’s condition (we refer to such graphs simply as Dirac graphs in the remainder of this paper) contains at least $c^{n}n!$ Hamilton cycles for some (small) constant $c>0$. They also conjectured that this constant can be improved to $1/2-o(1)$.

We first need to understand where this conjectured constant comes from. To that end, let $G(n,p)$ be the Erdős–Rényi random graph for some $p$, that is, we include every edge among $n$ vertices independently with probability $p$. Then, by Chernoff bounds, it follows that with high probability its minimum degree is $(1-o(1))np$, and also with high probability – which was shown by Janson [13] – the number of Hamilton cycles is $(1-o(1))\frac{1}{2}(n-1)!\,p^{n}=(1-o(1))^{n}\,n!\,p^{n}$ (i.e. is concentrated around the expected number). Thus, letting $p=\frac{1}{2}+\varepsilon$ for $\varepsilon>0$, we find that with high probability, $G$ is a Dirac graph and has at least $(\frac{1}{2}-o(1))^{n}n!$ Hamilton cycles, supporting the conjecture by Sárközy, Selkow, and Szemerédi [21].

This intuition was later confirmed by Cuckler and Kahn [5, 6], who showed that any graph with minimum degree $d\geq\frac{n}{2}$ contains at least $\left(\frac{d}{e+o(1)}\right)^{n}$ Hamilton cycles, which is exactly what we would expect in a random graph with $p=\frac{d}{n}+\varepsilon$, whose minimum degree is at least $d$ (with high probability). The random graph also certifies the tightness of this bound.

In this paper, however, we will focus on perfect matchings. Note that as long as the number of vertices of a Dirac graph is even, it produces at least one perfect matching, simply by taking every other edge of a Hamilton cycle. In fact, the results of Cuckler and Kahn [5, 6] extend to perfect matchings: any graph with minimum degree $d\geq\frac{n}{2}$ (with $n$ even) has at least $\left(\frac{d}{e+o(1)}\right)^{n/2}$ perfect matchings, and this bound is tight.

Cuckler and Kahn essentially showed how the number of perfect matchings relates to the solution of a certain convex optimisation problem, which is easier to study in practice. Before we can state their results precisely, we need to make a few definitions.

Definition 1.

Let $G=(V,E)$ be a $k$-uniform hypergraph. Then a weight assignment $\mathbf{x}\in[0,1]^{E}$ is a fractional perfect matching of $G$ if for every vertex $v\in V$, it holds that $\sum_{e\ni v}\mathbf{x}_{e}=1$.

Definition 2.

Let $G=(V,E)$ be a $k$-uniform hypergraph and let $\mathbf{x}$ be its fractional perfect matching. Then the entropy of $\mathbf{x}$ is given by

$$h(\mathbf{x}):=-\sum_{e\in E}\mathbf{x}_{e}\ln\mathbf{x}_{e},$$

with the convention $0\ln 0=0$. Moreover, the entropy of the hypergraph $G$ is defined as

$$h(G):=\sup_{\mathbf{x}}h(\mathbf{x}),$$

where $\mathbf{x}$ varies among all fractional perfect matchings of $G$.

Let $\Phi(G)$ denote the number of perfect matchings in graph $G$. Now the main result of Cuckler and Kahn [5, 6] is as follows.

Theorem 1.1 ([5, 6]).

Let $G$ be an $n$-vertex Dirac graph with $n$ even. Then

$$\Phi(G)=e^{h(G)}\left(e^{-1}+o(1)\right)^{n/2}.$$

Moreover, if $\delta(G)=d\geq\frac{n}{2}$, then $h(G)\geq\frac{n}{2}\ln d$, whence

$$\Phi(G)\geq\Phi(K_{n})(p+o(1))^{n/2},$$

where $p=d/n$ and $K_{n}$ is a complete graph on $n$ vertices.

This problem of counting perfect matchings in Dirac graphs extends naturally to hypergraphs.

Definition 3.

Let $G$ be a $k$-uniform hypergraph. A perfect matching in $G$ is a set of edges covering all vertices of $G$, with no two edges sharing a common vertex. We denote the number of perfect matchings in $G$ by $\Phi(G)$.

Definition 4.

Let $G=(V,E)$ be a $k$-uniform hypergraph and let $d$ be a positive integer with $0\leq d\leq k-1$. Given a $d$-subset $A=\{v_{1},\dots,v_{d}\}$ of $V$, we denote by $\deg_{d}A$ its $d$-degree, that is, the number of edges in $E$ that contain $A$ as a subset. We also define $\delta_{d}(G):=\min_{A\in\binom{V}{d}}\deg A$ the minimum $d$-degree among all $d$-subsets of $V$.

Definition 5.

Let $n$ and $k$ be positive integers with $k\mid n$, and let $d$ be an integer with $1\leq d\leq k-1$. Then $m_{d}(k,n)$ denotes the $d$-degree Dirac threshold of $n$-vertex $k$-uniform hypergraphs, that is, the minimum value of $\delta$ such that $\Phi(G)\geq 1$ whenever $\delta_{d}(G)\geq\delta$. Moreover, let

$$\alpha_{d}(k):=\lim_{\begin{subarray}{c}n\to\infty\\ k\mid n\end{subarray}}\frac{m_{d}(k,n)}{\binom{n-d}{k-d}}$$

be the asymptotic Dirac threshold for $d$-degree in $k$-uniform hypergraphs.

Ferber and Kwan [9] showed that the limit in the previous theorem exists, thereby justifying the definition. It has been conjectured that the exact values of (asymptotic) Dirac thresholds arise from only two extremal families of hypergraphs (see, for example, [1] for a discussion of these constructions).

Conjecture 1.2 ([11, 16]).

For all positive integers $k,d$ with $d\leq k-1$,

$$\alpha_{d}(k)=\max\left\{\frac{1}{2},\,1-\left(1-\frac{1}{k}\right)^{k-d}\right\}.$$

Very recently, several independent groups of authors [10, 18, 22] announced proofs of the long-standing Feige’s conjecture. This conjecture is itself a special case of the conjecture of Samuels, whose relationship with the problem of determining Dirac thresholds of hypergraphs has been studied in [1]. It follows from the results of this paper that Conjecture 1.2 holds assuming Feige’s conjecture. Before these breakthrough proofs of Feige’s conjecture, only sporadic exact values of (asymptotic) Dirac thresholds were known.

Even without knowing these thresholds precisely, it is still possible to count perfect matchings in Dirac hypergraphs. Since in these results it is usually required that the asymptotic Dirac threshold is strictly surpassed, we make the following definition.

Definition 6.

Let $n$, $k$, and $d$ be positive integers, $k\mid n$, $1\leq d\leq k-1$, and let $\gamma>0$. A $k$-uniform $n$-vertex hypergraph is said to be $(d,\gamma)$-Dirac (or simply $\gamma$-Dirac if $d$ is understood from the context) if $\delta_{d}(G)\geq(\alpha_{d}(k)+\gamma)\binom{n-d}{k-d}$.

First result in this direction is due to Ferber, Krivelevich, and Sudakov [8] who showed that a $(k-1,\gamma)$-Dirac $k$-uniform hypergraph $G$ satisfies

$$\Phi(G)\geq\Phi(K^{(k)}_{n})\left(\frac{\delta_{k-1}(G)}{n}+o(1)\right)^{n/k},$$

where $K^{(k)}_{n}$ denotes the complete $k$-uniform hypergraph on $n$ vertices. This was later extended by Kang, Kelly, Kühn, Osthus, and Pfenninger [14], and independently Pham, Sah, Sawhney, and Simkin [20] to all $1\leq d\leq k-1$, but with larger error term: they showed that in a $(d,\gamma)$-Dirac $k$-uniform $n$-vertex hypergraph, the number of perfect matchings is at least $n^{(1-1/k)n}\exp(-O(n))$.

Finally, the hypergraph analogue of the results of Cuckler and Kahn was recently achieved in its full strength due to work of Kwan, Safavi, and Wang [17].

Theorem 1.3 ([17]).

Let $\gamma>0$ be a real constant, and let $n,k,d$ be integers with $k\mid n$, $1\leq d\leq k-1$. Then every $(d,\gamma)$-Dirac $k$-uniform $n$-vertex hypergraph $G$ satisfies

$$\Phi(G)=e^{h(G)}\left(e^{-1}+o(1)\right)^{\left(1-\frac{1}{k}\right)n}.$$ (1.1)

Moreover, if $d\geq\frac{k}{2}$, then

$$h(G)\geq\frac{n}{k}\ln\left(\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right),$$ (1.2)

whence the number of perfect matchings satisfies

$$\Phi(G)\geq\Phi(K^{k}_{n})\,(p+o(1))^{n/k},$$ (1.3)

where $p=\delta_{d}(G)/\binom{n-d}{k-d}$.

Although at first sight one could hope to extend the results Kwan, Safavi, and Wang to all $1\leq d\leq k-1$, it was observed by Sauermann in [7, Section 5] that already for $(d,k)=(1,3)$ this is doomed to fail. We will discuss Sauermann’s construction in more detail in Section 5. The main contribution of this paper is the following theorem which shows that for any $d$, as long as the minimum $d$-degree is large enough, one can still find at least as many perfect matchings as is expected in a random hypergraph with the same edge density.

Theorem 1.4.

Let $k\geq 2$ and $1\leq d<k-1$ be positive integers. If $G$ is a $k$-uniform hypergraph that satisfies $\delta_{d}(G)>\frac{k-1}{k}\frac{n}{n-1}\binom{n-d}{k-d}$, then

$$h(G)\geq\frac{n}{k}\ln\left(\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right).$$

Asymptotically, this theorem shows that we get the desired number of perfect matchings whenever the minimum $d$-degree of $G$ deviates from the theoretical maximum by no more than a $1/k$-fraction. The question then arises to determine the exact thresholds above which entropy must satisfy (1.2), and we call these thresholds counting thresholds and denote $c_{d}(k,n)$. It follows from Theorem 1.4 that they exist and are nontrivial.

Unlike the case of Dirac thresholds, here we are not able to show that the ratio $c_{d}(k,n)/\binom{n-d}{k-d}$ tends to a limit as $n$ goes to infinity. Nevertheless, we can still give a result that is almost equally good in practice (i.e. after an application of Theorem 1.4): whenever the minimum $d$-degree of a $k$-uniform $n$-vertex graph (for $n$ large enough) is asymptotically larger than $\liminf_{n\to\infty}c_{d}(k,n)/\binom{n-d}{k-d}$, its entropy satisfies (1.2) up to an error term of order $o(n)$. This result justifies introducing the notion of approximate counting thresholds $\beta_{d}(k)$ to compensate for the error term.

Finally, we are able to give slightly better bounds on approximate counting thresholds by reducing to the cases with smaller $d$ and $k$. Namely, we show that $\beta_{d}(k)$ is upper-bounded by $\beta_{1}(k/d)$ whenever $d\mid k$, and by $\beta_{d-l}(k-l)$ for all $l<d$.

Note that in the statement of Theorem 1.4 we do not require that $k\mid n$. In fact, it is crucial for us that the notions of fractional perfect matchings and entropy still make sense even if no perfect matching exists due to divisibility constraints.

1.1 Structure of the paper

After a short exposition of preliminary results in Section 1.2, in Section 2 we show Theorem 1.4. In Section 3 we introduce counting and approximate counting thresholds, and show how they relate. In Section 4 we give some general upper bounds on approximate counting thresholds. Finally, in Section 5 we present some concluding remarks and possibilities for further development. For completeness, we also include in Appendix A a proof due to Hoffman of the important Theorem 1.6.

1.2 Preliminaries

It is worth noting that a lower bound on $\delta_{d^{\prime}}(G)$ for some $d^{\prime}$ implies a bound on $\delta_{d}(G)$ for all $d\leq d^{\prime}$ via a double counting argument.

Proposition 1.5.

Let $G$ be a $k$-uniform $n$-vertex graph. Then

$$\frac{\delta_{0}(G)}{\binom{n}{k}}\geq\cdots\geq\frac{\delta(G)}{\binom{n-k+1}{1}}.$$

Consequently, it holds that $\alpha_{0}(k)\geq\alpha_{1}(k)\geq\cdots\geq\alpha_{k-1}(k)$ for all $k$.

Proof.

Let $0\leq d<d^{\prime}\leq k-1$, and let $S\in\binom{V(G)}{d}$ be an arbitrary $d$-set of vertices. Then

$$\deg_{d}S \,\,\,=\,\,\,\binom{k-d}{d^{\prime}-d}\deg_{d}S\Big/\binom{k-d}{d^{\prime}-d}\,\,\,=\,\,\,\frac{1}{\binom{k-d}{d^{\prime}-d}}\sum_{S\subseteq e\in E(G)}\sum_{A\in\binom{e\setminus S}{d^{\prime}-d}}1$$

$$\,\,\,=\,\,\,\frac{1}{\binom{k-d}{d^{\prime}-d}}\sum_{A\in\binom{V(G)\setminus S}{d^{\prime}-d}}\sum_{S\cup A\subseteq e\in E(G)}1\,\,\,=\,\,\,\frac{1}{\binom{k-d}{d^{\prime}-d}}\sum_{A\in\binom{V(G)\setminus S}{d^{\prime}-d}}\deg_{d^{\prime}}(S\cup A)$$

$$\,\,\,\geq\,\,\,\frac{1}{\binom{k-d}{d^{\prime}-d}}\sum_{A\in\binom{V(G)\setminus S}{d^{\prime}-d}}\delta_{d^{\prime}}(G)\,\,\,=\,\,\,\binom{n-d}{d^{\prime}-d}\delta_{d^{\prime}}(G)\Big/\binom{k-d}{d^{\prime}-d}.$$

Since $\binom{n-d}{d^{\prime}-d}/\binom{k-d}{d^{\prime}-d}=\binom{n-d}{k-d}/\binom{n-d^{\prime}}{k-d^{\prime}}$ and $S$ was arbitrary, the proposition follows. ∎

As we will see in Section 2, it is desirable to find a set of conditions on the entries of real square matrices that guarantee that the row or column sums of the inverse matrix are positive (or nonnegative). The following definition gives one such set of conditions, which was originally discovered by Hoffman [12] in his work on the nonsingularity of real matrices.

Definition 7.

An $n\times n$ real matrix $A=(a_{ij})$ is said to be positive mean-dominant or PMD if

$$\sum_{j=1}^{n}a_{ij}\geq 0\hskip 14.22636pt \text{for }i=1,\dots,n$$ (1.4)

$$\frac{1}{n}\sum_{j=1}^{n}a_{ij}\geq a_{ik}\hskip 14.22636pt \text{for }i=1,\dots,n,\,k=1,\dots,n,\,k\neq i$$ (1.5)

If (1.4) and (1.5) are both strict, $A$ is said to be strictly positive mean-dominant.

(Strictly) positive mean-dominant matrices are referred to as $B$- and $B_{0}$-matrices, respectively, by some authors (e.g. [4, 19]). The following theorem gives the key properties of PMD matrices that we will need in this paper.

Theorem 1.6 ([12]).

Let $A$ be an $n\times n$ real PMD matrix. Then $\det A\geq 0$, with inequality strict if $A$ is strictly PMD. If moreover $A$ is invertible (which is always the case for $A$ strictly PMD), we have $\sum_{i=1}^{n}a^{-1}_{ij}\geq 0$ for all $j=1,\dots,n$, where $A^{-1}=(a^{-1})_{ij}$.

We include the proof of this theorem in Appendix A for completeness.

2 1-degree conditions for many perfect matchings

In this section, we show a (nontrivial) $1$-degree condition that ensures a Dirac hypergraph has many perfect matchings – more precisely, that it satisfies (1.3). This condition will, in turn, imply Theorem 1.4 via Proposition 1.5.

For completeness, we show how the lower bound on entropy in (1.2) implies the lower bound on the number of perfect matchings (1.3) whenever (1.1) holds, which is the case for all $(d,\gamma)$-Dirac hypergraphs by Theorem 1.3. Note that

$$\ln\Phi(K^{(k)}_{n})=\ln\frac{n!}{(n/k)!(k!)^{n/k}}=n\ln n-\frac{n}{k}\ln\frac{n}{k}-\left(1-\frac{1}{k}\right)n-\frac{n}{k}\ln(k!)+o(n)$$

by Stirling’s approximation, so the logarithm of the right-hand side of (1.3) equals

$$\ln\Phi(K^{(k)}_{n})+\frac{n}{k}\ln p+o(n)=n\ln n+\frac{n}{k}\ln\left(\frac{k}{n}p\right)-\left(1-\frac{1}{k}\right)n-\frac{n}{k}\ln(k!)+o(n).$$

On the other hand, supposing (1.1) and (1.2) hold and recalling that $p=\delta_{d}(G)/\binom{n-d}{k-d}$, the logarithm of the left-hand side satisfies

$$\ln\Phi(G) \geq h(G)-\left(1-\frac{1}{k}\right)n+o(n)$$

$$\geq\frac{n}{k}\ln\left(\frac{k}{n}\frac{\binom{n}{d}}{\binom{k}{d}}\binom{n-d}{k-d}p\right)-\left(1-\frac{1}{k}\right)n+o(n)$$

$$=\frac{n}{k}\ln\left(\frac{k}{n}\binom{n}{k}p\right)-\left(1-\frac{1}{k}\right)n+o(n)$$

$$=\frac{n}{k}\ln\left(\frac{k}{n}p\right)+n\ln n-\frac{n}{k}\ln(k!)-\left(1-\frac{1}{k}\right)n+o(n),$$

completing the proof.

Therefore, in order to acheive the desired lower bound on the number of perfect matchings in a $(d,\gamma)$-Dirac hypergraph, it suffices to show that (1.2) holds. As announced, the following theorem does this whenever $1$-degree is large enough.

Theorem 2.1.

Let $k\geq 2$ be an integer. If $G=(V,E)$ is a $k$-uniform hypergraph that satisfies $\delta_{1}(G)>\frac{n}{k}\binom{n-2}{k-2}$, then $h(G)\geq\frac{n}{k}\ln{\delta_{1}(G)}$.

Our proof follows the ideas of Cuckler and Kahn [6, Theorem 1.3]. However, we use the theory of PMD matrices to give an easier proof of [6, (24)] and generalise it to higher uniformities.

Proof.

Suppose $\mathbf{x}\in\mathbb{R}^{E}$ is a fractional perfect matching of $G$. Note that

$$\mathbbm{1}_{E}^{\top}\mathbf{x}=\sum_{e\in E}\mathbf{x}_{e}=\frac{1}{k}\sum_{e\in E}\sum_{v\in e}\mathbf{x}_{e}=\frac{1}{k}\sum_{v\in V}\sum_{e\ni v}\mathbf{x}_{e}=\frac{1}{k}\sum_{v\in V}1=\frac{n}{k},$$ (2.1)

so

$$h(G)\geq h(\mathbf{x})=-\sum_{e\in E}\mathbf{x}_{e}\ln\mathbf{x}_{e}=-\frac{n}{k}\sum_{e\in E}\frac{k\mathbf{x}_{e}}{n}\ln\mathbf{x}_{e}\geq-\frac{n}{k}\ln\frac{k}{n}\sum_{e\in E}\mathbf{x}_{e}^{2}$$

by Jensen’s inequality applied to the concave function $x\mapsto\ln x$. Therefore, it suffices to find a fractional perfect matching $\mathbf{x}$ of $G$ that satisfies $\mathbf{x}^{\top}\mathbf{x}=\sum_{e\in E}\mathbf{x}_{e}^{2}\leq\frac{n}{k\delta_{1}(G)}$.

Now let $M\in\mathcal{M}_{V\times E}(\mathbb{R})$ be the vertex-edge incidence matrix of $G$. We can rewrite the condition for $\mathbf{x}$ being a fractional perfect matching as $\mathbf{x}\geq 0$ and $M\mathbf{x}=\mathbbm{1}_{V}$. Moreover, given a positive vertex-weight assignment $\mathbf{u}\in\mathbb{R}_{\geq 0}^{V}$, $M^{\top}\mathbf{u}$ gives a positive edge-weight assignment (since $M\geq 0$), which becomes a fractional perfect matching if it satisfies $\mathbbm{1}_{V}=M(M^{\top}\mathbf{u})=MM^{\top}\mathbf{u}$ as well.

In the graph case ($k=2$), matrix $(a_{vw})_{v,w\in V}=A:=MM^{\top}$ is well-studied and known as the signless Laplacian matrix of $G$. Here, it will suffice to note that $a_{vv}=\deg_{1}(v)$ and $a_{vw}=\deg_{2}(v,w)$ for $v\neq w$. We check that $A$ is strictly PMD under the hypotheses of the theorem: all entries are nonnegative and diagonal entries are strictly positive, so the row sums are strictly positive as well; as for the mean dominance, we have for every $v\in V$ and $w\neq v$,

$$\frac{1}{n}\sum_{s\in V}a_{vs} =\frac{1}{n}\left(\deg_{1}(v)+\sum_{s\neq v}\deg_{2}(v,s)\right)=\frac{k}{n}\deg_{1}(v)$$

$$>\binom{n-2}{k-2}\geq\deg_{2}(v,w)=a_{vw},$$

which is exactly what we wanted.

By Theorem 1.6, $A$ is invertible and $A^{-1}$ has nonnegative column sums. That is, $\mathbbm{1}_{V}^{\top}A^{-1}\geq 0$. But $A$ is symmetric, so this implies that $\mathbf{u}:=A^{-1}\mathbbm{1}_{V}=\left(\mathbbm{1}_{V}^{\top}A^{-1}\right)^{\top}\geq 0$. Therefore, $\mathbf{x}:=M^{\top}\mathbf{u}$ is a well-defined fractional perfect matching.

We only need to check that $\mathbf{x}$ satisfies $\mathbf{x}^{\top}\mathbf{x}\leq\frac{n}{k\delta_{1}(G)}$. We have:

$$\mathbf{x}^{\top}\mathbf{x} =\mathbf{u}^{\top}MM^{\top}\mathbf{u}=\mathbf{u}^{\top}A\mathbf{u}=\mathbf{u}^{\top}\mathbbm{1}_{V}=\sum_{v\in V}\mathbf{u}_{v}$$

$$=\frac{1}{\delta_{1}(G)}\sum_{v\in V}\delta_{1}(G)\mathbf{u}_{v}\leq\frac{1}{\delta_{1}(G)}\sum_{v\in V}\deg_{1}(v)\mathbf{u}_{v}$$

$$=\frac{1}{\delta_{1}(G)}\sum_{v\in V}\sum_{e\ni v}\mathbf{u}_{v}=\frac{1}{\delta_{1}(G)}\sum_{e\in E}\sum_{v\in e}\mathbf{u}_{v}$$

$$=\frac{1}{\delta_{1}(G)}\sum_{e\in E}\mathbf{x}_{e}=\frac{n}{k\delta_{1}(G)},$$

so we are done. ∎

Remark 2.2.

The minimum $1$-degree condition in Theorem 2.1 is asymptotically of the form $1-1/k$, which strictly dominates $\alpha_{1}(k)$ for $1\leq d<k/2$, owing to the results of Kühn, Osthus, and Townsend [15] who showed that $\alpha_{d}(k)\leq 1-\frac{d}{k}-\frac{k-d-1}{k^{k-d}}$. Thus, hypergraphs that satisfy the conditions of Theorem 2.1 are $(1,\gamma)$-Dirac for sufficiently small $\gamma>0$, and therefore satisfy (1.1).

Remark 2.3.

Note that in the previous proof the strict inequality in the minimum degree condition $\delta_{1}(G)>\frac{n}{k}\binom{n-2}{k-2}$ implies that $A$ is strictly PMD and thus invertible. Thus the proof could hold even when $\delta_{1}(G)=\frac{n}{k}\binom{n-2}{k-2}$ if one can show that $A$ is still invertible.

In fact, if the signless Laplacian matrix of a $k$-uniform hypergraph $G$ is singular, then $G$ must be a partially bipartite hypergraph, that is, a hypergraph with three vertex parts $P$, $N$, and $Z$ and with all edges intersecting both $P$ and $N$ or being fully contained in $Z$. Calculations show that for a $k$-uniform $(1,\gamma)$-Dirac partially bipartite hypergraph $G$ there can be no vertices in part $Z$, since they would have too small $1$-degree.

Moreover, for $k=2$ the only Dirac bipartite graph is $K_{n/2,n/2}$, which can be treated separately (see Cuckler and Kahn [6, Lemma 3.3]). For $k=3$, one can show that even the $(1,\gamma)$-Dirac bipartite hypergraphs have $A$ invertible, so that Theorem 2.1 holds in the slightly stronger form with $\delta_{1}(G)\geq\frac{n}{k}\binom{n-2}{k-2}$.

Theorem 1.4 is now an easy corollary by Proposition 1.5.

Proof of Theorem 1.4.

From $\delta_{d}(G)>\frac{k-1}{k}\frac{n}{n-1}\binom{n-d}{k-d}$ it follows that

$$\delta_{1}(G)\geq\frac{\binom{n-1}{k-1}}{\binom{n-d}{k-d}}\delta_{d}(G)>\frac{n}{k}\binom{n-2}{k-2}$$

by Proposition 1.5, so the result follows immediately from Theorem 2.1. ∎

3 Counting thresholds

The results of the previous section lead to the following definition.

Definition 8.

Let $n,k,d$ be positive integers, $1\leq d\leq k-1$. Then the $d$-degree counting threshold for $n$ and $k$, denoted $c_{d}(k,n)$, is the minimum value of $\delta$ such that all $k$-uniform hypergraphs $G$ on $n$ vertices with $\delta_{d}(G)\geq\delta$ satisfy (1.2), that is,

$$h(G)\geq\frac{n}{k}\ln\left(\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right).$$

Moreover, Theorem 1.4 asserts that $c_{d}(k,n)\leq(1-\frac{1}{k})\frac{n}{n-1}\binom{n-d}{k-d}+1$, so counting thresholds are always bounded away from $\binom{n-d}{k-d}$ for fixed $d$ and $k$. On the other hand, this definition is “too precise” for the applications we need it for: every application of Theorem 1.3 gives an error term of $o(n)$ in the exponent, so we would not lose much by permitting the same error term in the definition of the counting threshold. This is the goal of the following definition.

Definition 9.

Let $1\leq d\leq k-1$ be positive integers. Then the $d$-degree $k$-uniform approximate counting threshold, denoted $\beta_{d}(k)$, is the minimum $\beta>0$ such that for all $\gamma,\varepsilon>0$, there exists $n_{0}$ such that for all $n\geq n_{0}$, if $G$ is a $k$-uniform $n$-vertex hypergraph with $\delta_{d}(G)\geq(\beta+\gamma)\binom{n-d}{k-d}$, then it satisfies

$$h(G)\geq\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right).$$

Again, this definition makes sense, as $\beta$ is bounded away from $1$ by $1/k$ by Theorem 1.4. Moreover, $\beta$ is clearly upper-bounded by $\limsup_{n\to\infty}c_{d}(k,n)/\binom{n-d}{k-d}$. It is less clear that it is also upper-bounded by $\liminf_{n\to\infty}c_{d}(k,n)/\binom{n-d}{k-d}$. We dedicate the remainder of this section to the proof of this fact, for which we will need a few lemmas. The first one lets us combine fractional perfect matchings of subhypergraphs to obtain a fractional perfect matching of the original hypergraph, with the entropy bounded in terms of the entropies of subhypergraphs. Its proof relies in part on the methods of Kwan, Safavi, and Wang in [17], which will be exploited even further in the next section.

Lemma 3.1.

Let $k,q,n$ be positive integers. Let $V$ be a set of $n$ vertices, and let $G$ and $H$ be a $k$-uniform hypergraph and a $q$-uniform hypergraph on vertex set $V$, respectively. Let $\mathbf{y}:E(H)\to\mathbb{R}_{\geq 0}$ be a fractional perfect matching of $H$, and for each $f\in E(H)$, let $\mathbf{x}^{f}:E(G[f])\to\mathbb{R}_{\geq 0}$ be a fractional perfect matching of the subgraph of $G$ induced by $f$. Then

$$\mathbf{x}:E(G)\to\mathbb{R}_{\geq 0},\hskip 7.0pte\mapsto\sum_{e\subseteq f\in E(H)}\mathbf{y}_{f}\mathbf{x}^{f}_{e}$$

defines a fractional perfect matching of $G$ that satisfies

$$h(\mathbf{x})\geq\sum_{f\in E(H)}\mathbf{y}_{f}h(\mathbf{x}^{f})+\frac{q}{k}h(\mathbf{y})-\frac{n}{k}\ln\binom{n-k}{q-k}.$$

Proof.

First we check that $\mathbf{x}$ defines a fractional perfect matching of $G$. It is clear that it is nonnegative, so take any $v\in V$ and note that

$$\sum_{v\in e\in E(G)}\mathbf{x}_{e}=\sum_{v\in e\in E(G)}\sum_{e\subseteq f\in E(H)}\mathbf{y}_{f}\mathbf{x}^{f}_{e}=\sum_{v\in f\in E(H)}\mathbf{y}_{f}\sum_{v\in e\in E(G[f])}\mathbf{x}^{f}_{e}=\sum_{v\in f\in E(H)}\mathbf{y}_{f}=1.$$

So $\mathbf{x}$ really is a fractional perfect matching.

Next we show the lower bound on the entropy of $\mathbf{x}$. For $e\in E(G)$, let $n_{e}$ denote the number of edges of $H$ containing $e$. By definition, we have:

$$h(\mathbf{x}) =\sum_{e\in E(G)}\mathbf{x}_{e}\ln\frac{1}{\mathbf{x}_{e}}=\sum_{e\in E(G)}\mathbf{x}_{e}\ln\frac{1}{n_{e}}\frac{n_{e}}{\mathbf{x}_{e}}$$

$$=-\sum_{e\in E(G)}(\ln n_{e})\mathbf{x}_{e}+\sum_{e\in E(G)}n_{e}\frac{\mathbf{x}_{e}}{n_{e}}\ln\frac{n_{e}}{\mathbf{x}_{e}}$$

$$\geq-\ln\binom{n-k}{q-k}\sum_{e\in E(G)}\mathbf{x}_{e}+\sum_{e\in E(G)}n_{e}\cdot\frac{\sum_{f\supseteq e}\mathbf{y}_{f}\mathbf{x}^{f}_{e}}{n_{e}}\ln\frac{n_{e}}{\sum_{f\supseteq e}\mathbf{y}_{f}\mathbf{x}^{f}_{e}}$$

$$\geq-\frac{n}{k}\ln\binom{n-k}{q-k}+\sum_{e\in E(G)}n_{e}\sum_{f\supseteq e}\frac{1}{n_{e}}\mathbf{y}_{f}\mathbf{x}^{f}_{e}\ln\frac{1}{\mathbf{y}_{f}\mathbf{x}^{f}_{e}}$$

$$=-\frac{n}{k}\ln\binom{n-k}{q-k}+\sum_{e\in E(G)}\sum_{f\supseteq e}\mathbf{x}^{f}_{e}\mathbf{y}_{f}\ln\frac{1}{\mathbf{y}_{f}}+\sum_{e\in E(G)}\sum_{f\supseteq e}\mathbf{y}_{f}\mathbf{x}^{f}_{e}\ln\frac{1}{\mathbf{x}^{f}_{e}}$$

$$=-\frac{n}{k}\ln\binom{n-k}{q-k}+\sum_{f\in E(H)}\left(\mathbf{y}_{f}\ln\frac{1}{\mathbf{y}_{f}}\right)\sum_{e\in E(G[f])}\mathbf{x}^{f}_{e}+\sum_{f\in E(H)}\mathbf{y}_{f}\sum_{e\in E(G[f])}\mathbf{x}^{f}_{e}\ln\frac{1}{\mathbf{x}^{f}_{e}}$$

$$=-\frac{n}{k}\ln\binom{n-k}{q-k}+\frac{q}{k}\sum_{f\in E(H)}\mathbf{y}_{f}\ln\frac{1}{\mathbf{y}_{f}}+\sum_{f\in E(H)}\mathbf{y}_{f}h(\mathbf{x}^{f})$$

$$=-\frac{n}{k}\ln\binom{n-k}{q-k}+\frac{q}{k}h(\mathbf{y})+\sum_{f\in E(H)}\mathbf{y}_{f}h(\mathbf{x}^{f}),$$

where for the first inequality we used that $n_{e}\leq\binom{n-k}{q-k}$ for all $e\in E(G)$, for the second we used (2.1) and applied Jensen’s inequality to the concave function $x\mapsto x\ln\frac{1}{x}$, and for the fifth equality we again used (2.1). This completes the proof. ∎

The following lemma is essentially that of Ferber and Kwan [7], adapted to treat $1$-degree instead of $0$-degree.

Lemma 3.2.

Let $1\leq d\leq k-1$ be integers, and let $\eta>0$ be a real constant. There exists $c=c(k)>0$ such that for all sufficiently large $q$ and $n$, the following holds.

Let $G$ be a $k$-uniform $n$-vertex hypergraph satisfying $\delta_{d}(G)\geq p\binom{n-d}{k-d}$ for some $p\in[0,1]$, and let $v\in V(G)$ be a fixed vertex. Let $S$ be a $q$-subset of $V(G)$ chosen uniformly among all subsets that contain $v$. Then with probability at least $1-\binom{q}{d}e^{-c\eta^{2}q}$, the subgraph of $G$ induced by $S$ has minimum $d$-degree at least $\delta_{d}(G[S])\geq(p-\eta)\binom{q-d}{k-d}$.

Proof.

Let $d,k,\eta$ be as in the statement of the lemma. We will choose $c$ implicitly later. Suppose also that $n$ and $q$ are large.

For a $d$-set $A\in\binom{V(G)}{d}$, let $X_{A}$ denote $\deg_{d}^{G[S]}A$ (i.e. the $d$-degree of $A$ in the induced subgraph $G[S]$) conditioned on $S\supseteq A$. We distinguish two cases: $A\ni v$ and $A\not\ni v$.

For the first case, $d$ members of $S$ are already chosen, and the remaining $q-d$ vertices are chosen uniformly from the set of $n-d$ total vertices. Therefore, each of at least $p\binom{n-d}{k-d}$ edges of $G$ containing $A$ is found in $S$ with probability $\binom{n-k}{q-k}/\binom{n-d}{q-d}=\binom{q-d}{k-d}/\binom{n-d}{k-d}$, so by linearity of expectation $\mathbb{E}X_{A}\geq p\binom{q-d}{k-d}$.

On the other hand, when $A\not\ni v$, there are two types of edges we are concerned about: those that contain $v$ in addition to $A$ and those that do not. However, we will simply ignore the first type to keep the calculations simple. To this end, note that there are at most $\binom{n-d-1}{k-d-1}$ edges of $G$ that contain $A\cup\{v\}$, so there are at least $p\binom{n-d}{k-d}-\binom{n-d-1}{k-d-1}$ edges that contain $A$, but not $v$. Since the remaining vertices of $S$ on top of $A$ and $v$ are chosen uniformly from a set of $n-d-1$ possible vertices, each of these edges appears in $S$ with probability $\binom{q-d-1}{k-d}/\binom{n-d-1}{k-d}$, so that

$$\mathbb{E}X_{A}\geq\left(p\binom{n-d}{k-d}-\binom{n-d-1}{k-d-1}\right)\frac{\binom{q-d-1}{k-d}}{\binom{n-d-1}{k-d}}=\frac{p(n-d)-(k-d)}{n-k}\frac{q-k}{q-d}\binom{q-d}{k-d}\geq\left(p-\frac{\eta}{2}\right)\binom{q-d}{k-d}$$

for $q$ and $n$ large. So in both cases we got $\mathbb{E}X_{A}\geq\left(p-\frac{\eta}{2}\right)\binom{q-d}{k-d}$.

Now, given $A$, the remaining $q-d$ or $q-d-1$ vertices of $S$ are chosen uniformly at random. If we expose these random vertices one at a time, we note that replacing one vertex by another can change $X_{A}$ by at most $\binom{q}{k-d-1}$. Then an application of the Azuma-Hoeffding inequality gives

$$\mathbb{P}\left[X_{A}\leq(p-\eta)\binom{q-d}{k-d}\right]\leq\exp\left(-\frac{(\eta/2)^{2}\binom{q-d}{k-d}^{2}}{2\binom{q}{k-d-1}^{2}(q-d)}\right)\leq e^{-c\eta^{2}q}$$

for small enough $c=c(k)>0$. Since this holds for arbitrary $A\in\binom{V(G)}{d}$, by applying a union bound to all $\binom{q}{d}$ $d$-subsets of $S$ we conclude. ∎

For integers $1\leq d\leq k-1$, write $\tilde{\beta}_{d}(k):=\liminf_{n\to\infty}c_{d}(k,n)/\binom{n-d}{k-d}$. We are now ready to prove the promised fact.

Theorem 3.3.

Let $1\leq d\leq k-1$ be integers. Then for every $\gamma,\varepsilon>0$, there exists $n_{0}$ such that for all $n\geq n_{0}$, the following holds. If $G$ is a $k$-uniform $n$-vertex hypergraph with $\delta_{d}(G)\geq(\tilde{\beta}_{d}(k)+\gamma)\binom{n-d}{k-d}$, then the entropy of $G$ satisfies

$$h(G)\geq\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right).$$

In other words, $\beta_{d}(k)\leq\tilde{\beta}_{d}(k)$.

Proof.

Let $G$ be as in the statement of the theorem and let $p=\delta_{d}(G)/\binom{n-d}{k-d}\geq\tilde{\beta}_{d}(k)+\gamma$. By definition of $\tilde{\beta}_{d}(k)$, there are arbitrarily large integers $q$ divisible by $k$ such that $c_{d}(k,q)\leq(\tilde{\beta}_{d}(k)+\gamma/2)\binom{q-d}{k-d}$.

Fix one such $q$, and call a $q$-set $S$ of vertices of $V(G)$ “good” if $\delta_{d}(G[S])\geq(p-\eta)\binom{q-d}{k-d}$ for some $0<\eta<\gamma/2$. Let $H$ be a $q$-uniform hypergraph on $V(G)$ whose edges are all good $q$-sets of $G$. Then by Lemma 3.2, $\delta_{1}(H)\geq(1-\rho)\binom{n-1}{q-1}$ for $\rho=\rho(\eta,q):=\binom{q}{d}e^{-c\eta^{2}q}$ and some constant $c>0$. Since $\rho$ goes to $0$ exponentially fast as $q$ grows to infinity with $\eta$ fixed, for $q$ sufficiently large it holds that $\rho<\frac{1}{q}\frac{n}{n-1}-\frac{1}{n-1}$, so by Theorem 2.1 the entropy of $H$ is at least $h(H)\geq\frac{n}{q}\ln\delta_{1}(H)$, achieved by some fractional perfect matching $\mathbf{y}:E(H)\to\mathbb{R}_{\geq 0}$.

By definition of the hypergraph $H$, every edge $f\in E(H)$ satisfies $\delta_{d}(G[f])\geq(\tilde{\beta}_{d}(k)+\gamma/2)\binom{q-d}{k-d}\geq c_{d}(k,q)$, so there exists a fractional perfect matching $\mathbf{x}^{f}$ of $G[f]$ with

$$h(\mathbf{x}^{f})\geq\frac{q}{k}\ln\left(\frac{k}{q}\frac{\binom{q}{d}}{\binom{k}{d}}\delta_{d}(G[f])\right)\geq\frac{q}{k}\ln\left((p-\eta)\binom{q-1}{k-1}\right).$$

Applying Lemma 3.1 then gives a fractional perfect matching $\mathbf{x}$ of $G$ that satisfies

$$h(\mathbf{x}) \geq\sum_{f\in E(H)}\mathbf{y}_{f}h(\mathbf{x}^{f})+\frac{q}{k}h(\mathbf{y})-\frac{n}{k}\ln\binom{n-k}{q-k}$$

$$\geq\frac{q}{k}\ln\left((p-\eta)\binom{q-1}{k-1}\right)\sum_{f\in E(H)}\mathbf{y}_{f}+\frac{q}{k}\frac{n}{q}\ln\left((1-\rho)\binom{n-1}{q-1}\right)-\frac{n}{k}\ln\binom{n-k}{q-k}$$

$$\geq\frac{n}{k}\ln\left((p-\eta)(1-\rho)\binom{q-1}{k-1}\frac{\binom{n-1}{q-1}}{\binom{n-k}{q-k}}\right)$$

$$\geq\frac{n}{k}\ln\left((1-\varepsilon)p\binom{n-1}{k-1}\right)$$

$$=\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right),$$

where the fourth inequality holds whenever $1/\eta$ and $q$ are large enough. This completes the proof. ∎

Note that even though we are unable to prove that $c_{d}(k,n)/\binom{n-d}{k-d}$ tends to a limit as $n\to\infty$, the previous theorem is almost equally good in practice since an application of Theorem 1.3 keeps the same order of the error term, that is, $o(n)$.

4 Bounds for approximate counting thresholds

Recall that Theorem 1.4 gives an upper bound on counting thresholds that is only a simple extension of the bound for $1$-degree, so it does not really take $d$ into account. However, it is still possible to obtain better general bounds on $\beta_{d}(k)$ by relating them to those of hypergraphs with smaller uniformity. This section pursues that goal. Our ideas rely in part on the methods of Kwan, Safavi, and Wang in [17].

First, one can reduce the case $(d,k)$ to $(1,k/d)$ whenever $d\mid k$. The resulting bound is then $1-d/k$ instead of the $1-1/k$ bound given by Theorem 1.4.

Theorem 4.1.

For all integers $1\leq d\leq k-1$ such that $d\mid k$, it holds that $\beta_{d}(k)\leq\beta_{1}(k/d)$.

Proof.

Fix $d$ and $k$ as in the statement of the theorem. Take arbitrary $\gamma,\varepsilon>0$, and let $G$ be a $k$-uniform hypergraph on $n$ vertices with $\delta_{d}(G)\geq(\beta_{1}(k/d)+\gamma)\binom{n-d}{k-d}$, where $n$ is large enough. We need to show that

$$h(G)\geq\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right).$$

Let $H$ be an auxiliary $k/d$-uniform hypergraph on vertex set $\binom{V(G)}{d}$. Its edges are the sets $f\in\binom{V(H)}{k/d}$ such that $\bigcup f\in E(G)$, where $\bigcup f$ denotes $\bigcup_{U\in f}U$. Then for every $S\in\binom{V(G)}{d}$,

$$\deg^{H}_{1}S =\left(\deg_{d}^{G}S\right)\frac{(k-d)!}{(k/d-1)!(d!)^{k/d-1}}$$

$$\geq(\beta_{1}(k/d)+\gamma)\binom{n-d}{k-d}\frac{(k-d)!}{(k/d-1)!(d!)^{k/d-1}}$$

$$\geq(\beta_{1}(k/d)+\gamma/2)\binom{\binom{n}{d}-1}{k/d-1},$$

as long as $n$ is large enough (in terms of $\gamma$). Under the same hypothesis, now in terms of both $\gamma$ and $\varepsilon$, it follows from the definition of $\beta_{1}(k/d)$ that there exists a fractional perfect matching $\mathbf{y}:E(H)\to\mathbb{R}_{\geq 0}$ of $H$ such that

$$h(\mathbf{y})\geq\frac{\binom{n}{d}}{k/d}\ln\Big((1-\varepsilon)\delta_{1}(H)\Big).$$ (4.1)

For $e\in E(G)$ and $f\in E(H)$, write $e\sim f$ whenever $\bigcup f=e$, and let $a=1/\binom{n-1}{d-1}$. Define an edge-weighting $\mathbf{x}$ of $G$ by $\mathbf{x}_{e}:=a\sum_{e\sim f\in E(H)}\mathbf{y}_{f}$. Then $\mathbf{x}$ is nonnegative. Moreover, for all $v\in V(G)$,

$$\sum_{e\ni v}\mathbf{x}_{e} =a\sum_{e\ni v}\sum_{f\sim e}\mathbf{y}_{f}=a\sum_{\begin{subarray}{c}f\in E(H)\\ v\in\bigcup f\end{subarray}}\sum_{e\sim f}\mathbf{y}$$

$$=a\sum_{\begin{subarray}{c}f\in E(H)\\ v\in\bigcup f\end{subarray}}\mathbf{y}_{f}=a\sum_{\begin{subarray}{c}S\in\binom{V(G)}{d}\\ v\in S\end{subarray}}\sum_{S\in f\in E(H)}\mathbf{y}_{f}$$

$$=a\sum_{\begin{subarray}{c}S\in\binom{V(G)}{d}\\ v\in S\end{subarray}}1=a\binom{n-1}{d-1}=1,$$

so $\mathbf{x}$ is a fractional perfect matching of $G$.

Let $N=\frac{k!}{(k/d)!(d!)^{k/d}}$ be the number of edges $f\in E(H)$ such that $e\sim f$ for any fixed edge $e\in E(G)$. Then

$$h(G)\geq h(\mathbf{x}) =\sum_{e\in E(G)}\Bigg(a\sum_{f\sim e}\mathbf{y}_{f}\Bigg)\ln\frac{1}{aN}\frac{N}{\sum_{f\sim e}\mathbf{y}_{f}}$$

$$=a\left(\ln\frac{1}{aN}\right)\sum_{f\in E(H)}\mathbf{y}_{f}+aN\sum_{e\in E(G)}\frac{\sum_{f\sim e}\mathbf{y}_{f}}{N}\ln\frac{N}{\sum_{f\sim e}\mathbf{y}_{f}}$$

$$\geq\frac{n}{k}\ln\left(\frac{(k/d)!(d!)^{k/d}}{k!}\binom{n-1}{d-1}\right)+aN\sum_{e\in E(G)}\sum_{f\sim e}\frac{1}{N}\mathbf{y}_{f}\ln\frac{1}{\mathbf{y}_{f}}$$

$$=\frac{n}{k}\ln\left(\frac{(k/d)!(d!)^{k/d}}{k!}\binom{n-1}{d-1}\right)+ah(\mathbf{y})$$

$$\geq\frac{n}{k}\ln\left((1-\varepsilon)\frac{(k/d)!(d!)^{k/d}}{k!}\binom{n-1}{d-1}\delta_{1}(H)\right)$$

$$=\frac{n}{k}\ln\left((1-\varepsilon)\frac{(k/d)\,d!}{k\dots(k-d+1)}\binom{n-1}{d-1}\delta_{d}(G)\right)$$

$$=\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right),$$

where the first inequality follows by Jensen’s inequality applied to the concave function $x\mapsto x\ln(1/x)$, and the second one follows from (4.1). This concludes the proof. ∎

Similarly, one can obtain a slightly better bound for $(d,k)$ by reducing it to the case $(d-l,k-l)$ for any $l<d$.

Theorem 4.2.

For all integers $1\leq l<d\leq k-1$, it holds that $\beta_{d}(k)\leq\beta_{d-l}(k-l)$.

Proof.

The proof is very similar to that of Theorem 4.1. Fix $l$, $d$, and $k$ as in the statement of the theorem. Take arbitrary $\gamma,\varepsilon>0$, and let $G$ be a $k$-uniform hypergraph on $n$ vertices with $\delta_{d}(G)\geq(\beta_{d-l}(k-l)+\gamma)\binom{n-d}{k-d}$, where $n$ is large enough. We need to show that

$$h(G)\geq\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right).$$

Given an $l$-set $U$ of vertices of $G$, let $H^{U}$ denote the $(k-l)$-uniform link hypergraph of $G$ at $U$, that is, a hypergraph with vertex set $V(G)\setminus U$ and edges all $(k-l)$-subsets $f$ such that $U\cup f\in E(G)$. For every $S\in\binom{V(H^{U})}{d-l}$, we have $\deg_{d-l}^{H^{U}}S=\deg_{d}^{G}(U\cup S)\geq(\beta_{d-l}(k-l)+\gamma)\binom{(n-l)-(d-l)}{(k-l)-(d-l)}$. Provided that $n$ is large enough in terms of $\gamma$ and $\varepsilon$, it follows from the definition of $\beta_{d-l}(k-l)$ that for every $U\in\binom{V(G)}{l}$, there exists a fractional perfect matching $\mathbf{x}^{U}:E(H^{U})\to\mathbb{R}_{\geq 0}$ of $H^{U}$ such that

$$h(\mathbf{x}^{U})\geq\frac{n-l}{k-l}\ln\left((1-\varepsilon)\frac{k-l}{n-l}\frac{\binom{n-l}{d-l}}{\binom{k-l}{d-l}}\delta_{d-l}(H^{U})\right).$$ (4.2)

For simplicity, given $e\in E(G)$, we write $\mathbf{x}^{U}_{e}$ for $\mathbf{x}^{U}_{e\setminus U}$. Let $a=\frac{k-l}{k}\frac{n}{n-l}\frac{1}{\binom{n}{l}}$ and define an edge-weighting $\mathbf{x}$ of $G$ by $\mathbf{x}_{e}:=a\sum_{U\in\binom{e}{l}}\mathbf{x}^{U}_{e}$ for $e\in E(G)$. Then $\mathbf{x}$ is clearly nonnegative. Moreover, for all $v\in V(G)$,

$$\sum_{e\ni v}\mathbf{x}_{e} =a\sum_{e\ni v}\sum_{U\in\binom{e}{l}}\mathbf{x}^{U}_{e}$$

$$=a\sum_{U^{\prime}\in\binom{V(G)\setminus\{v\}}{l-1}}\sum_{e\supseteq U^{\prime}\cup\{v\}}\mathbf{x}^{U^{\prime}\cup\{v\}}_{e}+a\sum_{U\in\binom{V(G)\setminus\{v\}}{l}}\sum_{e\supseteq U\cup\{v\}}\mathbf{x}^{U}_{e}$$

$$=a\sum_{U^{\prime}\in\binom{V(G)\setminus\{v\}}{l-1}}\frac{n-l}{k-l}+a\sum_{U\in\binom{V(G)\setminus\{v\}}{l}}1$$

$$=a\binom{n-1}{l-1}\frac{n-l}{k-l}+a\binom{n-1}{l}$$

$$=\frac{a(n-1)!}{(l-1)!(n-l-1)!}\left(\frac{1}{k-l}+\frac{1}{l}\right)$$

$$=a\binom{n-1}{l-1}\frac{(n-l)k}{(k-l)l}=1,$$

so $\mathbf{x}$ is a fractional perfect matching of $G$.

Let $N=\binom{k}{l}$. Then

$$h(G)\geq h(\mathbf{x}) =\sum_{e\in E(G)}\Bigg(a\sum_{U\in\binom{e}{l}}\mathbf{x}^{U}_{e}\Bigg)\ln\frac{1}{aN}\frac{N}{\sum_{U\in\binom{e}{l}}\mathbf{x}^{U}_{e}}$$

$$=a\left(\ln\frac{1}{aN}\right)\sum_{U\in\binom{V(G)}{l}}\sum_{e\supseteq U}\mathbf{x}^{U}_{e}+aN\sum_{e\in E(G)}\frac{\sum_{U\in\binom{e}{l}}\mathbf{x}^{U}_{e}}{N}\ln\frac{N}{\sum_{U\in\binom{e}{l}}\mathbf{x}^{U}_{e}}$$

$$\geq a\left(\ln\frac{1}{aN}\right)\sum_{U\in\binom{V(G)}{l}}\frac{n-l}{k-l}+aN\sum_{e\in E(G)}\sum_{U\in\binom{e}{l}}\frac{1}{N}\mathbf{x}^{U}_{e}\ln\frac{1}{\mathbf{x}^{U}_{e}}$$

$$=a\frac{n-l}{k-l}\binom{n}{l}\ln\frac{1}{aN}+a\sum_{U\in\binom{V(G)}{l}}h(\mathbf{x}^{U})$$

$$\geq\frac{n}{k}\ln\frac{1}{aN}+a\sum_{U\in\binom{V(G)}{l}}\frac{n-l}{k-l}\ln\left((1-\varepsilon)\frac{k-l}{n-l}\frac{\binom{n-l}{d-l}}{\binom{k-l}{d-l}}\delta_{d-l}(H^{U})\right)$$

$$\geq\frac{n}{k}\ln\frac{1}{aN}+a\binom{n}{l}\cdot\frac{n-l}{k-l}\ln\left((1-\varepsilon)\frac{k-l}{n-l}\frac{\binom{n-l}{d-l}}{\binom{k-l}{d-l}}\delta_{d}(G)\right)$$

$$=\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\frac{\binom{n}{l}\binom{n-l}{d-l}}{\binom{k}{l}\binom{k-l}{d-l}}\delta_{d}(G)\right)$$

$$=\frac{n}{k}\ln\left((1-\varepsilon)\frac{k}{n}\,\frac{\binom{n}{d}}{\binom{k}{d}}\,\delta_{d}(G)\right),$$

where the first inequality follows by Jensen’s inequality applied to the concave function $x\mapsto x\ln(1/x)$, the second one follows from (4.2), the third one uses the fact that $\delta_{d-l}(H^{U})\geq\delta_{d}(G)$ for every $U\in\binom{V(G)}{l}$ (with equality for at least one $U$), and the last equality follows from

$$\frac{\binom{n}{l}\binom{n-l}{d-l}}{\binom{k}{l}\binom{k-l}{d-l}}=\frac{\binom{n}{d}}{\binom{k}{d}}.$$

This concludes the proof. ∎

5 Concluding remarks

In this paper we introduced (approximate) counting thresholds for $d$-degrees in $k$-uniform hypergraphs, above which a hypergraph’s entropy is guaranteed to be large enough to ensure that the hypergraph contains at least as many perfect matchings as it is expected in a random hypergraph with the same edge density, i.e. with edge probability $p=\delta_{d}(G)/\binom{n-d}{k-d}$. Unlike the case $d\geq k/2$, where these thresholds are known to coincide, when $d<k/2$ they can diverge, and in this paper we initiate their study by showing some general upper bounds and a substitute for the convergence result available for Dirac thresholds.

Determining exact values of (approximate) counting thresholds could be an interesting problem for further research on the topic. For example, it follows from Theorem 1.4 that the approximate $1$-degree $3$-uniform counting threshold $\beta_{1}(3)$ is at most $1-1/3=2/3$. One can ask whether this is sharp, but unfortunately, we believe the answer is no. Consider Lisa Sauermann’s counterexample from [7, Section 5], which shows that Dirac and counting thresholds may diverge for $d<k/2$: it is a “bipartite” hypergraph $H_{\varepsilon}$ with vertex parts $A$ and $B$ of sizes $|A|=(1/3+\varepsilon)n$ and $B=(2/3-\varepsilon)n$ for some small $\varepsilon>0$, and edges all $3$-sets that do not have all three vertices from the same part. Calculations show that the hypergraph has the normalised minimum $1$-degree of at least $5/9$ (which is the Dirac threshold in this case), but can contain no more than $(1+o_{\varepsilon}(1))^{n}\Phi(K^{(3)}_{n})\left(\frac{4}{9}\right)^{n/3}$ perfect matchings, which is smaller than the expected number in the random hypergraph.

We believe that a family of such bipartite hypergraphs can also provide a sharp lower bound for (approximate) counting thresholds, at least in the case $(d,k)=(1,3)$. In particular, calculations show that for $0<\varepsilon<1/6$, the minimum $1$-degree of $H_{\varepsilon}$ is approximately $\delta_{1}=(\frac{1}{3}+\varepsilon)(\frac{5}{6}-\frac{\varepsilon}{2})n^{2}$, while the number of perfect matchings is

$$\ln\Phi(H_{\varepsilon})=\ln\Phi(K^{(3)}_{n})+\frac{n}{3}\Bigg( (1+3\varepsilon)\ln\left(\frac{1}{3}+\varepsilon\right)-(1-3\varepsilon)\ln\left(\frac{1}{3}-\varepsilon\right)$$

$$+(2-3\varepsilon)\ln\left(\frac{2}{3}-\varepsilon\right)-3\varepsilon\ln\varepsilon\Bigg)+o(n).$$

This is larger than the desired $\ln\Phi(K^{(3)}_{n})+\frac{n}{3}\ln(\delta_{1}/\binom{n-1}{2})$ only when $\varepsilon\gtrsim 0.04847$. In other words, we believe $\beta_{1}(3)\approx 0.61783\ll 2/3$. This is also suggested by computer search.

Acknowledgements. Parts of this paper come from the semester project that the author did as a Master student at ETH Zürich, Switzerland. The author would like to thank Barnabás Janzer, Zhihan Jin, and Benny Sudakov for their supervision of this project. The author would also like to thank Matthew Kwan, Farhood Rostamkhani, and Yiting Wang for useful comments and for spotting some mistakes.

Appendix A Proof of Theorem 1.6

The proof we present here is an adaptation of the original proof due to Hoffman [12]. Somewhat surprisingly, one single point in Theorem 1.6 implies all the others. This point is given by the following theorem.

Theorem A.1.

All strictly PMD matrices are invertible.

We postpone the proof and first show how Theorem A.1 implies Theorem 1.6.

Proof of Theorem 1.6 assuming Theorem A.1.

First let $A$ be a PMD $n\times n$ matrix. For $\lambda>0$, $\det(A+\lambda I_{n})$ is a monic polynomial in $\lambda$, so for $\lambda$ large enough, we have $\det(A+\lambda I_{n})>0$. Suppose $\det A<0$. By continuity of the determinant, there is $\lambda_{0}>0$ such that $\det(A+\lambda_{0}I_{n})=0$. But $A+\lambda_{0}I_{n}$ is a strictly PMD matrix, so $\det(A+\lambda_{0}I_{n})\neq 0$ by Theorem A.1, a contradiction. This shows $\det A\geq 0$. If $A$ is strictly PMD, we conclude again by Theorem A.1 that $\det A>0$.

Now suppose that $A$ is an invertible PMD matrix. Then $A^{-1}=\frac{1}{\det A}C(A)^{\top}$, where $C(A)$ is the cofactor matrix of $A$. By the first part of the proof and the fact that $\det A\neq 0$, we have $\det A>0$, so that the sign of the column sums of $A^{-1}$ is equal to the sign of the row sums of $C(A)$, and it suffices to show that these are nonnegative.

Let us denote by $A^{ij}$ the submatrix of $A$ with $i$-th row and $j$-th column removed. Let $1\leq i\leq n$. Then $\sum_{j=1}^{n}C(A)_{ij}=\sum_{j=1}^{n}(-1)^{i+j}\det(A^{ij})=\det A_{i\leftrightarrow\mathbbm{1}_{n}}$, where $A_{i\leftrightarrow\mathbbm{1}_{n}}$ is the matrix $A$ with the $i$-th row replaced by the all-ones vector $\mathbbm{1}_{n}$. But $A_{i\leftrightarrow\mathbbm{1}_{n}}$ is a PMD matrix as well, which implies that $\det A_{i\leftrightarrow\mathbbm{1}_{n}}\geq 0$, thus concluding the proof. ∎

With some more effort, one can show that the column sums of the inverse of strictly PMD matrices are themselves strictly positive, and this is done by Hoffman [12]. However, we do not need this additional result in this paper, so we omit its proof.

It remains to prove Theorem A.1.

A.1 Proof of Theorem A.1

The proof uses some basic theory of convex cones.

Definition 10.

Let $M$ be an $n\times m$ real matrix. The convex cone with respect to $M$ is the subset $C(M)$ of $\mathbb{R}^{n}$ of the form $\{Mx\mid x\in\mathbb{R}_{\geq 0}^{m}\}$.

Equivalently, a subset $C\subseteq\mathbb{R}^{n}$ is a convex cone if for every $x\in C$ and $\alpha\geq 0$, $\alpha x\in C$ as well.

Lemma A.2.

Let $n$ be a positive integer and let $M_{1},\dots,M_{n}$ be $n\times m_{i}$, $i=1,\dots,n$, real matrices, for some positive integers $m_{i}$, such that the cones $C_{i}=C(M_{i})$ and their opposites cover the whole space:

$$\bigcup_{i=1}^{n}(\pm C_{i})=\mathbb{R}^{n}.$$ (A.1)

Let $A$ be an $n\times n$ real matrix and suppose $A_{i*}M_{i}>0$ holds for all $i=1,\dots,n$, where $A_{i*}$ denotes the $i$-th row of $A$. Then $A$ is invertible.

Proof.

Assume that (A.1) holds and suppose $A$ is such that $A_{i*}M_{i}>0$ for all $i=1,\dots,n$. For the sake of contradiction, suppose $A$ is not invertible. Then there exists $y\in\mathbb{R}^{n}\setminus\{0\}$ such that $Ay=0$. By (A.1), $y\in C_{i}$ or $-y\in C_{i}$ for some $i$ and, without loss of generality, we can assume that $y\in C_{i}$ holds, that is, there exists $x\in\mathbb{R}_{\geq 0}^{m_{i}}\setminus\{0\}$ such that $y=M_{i}x$. This gives, combined with the hypothesis on $A_{i*}M_{i}$:

$$0=A_{i*}y=A_{i*}M_{i}x>0,$$

which is the desired contradiction. ∎

We can now proceed to the proof of Theorem A.1. Suppose $A$ is strictly PMD. The condition (1.4) can be restated as $A_{i*}\mathbbm{1}_{n}>0$ for all $i$, and similarly, the condition (1.5) is equivalent to $A_{i*}v_{k}>0$ for all $i\neq k$, where $v_{i}=-e_{i}+\frac{1}{n}\mathbbm{1}_{n}$. Therefore, $A$ is strictly PMD if and only if $A_{i*}M_{i}>0$ holds for all $i$, where $M_{i}=(v_{1}\,\dots\,v_{n})_{i\leftrightarrow\mathbbm{1}_{n}}$, that is, a matrix with column vectors $v_{1},\dots,v_{n}$, where $v_{i}$ was replaced by the all-ones vector $\mathbbm{1}_{n}$.

We want to apply Lemma A.2 to show that $A$ is invertible. For $M_{1},\dots,M_{n}$ as above, $A_{i*}M_{i}>0$ for all $i$ is already given by the strict positive mean-dominance of $A$, so it suffices to show

$$\bigcup_{i=1}^{n}\left(\pm C(M_{i})\right)=\mathbb{R}^{n}.$$

Claim A.3.

For all $i=1,\dots,n$, $\langle v_{i},\mathbbm{1}_{n}\rangle=0$ and any $n-1$ of the vectors $v_{1},\dots,v_{n}$ form a basis of $\mathbbm{1}_{n}^{\perp}$, the normal subspace of $\mathbbm{1}_{n}$.

Proof.

The first part of the claim is immediate. For the second, note that $\dim\mathbbm{1}_{n}^{\perp}=n-1$, so it suffices to show that any $n-1$ of the vectors $v_{1},\dots,v_{n}$ are linearly independent. Without loss of generality, we will show this for vectors $v_{1},\dots,v_{n-1}$. So let $\alpha_{1},\dots,\alpha_{n-1}\in\mathbb{R}$ be such that $\sum_{i=1}^{n-1}\alpha_{i}v_{i}=0$. We want to show that $\alpha_{1}=\dots=\alpha_{n-1}=0$.

We have

$$0=\sum_{i=1}^{n-1}\alpha_{i}v_{i}=\sum_{i=1}^{n-1}\alpha_{i}e_{i}+\frac{1}{n}\left(\sum_{i=1}^{n-1}\alpha_{i}\right)\mathbbm{1}_{n},$$

and taking the $n$-th coordinate, we get $0=\sum_{i=1}^{n-1}\alpha_{i}$. But then $0=\sum_{i=1}^{n-1}\alpha_{i}e_{i}$, which implies $\alpha_{i}=0$ for every $i$. ∎

Claim A.4.

Every vector $x\in\mathbbm{1}_{n}^{\perp}$ is a conical (i.e. nonnegative) combination of at most $n-1$ of the vectors $v_{1},\dots,v_{n}$.

Proof.

Note that

$$\sum_{i=1}^{n}v_{i}=\mathbbm{1}_{n}-\sum_{i=1}^{n}e_{i}=0.$$ (A.2)

By Claim A.3, $v_{1},\dots,v_{n-1}$ form a basis of $\mathbbm{1}_{n}^{\perp}$, so $x$ can be represented as a linear combination of $v_{i}$-s:

$$x=\alpha_{1}v_{1}+\dots+\alpha_{n-1}v_{n-1}.$$ (A.3)

If all $\alpha_{i}$-s are positive, we are done. Otherwise, for all $i$ such that $\alpha_{i}<0$, we can replace $v_{i}$ in (A.3) by $-\sum_{j\neq i}v_{j}$ using (A.2). This gives a representation of $x$ as a conical combination of possibly all $v_{i}$-s:

$$x=\beta_{1}v_{1}+\dots+\beta_{n}v_{n},\hskip 8.5359pt\beta_{1},\dots,\beta_{n}\geq 0.$$ (A.4)

If there is $i$ with $\beta_{i}=0$ in (A.4), we are done, so suppose this is not the case and take $i$ with the minimum value of $\beta_{i}$. By replacing again $v_{i}$ by $-\sum_{j\neq i}v_{j}$ in (A.4), $v_{i}$-term is set to $0$, while all other coefficients remain nonnegative by minimality of $\beta_{i}$, so we get the desired linear combination. ∎

We will now show

$$\bigcup_{i=1}^{n}C_{i}\supseteq\{y\mid\langle y,\mathbbm{1}_{n}\rangle\geq 0\},$$

which will then immediately imply

$$\bigcup_{i=1}^{n}(\pm C_{i})=\mathbb{R}^{n},$$

thus completing the proof. To this extent, let $y\in\mathbb{R}^{n}$ be such that $\langle y,\mathbbm{1}_{n}\rangle\geq 0$. We want to show that there is $i\in\{1,\dots,n\}$ and $x\in\mathbb{R}_{\geq 0}^{n}$ such that $y=M_{i}x$.

Let $y=y_{0}+y^{\perp}$ be the (unique) decomposition of $y$ with $y_{0}\parallel\mathbbm{1}_{n}$ and $y^{\perp}\perp\mathbbm{1}_{n}$. By Claim A.4, $y^{\perp}$ is a conical combination of at most $n-1$ vectors of $v_{1},\dots,v_{n}$. Without loss of generality, suppose $v_{1}$ is excluded from this conical representation and write $y^{\perp}=\alpha_{2}v_{2}+\dots+\alpha_{n}v_{n}$ with $\alpha_{2},\dots,\alpha_{n}\geq 0$.

We have also

$$0\leq\langle y,\mathbbm{1}_{n}\rangle=\langle y_{0},\mathbbm{1}_{n}\rangle,$$

so by posing $\alpha_{1}=\langle y_{0},\mathbbm{1}_{n}\rangle/n$, we get $\alpha_{1}\geq 0$ as well. Since now $\alpha_{1}\mathbbm{1}_{n}=y_{0}$ and $\alpha_{2}v_{2}+\dots+\alpha_{n}v_{n}=y^{\perp}$, we get $y=M_{1}x$ for $x=(\alpha_{1}\,\dots\,\alpha_{n})\geq 0$. This concludes the proof of Theorem A.1. ∎

Remark A.5.

Theorems 1.6 and A.1 actually generalise to an even broader class of matrices than strictly PMD matrices. Whilst in the definition of the strictly PMD matrices one takes the unweighted mean of row entries, it is possible to take a weighted mean instead, with weights shifted circularly by $k$ positions to the right in the condition (1.5) of Definition 7. Moreover, one can even reverse the inequality sign in (1.4) or (1.5), and Theorems 1.6 and A.1 would still hold (although with some of the promised inequalities reversed as well).

Since we only need the unweighted means, we restrict our presentation here to the (strictly) PMD matrices. We refer to the paper of Hoffman [12] for the proof of the general case.

Remark A.6.

It has been shown by Carnicer, Goodman, and Peña [3] that the set of conditions in Definition 7 is the weakest to ensure $\det A>0$ in the sense that with any of the conditions removed, there is a $n\times n$ real matrix that satisfies the remaining conditions and whose determinant is negative.

3