1 Introduction
A matching in a k-graph (k-uniform hypergraph) H is a set of vertex-disjoint edges of
$H.$
Matchings are one of the most natural objects in combinatorics, hence there are various topics related to matchings and each topic has been extensively studied. Especially, determining the maximum or average size of matchings in a given (hyper)graph is a central topic in the matching theory. For instance, Erdős matching conjecture [Reference Erdős3] is one of the most important conjectures in the extremal set theory, which regards the maximum sizes of matchings in given set systems.
Among various hypergraphs, (almost) regular hypergraphs form an interesting class of hypergraphs. For instance, Vizing’s theorem [Reference Vizing16] implies that any n-vertex d-regular graph has a matching of size at least
$\left (1 - \frac {1}{d+1} \right )\frac {n}{2}$
, thus an almost perfect matching if d is large.
For hypergraphs, Pippenger (unpublished) and Pippenger and Spencer [Reference Pippenger and Spencer14] proved that almost regular k-graphs with small codegrees have almost perfect matchings. This fact and its generalizations have numerous useful applications in design theory [Reference Glock, Kühn, Lo and Osthus4, Reference Keevash11], hypergraph coloring problems [Reference Kang, Kelly, Kühn, Methuku and Osthus10], Latin squares [Reference Montgomery13], extremal combinatorics [Reference Glock, Munhá Correia and Sudakov5, Reference Keevash and Sudakov12], and so on.
Another natural question is regarding the average size of matchings in the regular linear hypergraph. Let H be a d-regular linear k-graph and M be a matching chosen uniformly at random from the set of all matchings of
$H.$
For vertices
$v_1, \dots , v_s, u_1,\dots , u_t\in V(H)$
, denote by
$\mathcal {P}_H(\overline {v_1}, \dots , \overline {v_s}| \overline {u_1}, \dots , \overline {u_t})$
the probability that M does not cover any of
$v_1, \dots v_s$
conditioned on the event that M does not cover any of
$u_1, \dots , u_s.$
In particular,
$\mathcal {P}_H(\overline {v_1}, \dots , \overline {v_s})$
denotes the probability that M does not cover any of
$v_1, \dots v_s.$
Then the average size of matchings in H is closely related to the values of
$\mathcal {P}_H(\overline {v}).$
For distinct vertices u and v, the linearity of H implies that the set of edges containing u is disjoint from the set of edges containing v possibly except one. Moreover, d-regularity ensures that these sets have the same size. From these facts, it is reasonable to suspect that u and v are indistinguishable in terms of the number of matchings containing them. Indeed, Kahn [Reference Kahn7, Reference Kahn8] proposed the following conjecture stating that this suspicion is true.
Conjecture 1.1 (Kahn [Reference Kahn7, Reference Kahn8])
Let H be a d-regular linear k-graph. Then for all
$v \in V(H)$
, we have
To understand the meaning of the number
$d^{-1/k}$
, assume
$\mathcal {P}_H(\overline {v}) = x$
for all
$v\in V(H).$
Observe that for each edge
$e = \{v_1, \dots , v_k\}\in E(H)$
, we have
$\mathcal {P}_H(e\in M) = \mathcal {P}_H(\overline {v_1}, \dots , \overline {v_k}).$
For a vertex
$v\in V(H),$
let
$e_1, \dots , e_d$
be the edges of H containing v, where
$e_i = \{v, v_{(i, 1)}, \dots , v_{(i, k-1)}\}$
for each
$i\in [d].$
Then we have
By dividing by
$\mathcal {P}_H(\overline {v})$
on both sides, we obtain
We note that
$\mathcal {P}_H\left (\overline {v_{(i, 1)}}, \dots , \overline {v_{(i, k-1)}} \middle | \overline {v}\right ) = \mathcal {P}_{H - v}\left (\overline {v_{(i, 1)}}, \dots , \overline {v_{(i, k-1)}}\right ).$
As the linearity of H implies that deleting v does not change the set of edges containing
$v_{(i, j)}$
much, it is reasonable to suspect
$\mathcal {P}_H\left (\overline {v_{(i, 1)}}, \dots , \overline {v_{(i, k-1)}} \middle | \overline {v}\right ) = x^{k-1}.$
From this, we obtain the equality,
$x = \frac {1}{1 + d x^{k-1}},$
which has the unique positive solution
$(1 + o_d(1))d^{-1/k}.$
This provides a heuristic justification for the value
$d^{-1/k}$
in Conjecture 1.1.
Indeed, Kahn and Kim [Reference Kahn and Kim9] verified Conjecture 1.1 for graphs (which are linear
$2$
-graphs) and also provided the asymptotically correct value of the variance of the size of random matchings.
Theorem 1.2 (Kahn and Kim [Reference Kahn and Kim9])
Let G be an n-vertex d-regular graph. Let M be a random matching chosen uniformly at random from the set of all matchings of
$G.$
Then for all
$v\in V(G)$
, we have
-
(a) $\mathcal {P}_G(\overline {v}) = (1 + o_d(1))d^{-1/2}$
, so the expectation of
$|M|$
is
$\left (1 - \frac {1 + o_d(1)}{\sqrt {d}} \right )\frac {n}{2}$
, -
(b) the variance of $|M|$
is
$(1 + o_d(1))\frac {n}{4\sqrt {d}}$
.
They further conjectured the following, which is stronger than Conjecture 1.1.
Conjecture 1.3 (Kahn and Kim [Reference Kahn and Kim9])
Let
$k \geq 2$
be an integer and H be an n-vertex d-regular linear k-graph. Let M be a random matching chosen uniformly at random from the set of all matchings of H. Then for all
$v\in V(H)$
, we have
-
(a) $\mathcal {P}_G(\overline {v}) = (1 + o_d(1))d^{-1/k}$
, -
(b) the variance of $|M|$
is
$(1 + o_d(1))\frac {n}{k^2 d^{1/k}}$
.
Theorem 1.2 implies that the statistics for the random matchings of large regular graphs hardly depend on their specific structures. Surprisingly, this is no longer true for hypergraphs.
Theorem 1.4. Let
$k> 2$
be an integer and
$d_0, \varepsilon $
be positive real numbers. Then there exist
$d> d_0$
and d-regular linear k-graph H such that the following holds. There are two vertices
$v_1, v_2 \in V(H)$
which satisfies the following.
-
○ $\mathcal {P}_H(\overline {v_1})> 1 - \frac {1 + \varepsilon }{d^{k - 2}},$
-
○ $\mathcal {P}_H(\overline {v_2}) < \frac {1 + \varepsilon }{d+1}.$
This not only disproves Conjecture 1.1 (as well as Conjecture 1.3), it shows that the gap between
$\mathcal {P}_H(\overline {v_1})$
and
$\mathcal {P}_H(\overline {v_2})$
can be large, one being
$1 - o_d(1)$
and the other being
$o_d(1).$
Indeed, the following theorem determines the correct range of
$\mathcal {P}_H(\overline {v})$
, showing that Theorem 1.4 is best possible.
Theorem 1.5. Let
$k> 2$
be an integer and
$\varepsilon> 0$
be a real number. Then there exists
$d_0> 0$
such that for all
$d \geq d_0$
and for all d-regular linear k-graph H, we have
for all
$v\in V(H).$
To prove Theorem 1.5, we extend the celebrated result of Godsil [Reference Godsil6] on matching polynomials and paths in graphs in Section 3. One direct corollary of Godsil’s result is that for every graph G and
$v \in V(G),$
there is a tree T and a vertex
$u \in V(T)$
such that
$\mathcal {P}_G(\overline {v}) = \mathcal {P}_T(\overline {u}).$
This means that we can count on
$\mathcal {P}_T(\overline {u})$
instead of
$\mathcal {P}_G(\overline {v})$
and the structure of T allows us to compute
$\mathcal {P}_T(\overline {u})$
in a recursive manner. This is the main idea of the proof of Theorem 1.2. We generalize this result into hypergraphs. This may be of independent interest.
Organization
We prove Theorem 1.4 in Section 2 by explicitly constructing the regular linear k-graph H that satisfies the conclusion of Conjecture 1.4. In Section 3, we extend Godsil [Reference Godsil6]’s result to hypergraphs by defining a new type of walk on hypergraphs that we refer to as conflict-free walk. Using this result, we prove Theorem 1.5 in Section 4. Lastly, we discuss several concluding remarks in Section 5.
2 Random matchings and dynamical systems
2.1 d-extendable linear hypergraphs
The idea to prove Theorem 1.4 is to define an operation that can inductively construct a hypertree-like structure while keeping the degree condition. For this, we introduce some definitions. We say a k-graph H is d-extendable if all vertices of H have degree d except one vertex v of degree
$d-1.$
We say that the vertex v of degree
$d-1$
is the head of H and write it as
$\mathrm {head}(H).$
The following lemma shows the existence of a d-extendable linear k-graph.
Lemma 2.1. Let
$k \geq 2$
and
$\ell \geq 0$
be non-negative integers. Then there is a
$(k\ell + 1)$
-extendable linear k-graph
$H.$
Proof. We use induction on
$\ell .$
The base case, when
$\ell = 0$
, is trivial by taking a single edge with one isolated vertex. Denote this k-graph by
$H_0.$
Now we assume we have a
$(k(\ell - 1) + 1)$
-extendable linear k-graph
$H_{\ell - 1}.$
Claim 2.1. For every
$d \geq 1$
, there is a d-regular linear k-graph.
Proof of Claim 2.1
We use induction on
$d.$
If
$d = 1$
, we take a single edge, then this is a
$1$
-regular linear hypergraph. Now assume there is a
$(d-1)$
-regular linear k-graph
$F.$
Consider
$F_1, \dots , F_k$
disjoint copies of
$F.$
We add a perfect matching on
$V(F_1) \cup \cdots \cup V(F_k)$
where each edge of the perfect matching contains exactly one vertex of
$F_i$
for each
$i\in [k].$
Then the obtained hypergraph is d-regular and still a linear hypergraph. This proves the claim.
By Claim 2.1, we can take a
$(k\ell + 1)$
-regular linear k-graph
$F.$
Let
$F_1, \dots , F_{k-1}$
be disjoint copies of
$F.$
We choose an edge
$e_i = \{v_{(i, 1)}, \dots , v_{(i, k)}\}$
of
$F_i$
for each
$i\in [k-1].$
We introduce a new vertex
$v'$
that is disjoint from
$\bigcup _{i\in [k-1]}V(F_i)$
and remove
$e_i$
from
$F_i$
for each
$i\in [k-1].$
Now we add a new hyperedge
$\{v', v_{(i, 1)}, \dots , v_{(i, k-1)}\}$
for each
$i\in [k-1]$
and we finally add a hyperedge
$\{v', v_{(1, k)}, \dots , v_{(k-1, k)}\}.$
Let us write this hypergraph as
$H^{\prime }_{\ell }.$
We note that the degree of
$v'$
in
$H^{\prime }_{\ell }$
is k and the other vertices have degree
$k\ell + 1.$
Now we consider a disjoint
$\ell $
copies of
$H^{\prime }_{ell}$
and then identify all the degree k vertices. Denote such a hypergraph as
$H_{\ell }$
and let v be the vertex of
$H_{\ell }$
, which is the identified vertex of
$\ell $
copies of
$H^{\prime }_{\ell }$
. Note that except for v, all the other vertices of
$H_{\ell }$
come from exactly one copy of
$H^{\prime }_{\ell }$
which is not degree k, so its degree is
$(k\ell + 1)$
. For v, we identify
$\ell $
vertices of degree k, so degree of v in
$H_{\ell }$
is
$k\ell $
. Hence
$H_{\ell }$
is the desired
$(k\ell + 1)$
-extendable linear k-graph.
We now define an operation that extends a d-extendable linear k-graph into a larger d-extendable linear k-graph as follows.
Definition 2.2. Let F be a d-extendable linear k-graph. Let
$F'$
be a disjoint union of copies
$F_{(i, j)}$
of F where
$i\in [d-1]$
and
$j\in [k-1].$
We introduce a new vertex v which is disjoint from
$V(F').$
We now define a k-graph
$S_d(F)$
as
and
Let
$S_d^{(0)} = F$
and for non-negative integer
$\ell $
, we inductively define
$S_d^{(\ell )}(F)$
by
$S_d^{(\ell )}(F) = S_d(S_d^{(\ell -1)}(F)).$
We note that if F is a d-extendable linear k-graph, then so is
$S_d(F)$
and the newly introduced vertex v in the definition of
$S_d(\cdot )$
becomes a new head. Thus
$S_d^{(\ell )}(F)$
is well-defined. We will use the operation
$S_d(\cdot )$
iteratively to prove Theorem 1.4. To do this, we analyze several numerical properties that are related to
$S_d(\cdot ).$
2.2 Attractors on extreme points
From now on, we consider
$k> 2$
to be a fixed integer. For all integer
$d\geq 2$
, we define a function
$g_{d}(x)$
and
$f_{d}(x)$
as follows.
and
As the function
$q(x) := x/g_{d}(x)$
is an increasing function with
$q(0) < 1 < q(1),$
there is a unique solution
$0 < \alpha _{d} < 1$
such that
$\alpha _{d} = g_{d}(\alpha _{d}).$
It is routine to check
$\alpha _{d} = (1 - o_d(1))d^{-1/k}$
since
$(1 + (d-1)(1 -o_d(1))^{k-1}d^{-(k-1)/k})^{-1} = (1 - o_d(1))d^{-1/k}$
. The purpose of this section is to show that the dynamical system
$x_{\ell + 1} = f_d(x_{\ell })$
starting from
$x_0 \in [0, 1]$
has two attractors, one in
$(0, \alpha _d)$
and another in
$(\alpha _d, 1).$
Lemma 2.3. For sufficiently large d, the equation
$x = f_d(x)$
defined on the interval
$[0, 1]$
has exactly three solutions
$0 < \gamma _d < \alpha _d < \beta _d < 1$
.
Proof of Lemma 2.3
We first show that the equation
$x = f_d(x)$
has at most one solution on the interval
$(\alpha _d, 1].$
Claim 2.2. For all x in the interval
$(\alpha _d, \frac {1}{2}],$
the inequality
$f_d(x)> x$
holds.
Proof of Claim 2.2
Let
$x = \alpha _d \mu $
, where
$1 < \mu \leq \frac {1}{2\alpha _d}.$
Then we have
The penultimate equality is obtained from the fact that
$(1 + (d-1)\alpha _d^{k-1}) = 1/\alpha _d$
since
$\alpha _d$
is the unique fixed point of
$g_d$
. Since
$f_d(x) = g_d(g_d(x))$
, we have
which is deduced by the substitution
$\mu ' := \alpha _d + (1 - \alpha _d)\mu ^{k-1}$
, where
$\mu '$
is regarded as the new
$\mu $
in the above expression for
$g_d(x)$
. Hence, to complete the proof, it suffices to show
equivalently,
holds. Let
$h(\mu ) := \alpha _d \mu + \frac {(1 - \alpha _d) \mu }{(\alpha _d + (1 - \alpha _d)\mu ^{k-1})^{k-1}}.$
Then for all
$1 \leq \mu \leq 2$
, we have
For the last inequality, we use the condition
$k> 2.$
Since
$h(1) = 1 \leq 1$
, for all
$\mu \in (1, 2]$
, we have
$h(\mu ) < 1.$
Now, we consider the case when
$\mu \in (2, \frac {1}{2\alpha _d}].$
Then we have
This proves the claim.
Claim 2.3. For all
$x\in (\frac {1}{2}, 1)$
, we have
$f_d'(x) < 1.$
Proof of Claim 2.3
Note that
$f_d(x) = 1 - (d-1)\cdot ((d-1) + (1 + (d-1)x^{k-1})^{k-1})^{-1}$
. Thus, by computing the derivative directly, we have
This proves the claim.
Assume we have two distinct solutions
$x_1 < x_2$
for the equation
$x = f_d(x)$
, where
$x_1, x_2 \in (\alpha _d, 1].$
We note that
$1 \neq f_d(1)$
, so neither
$x_1$
nor
$x_2$
is
$1.$
By Claim 2.2, we have
$\frac {1}{2} < x_1 < x_2 < 1.$
By Claim 2.3, the function
$f_d(x) - x$
is strictly decreasing when
$x> \frac {1}{2}.$
This implies there are no two distinct solutions in the interval
$(\alpha _d, 1]$
, a contradiction. Thus there is at most one solution in
$(\alpha _d, 1).$
Since
$f_d(1) < 1$
and
$f_d(\frac {1}{2})> \frac {1}{2}$
, there is a unique solution
$\beta _d \in (\alpha _d , 1]$
by the intermediate value theorem.
Now, let
$\gamma _d := g_d(\beta _d).$
Then it is easy to see that
$\gamma _d$
is also a solution of the equation
$x = f_d(x).$
As
$\alpha _d$
is the unique solution of
$g_d(x) = x$
,
$\gamma _d$
is distinct from both
$\alpha _d$
and
$\gamma _d.$
Since
$g_d$
is decreasing function, and
$\beta _d> \alpha _d$
, this implies
$0 < \gamma _d < \alpha _d.$
Assume there is another solution
$\gamma ^{\prime }_d \in (0, \alpha _d)$
of the equation
$x = f_d(x)$
, where
$\gamma ^{\prime }_d$
is distinct from
$\gamma _d.$
Then
$g_d(\gamma ^{\prime }_d)$
is also a solution of
$x = f_d(x)$
and since
$g_d$
is a decreasing function, we have
$\beta _d \neq g_d(\gamma ^{\prime }_d) \in (\alpha _d, 1).$
This contradicts the fact that
$\beta _d$
is the unique solution of
$x = f_d(x).$
This completes the proof.
From Lemma 2.3 and the intermediate value theorem, it is easy to check the following.
Observation 2.4. For all sufficiently large d, we have
$\beta _d = 1 - \frac {1 + o_d(1)}{d^{k-2}}$
, and
$\gamma _d = \frac {1 + o_d(1)}{d + 1}.$
For each
$x\in [0, 1]$
, we have
The next proposition states that if a strictly increasing function h and a point p with
$p = h(p)$
have an interval I containing p which satisfies
$h(a)> a$
and
$h(b) < b$
for all
$a < p < b$
and
$a, b \in I$
, then the dynamical system
$p_{i + 1} = h(p_{i})$
starting from a point
$p_0 \in I$
eventually converges to
$p.$
Proposition 2.5. Let h be a strictly increasing real-valued continuous function that is defined on an interval I and there is a point
$p\in I$
such that
$p = h(p).$
Assume that
$h(a)>a$
and
$h(b)<b$
for all
$a,b\in I$
with
$a<p<b$
. Let
$p_0 \in I$
be an arbitrary point and define
$p_{i+1} = h(p_{i})$
inductively for each
$i \in \mathbb {Z}_{\geq 0}.$
Then we have
Proof of Proposition 2.5
If
$p_0 = p$
, then obviously
$\lim _{i\to \infty } p_i = p$
as p is the fixed-point. Hence, we may assume that
$p_0 \neq p$
. We first consider the case
$p_0 < p.$
Since h is a strictly increasing function and
$h(a)> a$
for all
$a < p$
in the interval I, the sequence
$\{p_i\}_{i\in \mathbb {Z}_{\geq 0}}$
is a strictly increasing function. We claim that the sequence
$\{p_{i}\}_{i\in \mathbb {Z}_{\geq 0}}$
is bounded from above by
$p.$
Assume this is not true. Let
$\ell $
be the smallest non-negative integer such that
$p_{\ell }> p.$
We note that
$p_0 < p$
, so
$\ell> 1.$
Then
$p_{\ell } = h(p_{\ell - 1})$
and
$p_{\ell - 1 } \leq p.$
Since h is strictly increasing, this implies
$p_{\ell } = h(p_{\ell - 1}) \leq h(p) = p$
, a contradiction.
Thus the sequence
$\{p_{i}\}_{i\in \mathbb {Z}_{\geq 0}}$
is bounded from above by p and it is a strictly increasing function, so the limit
$\lim _{i \to \infty } p_{i}$
exists and its value is bounded from above by
$p.$
Suppose
$p' < p$
is the limit value of the sequence
$\{p_{i}\}_{i \in \mathbb {Z}_{\geq 0}}.$
Note that as h is a strictly increasing function, its inverse function
$h^{-1}$
exists. Since
$p' < p$
, we have
$h^{-1}(p') < p'.$
By the definition of the limits of the sequence, there exists
$\ell $
such that
$h^{-1}(p') < p_{\ell }.$
Then we have
$p_{\ell + 1}> p'$
since h is a strictly increasing function. Moreover, the sequence
$\{p_i\}_{i\in \mathbb {Z}_{\geq 0}}$
is a strictly increasing sequence, which contradicts the assumption that the limit of the sequence is
$p'.$
This implies
$\lim _{i\to \infty } p_i = p.$
Now we consider the last case that
$p_0> p$
. For this case, let
$\hat {I} = -I$
be an interval and
$\hat {h}$
be a function defined on
$\hat {I}$
such that
$\hat {h}(x) := -h(-x)$
. Then we note that
$\hat {h}$
is a strictly increasing and continuous function on
$\hat {I}$
with
$\hat {h}(-p) = -p$
and also
$\hat {h}(c)> c$
and
$\hat {h}(d) < d$
for all
$c, d\in \hat {I}$
with
$c < -p < d$
. As
$-p_0 < -p$
, by symmetry, we deduce that
$\lim _{i\to \infty } p_i = p$
. This completes the proof.
From Observation 2.4 and Proposition 2.5, we directly obtain the following lemma.
Lemma 2.6. Let
$p_0 \in [0, 1]$
and recursively define
$p_{i+1} = f_d(p_i)$
for each
$i\in \mathbb {Z}_{\geq 0}.$
Then we have
2.3 Proof of Theorem 1.4
In this section, we prove the following lemma. Theorem 1.4 will be deduced from this lemma.
Lemma 2.7. For all sufficiently large
$d \equiv 1 \pmod {k},$
there is a d-extendable linear k-graph
$F_0$
such that the following holds.
-
○ $\mathcal {P}_{S_d^{(2\ell )}(F_0)}\left (\overline {\mathrm {head}(S_d^{(2\ell )}(F_0))}\right ) = (1 + o_{\ell }(1))\beta _d,$
-
○ $\mathcal {P}_{S_d^{(2\ell - 1)}(F_0)}\left (\overline {\mathrm {head}(S_d^{(2\ell - 1)}(F_0))}\right ) = (1 + o_{\ell }(1))\gamma _d.$
We use the following simple observation crucially in the proof of Lemma 2.7.
Observation 2.8. Let H be a disjoint union of k-graphs
$H_1, H_2, \dots , H_m.$
For each
$i\in [m]$
, let
$v_i \in V(H_i)$
be arbitrary vertices. Then for the uniformly chosen random matching M of
$H,$
the events
$v_1\notin M, \dots , v_m\notin M$
are mutually independent. Moreover, we have
$\mathcal {P}_H(\overline {v_i}) = \mathcal {P}_{H_i}(\overline {v_i})$
for each
$i\in [m].$
From the above observation, we can deduce the following lemma.
Lemma 2.9. Let H be a linear k-graph and
$v\in V(H)$
be a vertex such that
$H - v$
is a disjoint union of linear k-graphs
$\{H_{(i, j)}: i\in [m], j\in [k-1]\}.$
Let
$e_1,\dots , e_m$
be the edges of H containing
$v,$
where
$e_i = \{v, v_{(i, 1)}, \dots , v_{(i, k-1)}\}$
. Assume that for each
$i\in [m]$
and
$j\in [k-1]$
, we have
$e_i\cap V(H_{(i, j)}) = \{v_{(i, j)}\}.$
Then we have
Proof of Lemma 2.9
We do the same calculation that we presented in Section 1. Since for each
$i\in [m]$
,
$\mathcal {P}_{H}(e_i \in M) = \mathcal {P}_{H}\left (\overline {v}, \overline {v_{(i, 1)}}, \dots , \overline {v_{(i, k-1)}} \right )$
, we obtain
By dividing each side of (1) by
$\mathcal {P}_{H}(\overline {v})$
and then taking inverses, we obtain
We note that for each
$i\in [m]$
,
$\mathcal {P}_{H}\left (\overline {v_{(i, 1)}}, \dots , \overline {v_{(i, k-1)}} \middle | \overline {v} \right )$
is the same as
$\mathcal {P}_{H - v}\left (\overline {v_{(i, 1)}}, \dots , \overline {v_{(i, k-1)}}\right ).$
Since
$H - v$
is a disjoint union of
$H_{(i, j)}$
, by Observation 2.8, for each
$i\in [m]$
, we have
By combining (2) and (3), we obtain the desired formula. This completes the proof.
We are now ready to prove Lemma 2.7.
Proof of Lemma 2.7
Let F be a d-extendable linear k-graph obtained by Lemma 2.1.
Claim 2.4. Let F be a d-extendable linear k-graph. Then we have
Proof of Claim 2.4
If we remove the head of
$S_d(F)$
from
$S_d(F)$
, then the remaining hypergraph is a disjoint union of copies of F, and by the definition of the operation
$S_d(\cdot )$
, we can apply Lemma 2.9 to
$S_d(F)$
and the head of
$S_d(F).$
Since the head of
$S_d(F)$
has degree
$d-1$
, by Lemma 2.9, the desired equality holds. This proves the claim.
The next claim states that the probability that a random matching does not contain the head of F cannot be the value
$\alpha _d$
, which is one of the fixed points of the function
$f_d$
that is highly unstable.
Claim 2.5.
$\mathcal {P}_F\left (\overline {\mathrm {head}(F)}\right ) \neq \alpha _d.$
Proof of Claim 2.5
The number
$\mathcal {P}_F\left (\overline {\mathrm {head}(F)}\right )$
can be computed by dividing the number of matchings in
$F - v$
by the number of matchings in F, so the number
$\mathcal {P}_F\left (\overline {\mathrm {head}(F)}\right )$
is a rational number. Hence, to finish the proof, it suffices to show that
$\alpha _d$
is irrational. Assume
$\alpha _d$
is a rational number and it is
$\frac {n}{m}$
for some integer
$n, m$
which are coprime to each other. Then we have
$\frac {n}{m} + \frac {(d - 1)n^k}{m^k} = 1.$
Thus
$(d - 1)n^k = m^{k-1}(m - n).$
Note that the left-hand side is divisible by n while the right-hand side is not divisible by n because n and m are coprime, a contradiction. This proves the claim.
By Claim 2.5, we know that
$\mathcal {P}_{F}\left (\overline {\mathrm {head}(F)}\right ) \neq \alpha _d.$
If
$\mathcal {P}_{F}\left (\overline {\mathrm {head}(F)}\right )> \alpha _d$
, then we set
$F_0 = F.$
Otherwise, we set
$F_0 = S_d(F).$
Then by Claim 2.4, we have
Let
$p_{i} = \mathcal {P}_{S_d^{(i)}(F_0)}\left (\overline {\mathrm {head}(S_d^{(i)})(F_0)}\right )$
for each
$i\in \mathbb {Z}_{\geq 0}.$
Then by Claim 2.4, we have
$p_{i+1} = g_d(p_i)$
for each
$i\in \mathbb {Z}_{\geq 0}$
and
$\alpha _d < p_0 \leq 1.$
Since
$f_d(x) = g_d(g_d(x))$
, for each
$i\in \mathbb {Z}_{\geq 0}$
, we have
$p_{i+2} = f_d(p_i).$
Then by Lemma 2.6, the sequence
$\{p_{2i}\}_{i\in \mathbb {Z}_{\geq 0}}$
converges to
$\beta _d$
as i goes to infinity. Similarly, since
$0 < p_1 = g_d(p_0) < \alpha _d$
holds, the sequence
$\{p_{2i-1}\}_{i\in \mathbb {Z}_{\geq 0}}$
converges to
$\gamma _d$
as i goes to infinity. This completes the proof.
We have collected all ingredients to prove Theorem 1.4.
Proof of Theorem 1.4
Let
$d \equiv 1 \pmod {k}$
be a sufficiently large integer in terms of
$\varepsilon $
and let
$\delta $
be a small positive real number in terms of
$\varepsilon .$
By Lemma 2.7, there is a d-extendable linear k-graph
$F_0$
and
$\ell $
such that
and
Let
$H_0$
be a hypergraph
$S_d^{(2\ell + 1)}(F_0).$
Now we consider
$H' = \bigcup _{i\in [d], j\in [k-1]} H_{(i, j)}$
which is a disjoint union of
$(k-1)d$
copies of
$H_0.$
For each
$i\in [d]$
and
$j\in [k-1]$
, let
$v_{(i, j)}$
be the head of
$H_{(i, j)}.$
We now introduce a new vertex v that is disjoint from
$V(H').$
Define a k-graph H as
$V(H) = V(H') \cup \{v\}$
and
$E(H) = E(H') \cup \bigcup _{i\in [d-1]} \{v, v_{(i, 1)}, \dots , v_{(i, k-1)}\}.$
Since
$H_0$
is a d-extendable linear k-graph, we observe that H is a d-regular linear k-graph.
We now claim that H, v,
$v_{(1, 1)}$
would be the hypergraph and vertices that satisfy the conclusion of Theorem 1.4. Then Lemma 2.9 and (4) imply
Similarly, Lemma 2.9 and (5) imply
This completes the proof.
3 Conflict-free walks and matching polynomials
In this section, we generalize Godsil’s result [Reference Godsil6] into hypergraphs. We start with matching polynomials for hypergraphs. The matching polynomial of an n-vertex k-graph H is given by
where
$p(H, i)$
is the number of distinct matchings of size i in H where we let
$p(H, 0) = 1.$
A similar notion of the matching polynomial of H is the matching-generating polynomial of H, which is given by
We note that we have
which is an identity between the matching polynomials and matching-generating polynomials.
The study of matching polynomials for hypergraphs was recently initiated; to get more information on it, we recommend to see [Reference Clark and Cooper2, Reference Su, Kang, Li and Shan15, Reference Zhang, Kang, Shan and Bai17].
As the purpose of this section is to extend the result of Godsil [Reference Godsil6] into hypergraphs, we recall Godsil’s notion of path-tree. Let G be a graph and v be a vertex of
$G.$
The path-tree
$T = T(G, v)$
of G rooted at v is a tree such that the vertex set of T is the paths in G which start from v and we join two distinct paths in
$T(G, v)$
whenever one is a maximal subpath of the other. The main theorem of [Reference Godsil6] is the following.
Theorem 3.1 (Godsil [Reference Godsil6])
Let G be a graph and
$v \in V(G).$
Then we have
where V is a one-vertex path
$(v)$
of
$G.$
By combining Theorem 3.1 and (6), we obtain
This implies that we can convert the host graph to a path-tree, so we can recursively compute the value of
$\mathcal {P}_G(\overline {v}).$
Our goal for this section is to construct a hypergraph analog of a path-tree and establish a similar identity to Theorem 3.1 for hypergraphs. Let H be a hypergraph and
$v_1, \dots , v_n \in V(H)$
be distinct vertices and
$e_1, \dots , e_{n-1} \in E(H)$
be distinct edges of
$H.$
We say
$W = (v_1, e_1, v_2, \dots , v_{n-1}, e_{n-1}, v_n)$
is a Berge-path starting from
$v_1$
and ending at
$v_n$
if
$v_i, v_{i+1} \in e_i$
for each
$i\in [n-1].$
This notion was introduced by Berge [Reference Berge1]. A k-graph T is a k-uniform hypertree if, for every pair of vertices u and v, there is a unique Berge-path that starts from u and ends at
$v.$
Definitions of rooted k-uniform hypertree and its rooted sub-hypertree are the obvious hypergraph versions of rooted trees and subtrees in graph theory.
Berge-paths usually play the role of a hypergraph version of paths in several topics related to hypergraphs. However, to extend the notion of the path into an appropriate hypergraph analog that matches Theorem 3.1, we need a new type of Berge-path, which we call conflict-free walk.
Definition 3.2. Let H be a k-graph and
$\prec $
be an arbitrary linear ordering of
$V(H).$
Let
$\ell \geq 1$
be an integer,
$v_0, \dots , v_{\ell }\in V(H)$
and
${v_{i-1}, v_i}\subset e_i \in E(H)$
for each
$i\in [\ell ].$
Let
$e_i = \{v_{i-1}, u_{(i, 1)}, \dots , u_{(i, k-2)}, v_i\}$
and
$C_i = \{u_{(i, j)}: u_{(i, j)} \prec v_i, j\in [k-2]\} \cup \{v_{i-1}\}$
for each
$i\in [\ell ].$
We say a Berge-path
$W = (v_0, e_1, v_1, e_2, v_2, \dots , v_{\ell - 1}, e_{\ell }, v_{\ell })$
is a conflict-free walk that starts from
$v_0$
and ends at
$v_{\ell }$
if for each
$2\leq i\leq \ell $
, the edge
$e_i$
is disjoint from the set
$\bigcup _{j=1}^{i-1} C_j.$
We also consider a one-vertex Berge-path
$V = (v)$
as a conflict-free walk that starts from v and ends at
$v.$
We now define k-walk-tree, which is a hypergraph analog of the path-tree.
Definition 3.3. Let H be a k-graph,
$v\in V(H),$
and we fix a linear ordering
$\prec $
of
$V(H).$
We define a k-walk-tree
$T(H, v)$
of H rooted at v as follows. The vertex set of
$T(H, v)$
is the set of conflict-free walks that start from
$v.$
For the edge set, we join k conflict-free walks
$W_0, W_1, \dots , W_{k-1}$
as a hyperedge of
$T(H,v)$
if there is an edge
$e = \{u_0, \dots , u_{k-1}\} \in E(H)$
such that
$W_0$
is a conflict-free walk that starts from v and ends at
$u_0$
and for each
$i\in [k-1]$
, the conflict-free walk
$W_i$
ends at
$u_i$
and it is obtained from
$W_0$
by adding an edge
$e.$
The following observation directly follows from Definition 3.2.
Observation 3.4. Let H be a k-graph,
$v\in V(H),$
and we fix a linear ordering
$\prec $
of
$V(H).$
Let
$e_1, \dots , e_m \in E(H)$
be the set of edges that contain v such that
$e_i = \{v, u_{(i, 1)}, \dots , u_{(i, k-1)}\}$
and
$u_{(i, 1)} \prec \cdots \prec u_{(i, k-1)}$
for each
$i\in [m].$
Then the following holds.
-
(i) $T(H, v)$
is a k-uniform hypertree, -
(ii) if H is a hypertree, then $T(H, v)$
is isomorphic to H, where
$V = (v)$
in
$T(H, v)$
is mapped to v in H, -
(iii) $T(H, v)$
can be obtained from the collection of disjoint unions of hypertrees $$ \begin{align*}\Big\{\bigcup_{j = 1}^{k-1} T(H - \{v, u_{(i, 1)}, \dots, u_{(i, j-1)}\}, u_{(i, j)}): i\in [m]\Big\}\end{align*} $$by adding a hyperedge $\{v, (u_{(i, 1)}), \dots , (u_{(i, k-1)})\}$
for each
$i\in [m]$
, where
$(u_{(i, j)})$
is a root of
$T(H - \{v, u_{(i, 1)}, \dots , u_{(i, j-1)}\}, u_{(i, j)})$
for each
$i\in [m]$
and
$j\in [k-1].$
We note that if
$k = 2$
, then conflict-free walks are paths and k-walk-trees are path-trees.
We now claim that the k-walk-tree is an appropriate generalization of Godsil’s path-tree.
Theorem 3.5. Let H be a k-graph,
$v \in V(H),$
and we fix a linear ordering of
$V(H).$
Then we have
where V is a one-vertex conflict-free walk
$(v).$
To prove Theorem 3.5, we collect the following two lemmas.
Lemma 3.6. Let H be a k-graph which is a disjoint union of two vertex-disjoint k-graphs
$H_1$
and
$H_2.$
Then we have
The proof of Lemma 3.6 can be directly obtained from the definition of the matching polynomial.
Lemma 3.7 (Su, Kang, Li, and Shan [Reference Su, Kang, Li and Shan15])
Let H be a k-graph and
$v\in V(H).$
Let
$e_1, \dots , e_m \in E(H)$
be the set of edges containing
$v.$
Denote
$V(e_i)$
by the set of vertices of
$e_i$
for each
$i\in [m].$
Then we have
Proof of Theorem 3.5
We use induction on the number of vertices of
$H.$
If
$V(H) \leq k$
, then H is edgeless or it has only one edge. Then by Observation 3.4
$(ii),$
the theorem is true. Now we assume
$V(H)> k.$
Let
$e_1, \dots , e_m \in E(H)$
be the set of edges that contain v such that
$e_i = \{v, u_{(i, 1)}, \dots , u_{(i, k-1)}\}$
and
$u_{(i, 1)} \prec \cdots \prec u_{(i, k-1)}$
for each
$i\in [m].$
Then we have
Here,
$V = (v)$
and
$U_{(i, j)}$
is the natural conflict-free walk that starts from v that corresponds to the vertex
$u_{(i, j)}$
for each
$i\in [m]$
and
$j\in [k-1].$
Similarly,
$E_i$
is the edge of
$T(H, v)$
that naturally corresponds to
$e_i$
for each
$i\in [m].$
This completes the proof.
By (6) and Theorem 3.5, we also obtain
where
$V = (v)$
. Thus we deduce the following corollary.
Corollary 3.8. Let H be a k-graph and
$v\in V(H)$
,
$V = (v).$
Then we have
4 Proof of Theorem 1.5
In this section, we prove Theorem 1.5 by using Corollary 3.8. We start with the following proposition.
Proposition 4.1. Let H be a k-graph,
$v\in V(H),$
and we fix a linear ordering
$\prec $
of
$V(H).$
Let
$e_1, \dots , e_m \in E(H)$
be the set of edges that contain v such that
$e_i = \{v, u_{(i, 1)}, \dots , u_{(i, k-1)}\}$
and
$u_{(i, 1)} \prec \cdots \prec u_{(i, k-1)}$
for each
$i\in [m].$
Then we have
Proof of Proposition 4.1
We observe that the probability of the random matching containing an edge
$e_i$
is the same as the probability that the random matching M does not contain all the vertices of
$V(e_i)$
for each
$i\in [m].$
Thus we have
By dividing by
$\mathcal {P}_H(\overline {v})$
, we obtain
By the chain rule of the conditional probability, we have
for each
$i\in [m].$
Finally, we note that
holds for each
$i\in [m]$
and
$j\in [k-1].$
By combining (8)–(10), we obtain the desired equality. This completes the proof.
From now on, we fix our k-graph H,
$v\in V(H)$
, and the linear order
$\prec $
on
$V(H).$
We denote by V the one-vertex conflict-free walk
$(v)$
and T the k-walk-tree
$T(H, v).$
For a conflict-free walk U that starts from v, we write
$T(U)$
for the sub-hypertree of T rooted at
$U.$
Lemma 4.2. Let
$E_1, \dots , E_m$
be the set of edges that contain V in
$T.$
Let
$E_i = \{V, U_{(i, 1)}, \dots , U_{(i, k-1)}\}$
for each
$i\in [m].$
Then we have
Proof of Lemma 4.2
Let
$e_1, \dots , e_m \in E(H)$
be the set of edges that contain v such that for each
$i\in [m]$
and
$j\in [k-1]$
, the edge
$e_i = \{v, u_{(i, 1)}, \dots , u_{(i, k-1)}\}$
and
$u_{(i, 1)} \prec \cdots \prec u_{(i, k-1)}$
, and
$u_{(i, j)}$
is the conflict-free walk
$(v, e_i, U_{(i, j)}).$
By Corollary 3.8 and Proposition 4.1, we have
where
$U^{\prime }_{(i, j)}$
is the conflict-free walk
$(U_{(i, j)})$
in the k-walk-tree
$T(H-\{v, u_{(i, 1)}, \dots , u_{(i, j-1)}\}, u_{(i, j)}).$
From the definition of the conflict-free walk and k-walk-tree, we observe that for each
$i\in [m]$
and
$j\in [k-1]$
, the two hypertrees
$T(U_{(i, j)})$
and
$T(H-\{v, u_{(i, 1)}, \dots , u_{(i, j-1)}\}, u_{(i, j)})$
are isomorphic, where
$U_i^{j}$
is mapped to
$U^{\prime }_{(i, j)}.$
This completes the proof.
We remark that by Observation 3.4 (ii), the k-walk-tree of a hypertree is isomorphic to the original hypertree, thus we can recursively apply Lemma 4.2 by starting from the leaves of the k-walk-tree to estimate
$\mathcal {P}_H(\overline {v}).$
Proof of Theorem 1.5
Let d be a sufficiently large non-negative integer. We apply Lemma 4.2 to H, v, and
$T.$
Since H is a d-regular linear k-graph, by expanding the formula in the statement of Lemma 4.2 up to the second level of the hypertree T, we obtain
where for each
$i\in [d], i'\in [d-1]$
and
$j, j'\in [k-1]$
, the walk
$U_{i, i'}^{j, j'}$
is a conflict-free walk of length two starting from v.
We observe that the right-hand side of (11) is less than or equal to the value obtained by replacing all the numbers
$\mathcal {P}_{T(U_{i, i'}^{j, j'})}\left ( \overline {U_{i, i'}^{j, j'}}\right )$
by
$1.$
Thus we obtain
Similarly, the right-hand side of (11) is greater than or equal to the value obtained by replacing all the numbers
$\mathcal {P}_{T(U_{i, i'}^{j, j'})}\left ( \overline {U_{i, i'}^{j, j'}}\right )$
by
$0.$
Thus we have
This completes the proof.
5 Concluding remarks
We note that in the proof of Theorem 1.5, the inequality
$\mathcal {P}_{H}(\overline {v}) \geq \frac {1}{d+1}$
does not need the assumption that d is sufficiently large and
$k> 2.$
Thus the following corollary holds from the proof.
Corollary 5.1. If H is an n-vertex d-regular linear k-graph with
$k \geq 2$
and
$d \geq 1,$
then the average size of matchings in H is at most
$\left (1 - \frac {1}{d+1}\right )\frac {n}{k}.$
Although Theorem 1.4 shows that
$\max \{\mathcal {P}_H(\overline {v}) : v\in V(H)\}$
may be close to
$1,$
it is still possible that
$\sum _{v\in V(H)} \mathcal {P}_H(\overline {v}) = o_d(n).$
We believe this is true.
In this paper, we disprove Conjecture 1.1 for all
$k> 2$
and provide a sharp bound for
$\mathcal {P}_H(\overline {v})$
for d-regular linear k-graph. The construction for the counterexample uses a limit of dynamical systems, thus the number of vertices in our hypergraph is very large compared with
$d.$
The proof highly relies on the fact that d is a fixed constant, so we can iteratively expand our hypergraph until we obtain our desired properties. Then what if d also grows with the order of the hypergraph? In this case, we suspect that Conjecture 1.1 would be true for such values of
$d.$
Conjecture 5.2. Let
$k \geq 3$
be a positive integer and
$0 < \delta , \varepsilon < 1$
be a positive real number. Then there is
$n_0$
such that the following is true for all
$n \geq n_0.$
Let H be an n-vertex k-graph that satisfies the following. For all
$v\in V(H)$
, the degree of v lies between
$(1 - n^{-\delta })d$
and
$(1 + n^{-\delta })d$
for some
$d> n^{\varepsilon }$
, and the maximum codegree of H is bounded above by
$n^{-\delta } d.$
Then for all
$v\in V(H),$
we have
If Conjecture 5.2 is true, there are several interesting consequences. For instance, this implies that the average size of partial transversals in sufficiently large n-symbol Latin squares is
$(1 - n^{-1/3} + o_n(1))n$
, meaning that the average size of partial transversals hardly depends on the specific structure of the Latin squares. We can also obtain sharp estimates for average sizes of partial combinatorial designs in the hypergraphs if Conjecture 5.2 is true.
Theorem 3.5 generalizes Godsil’s celebrated identity [Reference Godsil6] to hypergraphs. The matching polynomials and Godsil’s path-trees have many applications in various areas, such as statistical physics. We believe Theorem 3.5 has the potential to generalize several results on matching polynomials of graphs to hypergraphs.
Acknowledgements
This research was performed during the author’s visit to the Universität Hamburg. We thank the Universität Hamburg for its support, hospitality, and for providing a great working environment. The author also thanks his advisor, Jaehoon Kim, for his helpful advice and encouragement. He also thanks the anonymous referee for valuable comments and suggestions that improved this work.
Competing interests
The author has no competing interests to declare.
Funding statement
This research was supported by grants from the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) <10.13039/501100003725> (No. RS-2023-00210430); the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2022R1C1C1010300); Institute for Basic Sciences <10.13039/501100010446> (IBS-R029-C4).
Data availability statement
No data used.
Ethical standards
The research meets all ethical guidelines, including adherence to the legal requirements of the study country.
Open access
