Andrzej Dudek and Laars Helenius
Department of Mathematics, Western Michigan University, Kalamazoo, MI
{andrzej.dudek,
Abstract.
An ℓ-offset Hamilton cycleC in a k-uniform hypergraph H on n vertices is a collection of edges of H such that for some cyclic order of [n] every pair of consecutive edges Ei−1,Ei in C (in the natural ordering of the edges) satisfies |Ei−1∩Ei|=ℓ and every pair of consecutive edges Ei,Ei+1 in C satisfies |Ei∩Ei+1|=k−ℓ. We show that in general √ekℓ!(k−ℓ)!/nk is the sharp threshold for the existence of the ℓ-offset Hamilton cycle in the random k-uniform hypergraph H(k)n,p. We also examine this structure’s natural connection to the 1-2-3 Conjecture.
The first author was supported in part by Simons Foundation Grant #244712 and by the National Security Agency under Grant Number H98230-15-1-0172. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon.
1. Introduction
A k-uniform hypergraph is a hypergraph in which each edge contains exactly k vertices. The random k-uniform hypergraph, denoted H(k)n,p, has each possible edge appearing independently with probability p. Observe that H(2)n,p is equivalent to the binomial random graph Gn,p.
The threshold for the existence of Hamilton cycles in the random graph Gn,p has been known for many years, see, e.g., [3], [5] and [17]. There have been many generalizations of these results over the years and the problem is well understood. Quite recently some of these results were extended to hypergraphs.
Suppose that 1≤ℓ<k. An ℓ-overlapping Hamilton cycleC
in a k-uniform hypergraph H=(V,E) on n vertices is a
collection of mℓ=n/(k−ℓ) edges of H such that for some cyclic order
of [n] every edge consists of k consecutive vertices and for
every pair of consecutive edges Ei−1,Ei in C (in the natural
ordering of the edges) we have |Ei−1∩Ei|=ℓ. Thus, in every
ℓ-overlapping Hamilton cycle the sets Ci=Ei∖Ei−1,i=1,2,…,mℓ, are a partition of V into sets of
size k−ℓ. Hence, mℓ=n/(k−ℓ). Thus, k−ℓ divides n.
In the literature, when ℓ=k−1 we have a tight Hamilton cycle and
when ℓ=1 we have a loose Hamilton cycle.
A k-uniform hypergraph is said to be ℓ-Hamiltonian when it contains an ℓ-overlapping Hamilton cycle.
Recently, results on loose hamiltonicity of H(k)n,p were
obtained by Frieze [10] (for k=3), Dudek and Frieze [6] (for k≥4 and 2(k−1)|n),
and by Dudek, Frieze, Loh and Speiss [8] (for k≥3 and (k−1)|n).
Throughout this paper the following conventions are adhered to: we let ω=ω(n) be any function tending to infinity with n, we let e be the base of natural logarithm logn, and we do not round numbers that are supposed to be integers either up or down. This last convention is justified since the rounding errors introduced are negligible for the asymptomatic calculations we make.
There exists an absolute constant c>0 such that if p≥c(logn)/n2, then a.a.s. H(3)n,p contains a loose Hamilton cycle provided that 2|n. Furthermore, for every k≥4 if p≥ω(logn)/nk−1, then H(k)n,p contains a loose Hamilton cycle provided that (k−1)|n.
These results are basically optimal since if p≤(1−ε)(k−1)!(logn)/nk−1 and ε>0 is constant, then a.a.s. H(k)n,p contains isolated vertices. More recently Ferber [9] simplified some of the proofs of Theorem 1 and Dudek and Frieze [7] were able to extend these to an arbitrary ℓ≥2.
For all integers k>ℓ≥2 and fixed ε>0, if
p≤(1−ε)ek−ℓ/nk−ℓ, then
a.a.s. H(k)n,p is not ℓ-Hamiltonian.
For all integers k>ℓ≥3, there exists a
constant c=c(k) such that if p≥c/nk−ℓ
and n is a multiple of k−ℓ, then a.a.s.
H(k)n,p is ℓ-Hamiltonian.
If k>ℓ=2 and p≥ω/nk−2
and n is a multiple of k−2,
then a.a.s. H(k)n,p is 2-Hamiltonian.
For a fixed ε>0, if k≥4 and p≥(1+ε)e/n, then
a.a.s. H(k)n,p contains a tight Hamilton cycle.
This theorem shows, in particular, that e/n is the sharp threshold for the existence of a tight Hamilton cycle in a k-uniform hypergraph, when
k≥4.
Finally Poole [19] considered weak (Berge) Hamiltonian cyclesC in k-uniform hypergraphs H on n vertices which are collections of edges of H such that for some cyclic order
of [n] every pair of consecutive vertices belong to an edge from C and these edges are not necessarily distinct. Notice that loose Hamilton cycles are weak Hamiltonian cycles, too. In particular,
Let k≥3. Then, p=(k−1)!(logn)/nk−1 is a sharp threshold for the existence of the weak Hamiltonian cycle in H(k)n,p.
In this paper we let 1≤ℓ≤k/2 and define an ℓ-offset Hamilton cycleC in a k-uniform hypergraph H on n vertices as a collection of m edges of H such that for some cyclic order of [n] every pair of consecutive edges Ei−1,Ei in C (in the natural ordering of the edges) satisfies |Ei−1∩Ei|=ℓ and every pair of consecutive edges Ei,Ei+1 in C satisfies |Ei∩Ei+1|=k−ℓ (see Figure 1).
Since every ℓ-offset Hamilton cycle consists of two perfect matching of size n/k, we have m=2n/k and we always assume that k divides n when discussing ℓ-offset Hamilton cycles. A k-uniform hypergraph is said to be ℓ-offset Hamiltonian when it contains an ℓ-offset Hamilton cycle.
It follows from a result of Parczyk and Person (Corollary 3.1 in [18]) that if p=ω/nk/2, then a.a.s. H(k)n,p is ℓ-offset Hamiltonian for any k≥4 and ℓ≥2. In the next theorem we replace this asymptotic threshold by the sharp one for k≥6 and ℓ≥3.
Theorem 4
Let ε>0. Then:
For all integers k≥3 and 1≤ℓ≤k2, if p=(1−ε)√ekℓ!(k−ℓ)!/nk,
then a.a.s. H(k)n,p is not ℓ-offset Hamiltonian.
For all integers k≥6 and 3≤ℓ≤k2, if p=(1+ε)√ekℓ!(k−ℓ)!/nk,
then a.a.s. H(k)n,p is ℓ-offset Hamiltonian.
For all integers k≥4 and ℓ=2 and if p=ωnk/2,
then a.a.s. H(k)n,p is 2-offset Hamiltonian.
The proof for Theorem 4 presented in the next section is based on the second moment method, similar to the proof of Theorem 2. Observe that the only case not covered by Theorem 4 is ℓ=1; we will comment on this in Section 5. Moreover, we will also see in Sections 3 and 4 that the structures captured by offset Hamiltonian cycles arise in a natural way in a problem related to the 1-2-3 Conjecture.
Let X be the random variable that counts the number of ℓ-offset Hamiltonian cycles. Observe that the number of cycles in the complete k-uniform hypergraph is:
γn:=n!2n⋅k−ℓ(ℓ!(k−ℓ)!)n/k.
Indeed, first we order all vertices into a cycle, next we add 2n/k edges, which can be shifted by at most k−ℓ positions, and finally we need to correct this by permuting all vertices in any two consecutive edges.
and let H be a fixed ℓ-offset Hamiltonian cycle. Observe that
E(X)=(1+o(1))(k−ℓ)√π2n(1+ε)2n/k=∞.
Let N(b,a) be the number of H′ℓ-offset Hamiltonian cycles such that |E(H)∩E(H′)|=b and E(H)∩E(H′) consists of a edge disjoint paths. Since trivially N(0,0)≤γn, we obtain
so that we can use Chebyshev’s inequality to imply that
Pr(X=0)≤E(X2)E(X)2−1=o(1),
(1)
as required.
To find an upper bound on N(b,a) we first consider how many ways we can find paths P1,P2,…,Pa with a total of b edges. To begin, for each 1≤i≤a choose vertices vi on V(H). We have at most
na
(2)
choices. Let
b1+b2+⋯+ba=b,
where bi≥1 is an integer for every 1≤i≤a. Note that this equation has exactly
(b−1a−1)
(3)
solutions. So for every i, we choose a path of length bi in H which starts at vi and it moves clockwise. Thus we (2) and (3) tell us we have at most
(b−1a−1)na
(4)
ways to choose our paths.
Now we count the number of H′ containing P1,…,Pa. For each even path (that means with even number of edges)
|V(Pi)|=bik2+ℓ or |V(Pi)|=bik2+(k−ℓ)
and for each odd path
|V(Pi)|=bik2+k2.
Since ℓ≤k/2 then for all paths we have
|V(Pi)|≥bik2+ℓ.
Then
∑i|V(Pi)|
≥∑i(bik2+ℓ)=bk/2+aℓ.
Thus, we have at most n−bk/2−aℓ vertices not in ⋃ai=1V(Pi). Observe that H′ is uniquely determined by the sequence of 2n/k subsets each of sizes alternating from k−ℓ to ℓ. For each V(Pi), if bi=1 then we need to divide |V(Pi)|=k vertices into 2 subsets of size k−ℓ and ℓ. The number of ways these paths can be split into alternating subsets is at most
(kℓ)a≤(kk/2)a<2ka.
(5)
(If bi>1, then there is nothing to do.)
Next we divide the vertices in V(H)∖(V(P1)∪⋯∪V(Pa)) into subsets of size ℓ and k−ℓ to obtaining a cycle of alternating subsets. Let b′i be the number of edges in H′ that lie between Pi and Pi+1 and connect Pi with Pi+1.
Then there are exactly b′i−1 alternating subsets between Pi and Pi+1 in H′. Thus, we have at least (b′i−2)/2 groups of size ℓ and of size k−ℓ between Pi and Pi+1. Since
a∑i=1(b′i−2)/2=(2nk−b)/2−a=n/k−b/2−a,
we conclude that we have at least (n/k−b/2−a) groups of size ℓ and at least (n/k−b/2−a) groups of size k−ℓ on V(H)∖(V(P1)∪⋯∪V(Pa)). Consequently, we can divide V(H)∖(V(P1)∪⋯∪V(Pa)) into alternating groups in at most
This proves part (iii) and completes the proof of Theorem 4.
3. Group colorings
The well-known 1-2-3 Conjecture of Karoński, Łuczak and Thomason [15] asserts that in every graph (without isolated edges)
the edges can have assigned weights from {1,2,3} so that adjacent vertices have different sums of incident edge weights.
This conjecture attracted a lot of attention and has been studied by several researchers (see, e.g., a survey paper of Seamone [20]).
The 1-2-3 conjecture is still open but Kalkowski, Karoński, and Pfender [13] have shown that the conjecture holds if {1,2,3} is replaced by {1,…,5}. (For previous results see [1, 2, 21]).
One can extend these ideas by considering k-uniform hypergraphs H. A vertex coloring of H is weak if H has no monochromatic edge and strong if for each edge all vertices within that edge have distinct colors. Then we say that H is weaklyw-weighted if there exists an edge coloring from [w] induces a weak vertex-coloring. Similarly, we say that H is stronglyw-weighted if the corresponding coloring is strong.
Clearly each strongly w-weighted hypergraph is also weakly w-weighted. Note that for graphs (k=2) weak and strong colorings (and therefore weightings) are the same.
In [14] Kalkowski, Karoński, and Pfender studied weakly weighted hypergraphs. In particular, they proved that any k-uniform hypergraph without isolated edges is weakly (5k−5)-weighted and that 3-uniform hypergraphs are even weakly 5-weighted. They also asked whether there is an absolute constant w0 such that every k-uniform hypergraph is weakly w0-weighted. Furthermore, they conjectured that each 3-uniform hypergraph without isolated edges is weakly 3-weighted. It was shown by Bennett, Dudek, Frieze and Helenius [4] that for almost all uniform hypergraphs these conjectures hold.
In this paper we explore another direction, where edge-weights are elements of an abelian group. This was introduced by Karoński, Łuczak and Thomason [15].
Let Γ be a finite abelian group of odd order and let G be a non-trivial |Γ|-colorable graph. Then there is a weighting of the edges of G with the elements of Γ such that the resultant vertex weighting is a proper coloring.
It was our attempts to extend this idea to k-uniform hypergraphs that led us to consider the concept of offset Hamilton cycles. So for u,v∈V(H) let T be a uv-trail (that means a sequence of vertices with repeated vertices allowed) in H such that
the first two edges have k−1 vertices in common not including u, and
the last two edges have k−1 vertices in common not including v, and
any two successive edges in the trail have either 1 or k−1 vertices in common in an alternating fashion.
Any trail that fits this pattern will be called 1-offset. Thus the vertices along T are subdivided into alternating groups of size 1 and k−1, starting and ending with subdivisions of 1. Observe that this condition implies the number of edges in T must be even. Also, since T is a trail, vertices can get used in multiple edges, including u and v, but the first two edges must start with u as a singleton and the last two edges must finish with v as a singleton (see Figure 2). Let T be the hypergraph property that for all pairs of vertices u,v∈V(H) there exists a 1-offset uv-trail. If hypergraph H∈T, then we say that H is T-connected.