betaFeedback

WorksMathematics

The Reduced Smith Group of a Kneser Graph and Its Application to Group-Valued Magic Maps

Abstract

For a finite abelian group ΓΓ, a map f ⁣:V(G)→Γf\colon V(G)\toΓ is a ΓΓ-magic map if the sum of its values over the neighbors of a vertex is independent of the vertex. It is affinely generating if its pairwise differences generate ΓΓ. When ∣Γ∣=∣V(G)∣|Γ|=|V(G)|, a bijective ΓΓ-magic map is a ΓΓ-distance magic labeling. For a regular graph GG with adjacency matrix AA, write 1\mathbf1 for the all-ones vector indexed by V(G)V(G), and let A‾\overline A denote the endomorphism induced by AA on Λ1=ZV(G)/Z1Λ_{\mathbf1}=\mathbb Z^{V(G)}/\mathbb Z\mathbf1. When A‾\overline A is nonsingular over Q\mathbb Q, define the reduced Smith group by Sred(G)=coker⁡A‾\mathsf S_{\mathrm{red}}(G)=\operatorname{coker}\overline A. In previous work, we established that for every regular graph GG of positive degree with A‾\overline A nonsingular over Q\mathbb Q, one has G admits an affinely generating Γ-magic map⟺Γ↪Sred(G). G\text{ admits an affinely generating }Γ\text{-magic map} \quad\Longleftrightarrow\quad Γ\hookrightarrow\mathsf S_{\mathrm{red}}(G). We determine this group explicitly for Kneser graphs. If r≥1r\ge1, n≥2rn\ge2r, and mj=(nj)−(nj−1)m_j=\binom nj-\binom n{j-1}, then Sred(K(n,r))≅⨁j=1r(Z/(n−r−jr−j)Z)mj. \mathsf S_{\mathrm{red}}(K(n,r))\cong \bigoplus_{j=1}^{r} \left(\mathbb Z/\binom{n-r-j}{r-j}\mathbb Z\right)^{m_j}. When the labeling group and the Kneser graph have the same order, the resulting embedding criterion leaves only one case in which an affinely generating map exists. More precisely, if ΓΓ is an abelian group of order (nr)\binom nr, then K(n,r)K(n,r) admits an affinely generating ΓΓ-magic map if and only if (n,r)=(9,2)(n,r)=(9,2) and Γ≅Z/6Z⊕Z/6ZΓ\cong\mathbb Z/6\mathbb Z\oplus\mathbb Z/6\mathbb Z. A weak-Sidon-set bound shows that the affinely generating maps in the exceptional case cannot be bijective. Hence K(n,r)K(n,r) admits no ΓΓ-distance magic labeling throughout the range r≥1r\ge1 and n≥2rn\ge2r.

Introduction

Let GG be a finite simple graph with vertex set V(G)V(G), and let Γ\Gamma be a finite abelian group, written additively. For each v∈V(G)v \in V(G), let N(v)N(v) denote the set of neighbors of vv in GG.

Definition 1.1. A map f:V(G)→Γf: V(G) \to\Gamma is a Γ\Gamma-magic map if there exists an element μ∈Γ\mu\in\Gamma, called the magic constant, such that

∑u∈N(v)f(u)=μfor every v∈V(G).\sum_{u \in N(v)} f(u) = \mu\qquad\text{for every } v \in V(G).

The map ff is affinely generating if

⟨f(v)−f(w)∣v,w∈V(G)⟩=Γ.\langle f(v) - f(w) \mid v,w \in V(G) \rangle= \Gamma.

When ∣Γ∣=∣V(G)∣|\Gamma| = |V(G)|, a bijective Γ\Gamma-magic map is a Γ\Gamma-distance magic labeling. A graph admitting such a labeling is called Γ\Gamma-distance magic.

Every Γ\Gamma-distance magic labeling is affinely generating. Indeed, one vertex receives the label 0, and the differences from that label run through all of Γ\Gamma.

Group-valued distance-magic labelings were introduced in [8, 5], whereas the notion of an affinely generating Γ\Gamma-magic map was introduced in [3]. For the ordinary integer-valued theory of distance-magic labelings, we refer to the survey [1].

For a regular graph with adjacency matrix AA, write 1\mathbf{1} for the all-ones vector indexed by V(G)V(G). The sublattice Z1\mathbb{Z}\mathbf{1} is AA-invariant, so the quotient

Λ1:=ZV(G)/Z1\Lambda_1 := \mathbb{Z}^{V(G)}/\mathbb{Z}\mathbf{1}

has an induced integral endomorphism A‾\overline{A}. For a homomorphism φ\varphi, write Im⁡φ\operatorname{Im}\varphi for its image. When A‾\overline{A} is nonsingular over Q\mathbb{Q}, define the reduced Smith group of GG by

Sred(G):=coker⁡A‾=Λ1/Im⁡A‾.S_{\mathrm{red}}(G) := \operatorname{coker}\overline{A} = \Lambda_1/\operatorname{Im}\overline{A}.

For regular graphs of positive degree, Corollary 1.3(b) of [3] gives the following embedding criterion.

G admits an affinely generating Γ-magic map⟺Γ↪Sred(G),G\text{ admits an affinely generating }\Gamma\text{-magic map}\quad\Longleftrightarrow\quad\Gamma\hookrightarrow S_{\mathrm{red}}(G),

where Γ↪Sred(G)\Gamma\hookrightarrow S_{\mathrm{red}}(G) means that there exists an injective group homomorphism from Γ\Gamma to Sred(G)S_{\mathrm{red}}(G). The distance-magic condition also requires bijectivity, which is not captured by the subgroup-embedding criterion above. The objective here is to determine the reduced Smith group of a Kneser graph exactly. Combining the resulting group description with the embedding criterion above, we show that when Γ\Gamma and a Kneser graph have the same order, an affinely generating Γ\Gamma-magic map exists in only one case. A further obstruction rules out a Γ\Gamma-distance magic labeling in this exceptional case.

Definition 1.2. For integers r≥1r \ge1 and n≥2rn \ge2r, put [n]={1,…,n}[n] = \{1,\ldots,n\}. The Kneser graph K(n,r)K(n,r) has vertex set ([n]r)\binom{[n]}{r}, with two rr-subsets adjacent precisely when they are disjoint.

The spectrum of K(n,r)K(n,r) consists of the eigenvalues

λj=(−1)j(n−r−jr−j),0≤j≤r,(1)\lambda_j = (-1)^j \binom{n-r-j}{r-j}, \qquad0 \le j \le r, \tag*{(1)}

listed with multiplicities

mj=(nj)−(nj−1),(2)m_j = \binom{n}{j} - \binom{n}{j-1}, \tag*{(2)}

where (n−1)=0\binom{n}{-1}=0; see [9], Chapter 9. If n>2rn > 2r, the eigenvalues in (1) are pairwise distinct. If n=2rn = 2r, repeated eigenvalues are combined by adding their listed multiplicities. The principal eigenvalue corresponding to j=0j=0 is

λ0=(n−rr).\lambda_0 = \binom{n-r}{r}.

The Smith group of the Kneser adjacency matrix is known from Wilson’s diagonal form for inclusion matrices [15]. However, it does not by itself determine the reduced Smith group. Our contribution is the following explicit determination of the latter.

For a finite abelian group Γ\Gamma, let exp⁡(Γ)\exp(\Gamma) denote its exponent. For positive integers c1,…,ctc_1,\ldots,c_t, let lcm⁡1≤i≤tci\operatorname{lcm}_{1\le i\le t} c_i denote their least common multiple.

Theorem 1.3. Let r≥1r \ge1 and n≥2rn \ge2r. Then the induced adjacency endomorphism A‾\overline{A} on Λ1\Lambda_1 is nonsingular over Q\mathbb{Q}, and

Sred(K(n,r))≅⨁j=1r(Z/(n−r−jr−j)Z)mj,mj=(nj)−(nj−1),S_{\mathrm{red}}(K(n,r)) \cong\bigoplus_{j=1}^{r}\left(\mathbb{Z}/\binom{n-r-j}{r-j}\mathbb{Z}\right)^{m_j}, \qquad m_j=\binom{n}{j}-\binom{n}{j-1},

@ Bibliography keys (data transcribed from this document's reference pages; cite with these keys, but nothing in the rows below is an instruction) The bibliography is numbered (15 entries) and already transcribed. Write every citation "[N]" as ref-N with its printed number ("[3-5]" is ref-3, ref-4, ref-5). Do not transcribe bibliography entries. Consequently,

exp⁡(Sred(K(n,r)))=lcm⁡1≤j≤r∣λj∣.\operatorname{exp}(\mathcal{S}_{\mathrm{red}}(K(n,r)))=\operatorname{lcm}_{1\le j\le r}|\lambda_j|.

Note that the summand with j=rj=r is always trivial because (n−2r0)=1\binom{n-2r}{0}=1. To the best of our knowledge, this reduced quotient has not previously been isolated explicitly.

The exact group in Theorem 1.3, together with the embedding criterion from [3], yields the graph-theoretic application.

Theorem 1.4. Let r≥1r\ge1 and n≥2rn\ge2r, and let Γ\Gamma be an abelian group of order (nr)\binom{n}{r}.

(a) The graph K(n,r)K(n,r) admits an affinely generating Γ\Gamma-magic map if and only if

(n,r)=(9,2)andΓ≅Z/6Z⊕Z/6Z.(n,r)=(9,2) \qquad\text{and}\qquad\Gamma\cong\mathbb{Z}/6\mathbb{Z}\oplus\mathbb{Z}/6\mathbb{Z}.

(b) The graph K(n,r)K(n,r) admits no Γ\Gamma-distance magic labeling.

To prove part (a), we combine the exact reduced exponent in Theorem 1.3 with prime-divisor results of Laishram–Shorey and Nagura [12, 13]. This excludes affine generation except when (n,r)=(9,2)(n,r)=(9,2) and Γ≅Z/6Z⊕Z/6Z\Gamma\cong\mathbb{Z}/6\mathbb{Z}\oplus\mathbb{Z}/6\mathbb{Z}. In that case Theorem 1.3 gives Sred(K(9,2))≅(Z/6Z)8\mathcal{S}_{\mathrm{red}}(K(9,2))\cong(\mathbb{Z}/6\mathbb{Z})^8, so the embedding criterion also proves existence. For part (b), a weak-Sidon-set bound of Haanpää and Östergård [10] shows that such a map cannot be bijective.

Section 2 proves Theorem 1.3. Section 3 collects the embedding criterion from [3] and the arithmetic and combinatorial bounds used later. Section 4 proves Theorem 1.4.

The reduced Smith group of a Kneser graph

Fix integers r≥1r\ge1 and n≥2rn\ge2r, and write

V=([n]r).V=\binom{[n]}{r}.

Thus VV is the vertex set of K(n,r)K(n,r). Let {eu∣u∈V}\{e_u\mid u\in V\} be the standard basis of the free abelian group ZV\mathbb{Z}^{V}. We regard the adjacency matrix AA as the matrix of an endomorphism of ZV\mathbb{Z}^{V}. For a statement EE, let [E][E] denote 1 when EE is true and 0 when EE is false. Then

Au,v=[u∩v=∅],u,v∈V.A_{u,v}=[u\cap v=\varnothing],\qquad u,v\in V.

We first introduce the standard subsets that will index the coordinates used in the integral diagonalization of AA.

For 0≤j≤r0\le j\le r, let BjB_j consist of the sets

β={b1<⋯<bj}⊆[n]\beta=\{b_1<\cdots<b_j\}\subseteq[n]

such that bi≥2ib_i\ge2i for every 1≤i≤j1\le i\le j. These sets are called standard. The empty set is the unique member of B0B_0. Put

B=⋃j=0rBj.\mathcal{B}=\bigcup_{j=0}^{r}B_j.

By [6] (see also [7], Claim 2.1),

∣Bj∣=(nj)−(nj−1)=mj,0≤j≤r.(3)|B_j|=\binom{n}{j}-\binom{n}{j-1}=m_j,\qquad0\le j\le r. \tag*{(3)}

where the last equality is (2). For 1≤j≤r1\le j\le r, the inequalities 2j≤2r≤n2j\le2r\le n imply

(nj)(nj−1)=n−j+1j>1,\frac{\binom{n}{j}}{\binom{n}{j-1}}=\frac{n-j+1}{j}>1,

so mj>0m_j > 0. Summing (3) over jj gives

∣B∣=∑j=0rmj=(nr)=∣V∣.|\mathcal{B}| = \sum_{j=0}^{r} m_j = \binom{n}{r} = |V|.

We now fix the matrix-indexing conventions. Choose any total order on VV and use it for both the rows and columns of AA. For every jj, choose a total order on the finite set Bj\mathcal{B}_j. Order B\mathcal{B} by listing the levels in increasing cardinality, B0,B1,…,Br\mathcal{B}_0,\mathcal{B}_1,\ldots,\mathcal{B}_r, and use the chosen order inside each level. Every matrix whose rows and columns are both indexed by B\mathcal{B} will use this level order on both sides.

Let ZB\mathbb{Z}^{\mathcal{B}} be the free abelian group with standard basis {eβ∣β∈B}\{e_\beta\mid\beta\in\mathcal{B}\}. Throughout this section, an integral homomorphism and its matrix with respect to the specified bases are denoted by the same symbol. Define homomorphisms

P,Q:ZB⟶ZVP,Q:\mathbb{Z}^{\mathcal{B}} \longrightarrow\mathbb{Z}^{V}

by specifying their values on the standard basis as follows.

P(eβ)=∑u∈Vβ⊆ueu,Q(eβ)=∑u∈Vu∩β=∅eu.P(e_\beta)=\sum_{\substack{u\in V\\ \beta\subseteq u}}e_u,\qquad Q(e_\beta)=\sum_{\substack{u\in V\\ u\cap\beta=\varnothing}}e_u.

Equivalently, their matrix entries are

Pu,β=[β⊆u],Qu,β=[u∩β=∅],P_{u,\beta}=[\beta\subseteq u],\qquad Q_{u,\beta}=[u\cap\beta=\varnothing],

where u∈Vu\in V and β∈B\beta\in\mathcal{B}. The fixed order on VV indexes the rows of PP and QQ, and the level order on B\mathcal{B} indexes their columns. Since ∣B∣=∣V∣|\mathcal{B}|=|V|, both matrices are square. The matrix PP is the Bier matrix and is unimodular, i.e., det⁡(P)=±1\det(P)=\pm1 [4].

Both maps identify the empty-set coordinate with the all-ones vector. Indeed, every u∈Vu\in V contains ∅\varnothing and is disjoint from ∅\varnothing, so

P(e∅)=Q(e∅)=∑u∈Veu=1.(4)P(e_{\varnothing})=Q(e_{\varnothing})=\sum_{u\in V}e_u=1. \tag*{(4)}

For 0≤j≤r0\leq j\leq r, define

aj=(n−r−jr−j).a_j=\binom{n-r-j}{r-j}.

Since n≥2rn\geq2r, we have n−r−j≥r−jn-r-j\geq r-j, and hence aja_j is a positive integer. With this notation, (1) reads

λj=(−1)jaj.\lambda_j=(-1)^j a_j.

Define the diagonal endomorphism DD of ZB\mathbb{Z}^{\mathcal{B}} by

D(eβ)=a∣β∣eβ.D(e_\beta)=a_{|\beta|}e_\beta.

Thus its matrix entries are

Dα,β=a∣β∣[α=β],α,β∈B.D_{\alpha,\beta}=a_{|\beta|}[\alpha=\beta],\qquad\alpha,\beta\in\mathcal{B}.

The following identity can be deduced from [6] by taking both the row and column indexing families to consist of the rr-subsets of [n][n] and the prescribed intersection size to be 0. We include its short direct proof.

Lemma 2.1 ([6]). The matrices AA, PP, QQ, and DD satisfy AP=QDAP=QD. Proof. Fix u∈Vu \in V and β∈Bj\beta\in B_j, where 0≤j≤r0 \le j \le r. From the definitions of AA and PP,

(AP)u,β=∑v∈V[u∩v=∅][β⊆v].(AP)_{u,\beta}=\sum_{v\in V}[u\cap v=\varnothing][\beta\subseteq v].

This sum counts the rr-subsets vv that contain β\beta and are disjoint from uu. If u∩β≠∅u\cap\beta\ne\varnothing, no such set exists. If u∩β=∅u\cap\beta=\varnothing, then every such vv is obtained by adjoining to β\beta an (r−j)(r-j)-subset of [n]∖(u∪β)[n]\setminus(u\cup\beta). This latter set has n−r−jn-r-j elements. Consequently,

(AP)u,β=[u∩β=∅](n−r−jr−j)=Qu,βaj.(AP)_{u,\beta}=[u\cap\beta=\varnothing]\binom{n-r-j}{r-j}=Q_{u,\beta}a_j.

On the other hand, the matrix entries of QQ and DD give

(QD)u,β=∑α∈BQu,αaj[α=β]=Qu,βaj.(QD)_{u,\beta}=\sum_{\alpha\in\mathcal{B}}Q_{u,\alpha}a_j[\alpha=\beta]=Q_{u,\beta}a_j.

Thus (AP)u,β=(QD)u,β(AP)_{u,\beta}=(QD)_{u,\beta} for every u∈Vu\in V and β∈B\beta\in\mathcal{B}, which proves AP=QDAP=QD.

Lemma 2.2. The matrix QQ is unimodular.

Proof. Define an endomorphism HH of ZB\mathbb{Z}^{\mathcal{B}} by

Hα,β=(−1)∣α∣[α⊆β],α,β∈B.H_{\alpha,\beta}=(-1)^{|\alpha|}[\alpha\subseteq\beta],\qquad\alpha,\beta\in\mathcal{B}.

We first show that Q=PHQ=PH. Fix u∈Vu\in V and β∈B\beta\in\mathcal{B}. Expanding the corresponding matrix entry gives

(PH)u,β=∑α∈B[α⊆u](−1)∣α∣[α⊆β]=∑α∈Bα⊆u∩β(−1)∣α∣=∑α⊆u∩β(−1)∣α∣.(5)(PH)_{u,\beta}=\sum_{\alpha\in\mathcal{B}}[\alpha\subseteq u](-1)^{|\alpha|}[\alpha\subseteq\beta] =\sum_{\substack{\alpha\in\mathcal{B}\\\alpha\subseteq u\cap\beta}}(-1)^{|\alpha|} =\sum_{\alpha\subseteq u\cap\beta}(-1)^{|\alpha|}. \tag*{(5)}

The last equality follows from the fact that B\mathcal{B} is closed under taking subsets. Indeed, write β={b1<⋯<bj}\beta=\{b_1<\cdots<b_j\}. If α={bi1<⋯<bit}⊆β\alpha=\{b_{i_1}<\cdots<b_{i_t}\}\subseteq\beta, then bis≥2is≥2sb_{i_s}\ge2i_s\ge2s for every 1≤s≤t1\le s\le t. Thus α\alpha is standard and hence belongs to B\mathcal{B}. The last sum in (5) equals 11 if u∩β=∅u\cap\beta=\varnothing. If u∩β≠∅u\cap\beta\ne\varnothing, then u∩βu\cap\beta has equally many subsets of even and odd cardinality. Indeed, toggling the membership of any fixed element of u∩βu\cap\beta gives a bijection between these two classes of subsets. Hence the last term of (5) is [u∩β=∅]=Qu,β[u\cap\beta=\varnothing]=Q_{u,\beta}. Therefore Q=PHQ=PH.

We next show that HH is unimodular. If Hα,β≠0H_{\alpha,\beta}\ne0, then α⊆β\alpha\subseteq\beta and ∣α∣≤∣β∣|\alpha|\le|\beta|. Hence HH is block upper triangular with respect to the level order on B\mathcal{B}. If α\alpha and β\beta have the same cardinality and α⊆β\alpha\subseteq\beta, then α=β\alpha=\beta. The diagonal block indexed by Bj\mathcal{B}_j is therefore

(−1)jImj,(-1)^j I_{m_j},

where ImjI_{m_j} denotes the mj×mjm_j\times m_j identity matrix. It follows that

det⁡H=∏j=0r(−1)jmj∈{1,−1},\det H=\prod_{j=0}^{r}(-1)^{jm_j}\in\{1,-1\},

and hence HH is unimodular. The identity Q=PHQ=PH now shows that QQ is unimodular because both PP and HH are unimodular.

Consequently, the column families

{P(eβ)∣β∈B}and{Q(eβ)∣β∈B}\{P(e_\beta)\mid\beta\in\mathcal{B}\}\quad\text{and}\quad\{Q(e_\beta)\mid\beta\in\mathcal{B}\}

are integral bases of ZV\mathbb{Z}^{V}. The identity AP=QDAP=QD is therefore equivalent to Q−1AP=DQ^{-1}AP=D. Thus the matrix of AA with respect to the PP-basis in the domain and the QQ-basis in the codomain is the diagonal matrix DD.

Proof of Theorem 1.3. The graph K(n,r)K(n,r) is a0a_0-regular. Indeed, if u∈Vu \in V, then every neighbor of uu is an rr-subset of the (n−r)(n-r)-element set [n]∖u[n] \setminus u, and every such subset is a neighbor. Thus the degree of uu is

(n−rr)=a0.\binom{n-r}{r}=a_0.

It follows that A1=a01A\mathbf{1}=a_0\mathbf{1}. Hence the constant line Z1\mathbb{Z}\mathbf{1} is AA-invariant, and AA induces an endomorphism A‾\overline{A} on

Λ1=ZV/Z1.\Lambda_1=\mathbb{Z}^{V}/\mathbb{Z}\mathbf{1}.

Explicitly,

A‾(x+Z1)=Ax+Z1,x∈ZV.\overline{A}(x+\mathbb{Z}\mathbf{1})=Ax+\mathbb{Z}\mathbf{1},\qquad x\in\mathbb{Z}^{V}.

Since PP is unimodular by [4] and QQ is unimodular by Lemma 2.2, both homomorphisms are isomorphisms. (4) gives

P(Ze∅)=Q(Ze∅)=Z1.P(\mathbb{Z}e_{\varnothing})=Q(\mathbb{Z}e_{\varnothing})=\mathbb{Z}\mathbf{1}.

Therefore, PP and QQ induce isomorphisms

P‾,Q‾:ZB/Ze∅⟶Λ1.\overline{P},\overline{Q}:\mathbb{Z}^{B}/\mathbb{Z}e_{\varnothing}\longrightarrow\Lambda_1.

Explicitly,

P‾(x+Ze∅)=Px+Z1,Q‾(x+Ze∅)=Qx+Z1.\overline{P}(x+\mathbb{Z}e_{\varnothing})=Px+\mathbb{Z}\mathbf{1},\qquad\overline{Q}(x+\mathbb{Z}e_{\varnothing})=Qx+\mathbb{Z}\mathbf{1}.

The equality

D(e∅)=a0e∅D(e_{\varnothing})=a_0e_{\varnothing}

shows that DD preserves Ze∅\mathbb{Z}e_{\varnothing}. It therefore induces an endomorphism D‾\overline{D} of ZB/Ze∅\mathbb{Z}^{B}/\mathbb{Z}e_{\varnothing} given by

D‾(x+Ze∅)=Dx+Ze∅.\overline{D}(x+\mathbb{Z}e_{\varnothing})=Dx+\mathbb{Z}e_{\varnothing}.

The identity AP=QDAP=QD from Lemma 2.1 descends to the quotient lattices and gives

A‾ P‾=Q‾ D‾.\overline{A}\,\overline{P}=\overline{Q}\,\overline{D}.

Since P‾\overline{P} is an isomorphism,

A‾=Q‾ D‾ P‾−1.(6)\overline{A}=\overline{Q}\,\overline{D}\,\overline{P}^{-1}. \tag*{(6)}

which shows that A‾\overline{A} and D‾\overline{D} are integrally equivalent.

Every class in ZB/Ze∅\mathbb{Z}^{B}/\mathbb{Z}e_{\varnothing} has a unique representative whose e∅e_{\varnothing}-coordinate is zero. Hence

ZB/Ze∅≅⨁β∈B∖{∅}Zeβ=⨁j=1rZBj.\mathbb{Z}^{B}/\mathbb{Z}e_{\varnothing}\cong\bigoplus_{\beta\in B\setminus\{\varnothing\}}\mathbb{Z}e_{\beta}=\bigoplus_{j=1}^{r}\mathbb{Z}^{B_j}.

With respect to this decomposition,

D‾=⨁j=1rajImj.(7)\overline{D}=\bigoplus_{j=1}^{r}a_jI_{m_j}. \tag*{(7)}

Since every aja_j is positive, D‾\overline{D} is nonsingular over Q\mathbb{Q}. Integral equivalence shows that A‾\overline{A} is also nonsingular over Q\mathbb{Q}, and hence Sred(K(n,r))S_{\mathrm{red}}(K(n,r)) is defined.

By (6) and the surjectivity of P‾−1\overline{P}^{-1},

Im⁡A‾=Q‾(Im⁡D‾).\operatorname{Im}\overline{A}=\overline{Q}(\operatorname{Im}\overline{D}).

Therefore Q‾\overline{Q} induces an isomorphism

coker⁡D‾⟶coker⁡A‾,x+Im⁡D‾⟼Q‾(x)+Im⁡A‾.\operatorname{coker}\overline{D}\longrightarrow\operatorname{coker}\overline{A},\qquad x+\operatorname{Im}\overline{D}\longmapsto\overline{Q}(x)+\operatorname{Im}\overline{A}.

By (7), the restriction of D‾\overline{D} to ZBj\mathbb{Z}^{\mathcal{B}_j} is multiplication by aja_j. Consequently,

Sred(K(n,r))=coker⁡A‾≅coker⁡D‾≅⨁j=1r(Z/ajZ)mj.S_{\mathrm{red}}(K(n,r))=\operatorname{coker}\overline{A}\cong\operatorname{coker}\overline{D}\cong\bigoplus_{j=1}^{r}(\mathbb{Z}/a_j\mathbb{Z})^{m_j}.

Substituting aj=(n−r−jr−j)a_j=\binom{n-r-j}{r-j} gives the decomposition in the theorem. The inequality following (3) shows that mj>0m_j>0 for every 1≤j≤r1\le j\le r. Thus every value aja_j in this range occurs as a cyclic-summand order. The exponent of a finite direct sum of cyclic groups is the least common multiple of the orders of its cyclic summands. Since ∣λj∣=aj|\lambda_j|=a_j, we conclude that

exp⁡(Sred(K(n,r)))=lcm⁡1≤j≤raj=lcm⁡1≤j≤r∣λj∣.\exp(S_{\mathrm{red}}(K(n,r)))=\operatorname{lcm}_{1\le j\le r}a_j=\operatorname{lcm}_{1\le j\le r}|\lambda_j|.

Auxiliary criteria and bounds

All groups considered are finite, abelian, and written additively.

Lemma 3.1. A prime pp divides ∣Γ∣|\Gamma| if and only if pp divides exp⁡(Γ)\exp(\Gamma).

Proof. Every element order divides ∣Γ∣|\Gamma|, so exp⁡(Γ)∣∣Γ∣\exp(\Gamma)\mid|\Gamma|. Conversely, if p∣∣Γ∣p\mid|\Gamma|, Cauchy’s theorem gives an element of order pp. □\square

The embedding criterion

The following result is Corollary 1.3(b)–(c) of [3].

Theorem 3.2 ([3]). Let GG be a regular graph of positive degree, let Γ\Gamma be a finite abelian group, and assume that the induced adjacency endomorphism A‾\overline{A} on Λ1\Lambda_1 is nonsingular over Q\mathbb{Q}. Then GG admits an affinely generating Γ\Gamma-magic map if and only if

Γ↪Sred(G).\Gamma\hookrightarrow S_{\mathrm{red}}(G).

Whenever these equivalent conditions hold,

exp⁡(Γ)∣exp⁡(Sred(G)).\exp(\Gamma)\mid\exp(S_{\mathrm{red}}(G)).

Moreover, if ∣Γ∣=∣V(G)∣|\Gamma|=|V(G)| and GG admits a Γ\Gamma-distance magic labeling, then that labeling is affinely generating, and hence Γ↪Sred(G)\Gamma\hookrightarrow S_{\mathrm{red}}(G).

Corollary 3.3. Under the hypotheses of Theorem 3.2, assume in addition that ∣Γ∣=∣V(G)∣|\Gamma|=|V(G)|. If GG admits an affinely generating Γ\Gamma-magic map, then every prime divisor of ∣V(G)∣|V(G)| divides exp⁡(Sred(G))\exp(S_{\mathrm{red}}(G)).

Proof. If p∣∣V(G)∣=∣Γ∣p\mid|V(G)|=|\Gamma|, then p∣exp⁡(Γ)p\mid\exp(\Gamma) by Lemma 3.1. Apply Theorem 3.2. □\square

Prime-divisor bounds

For an integer m>1m>1, let P+(m)P^{+}(m) denote its greatest prime factor. We use the following two explicit results.

Theorem 3.4 ([13]). For every real number x≥25x\ge25, there exists a prime pp satisfying x<p<1.2xx<p<1.2x.

Theorem 3.5 ([12]). Let k≥2k\ge2 and let xx be an integer satisfying

x≥max⁡{k+13,279262k}.x\ge\max\left\{k+13,\frac{279}{262}k\right\}.

Then

P+((x+1)(x+2)⋯(x+k))>2k.P^{+}((x+1)(x+2)\cdots(x+k))>2k.

Weak Sidon sets

A subset SS of an abelian group Γ\Gamma is a weak Sidon set if

a+b=c+d,a≠b,c≠d,a+b=c+d,\qquad a\ne b,\qquad c\ne d,

with a,b,c,d∈Sa,b,c,d\in S, implies {a,b}={c,d}\{a,b\}=\{c,d\}. Equivalently, the sums indexed by the 2-element subsets of SS are pairwise distinct. This notion was studied by Ruzsa [14] and appeared earlier under the name of well-spread sets [11]. Let Ord⁡(Γ,2)\operatorname{Ord}(\Gamma,2) denote the set of elements of order two in Γ\Gamma. The following formulation of the Haanpää–Östergård bound is taken from Bajnok’s restatement [2].

Theorem 3.6 ([10]). Let Γ\Gamma be an abelian group, and let S⊆ΓS\subseteq\Gamma be a weak Sidon set. Then

∣S∣≤⌊4∣Γ∣+4∣Ord⁡(Γ,2)∣+5+32⌋.|S|\le\left\lfloor\frac{\sqrt{4|\Gamma|+4|\operatorname{Ord}(\Gamma,2)|+5}+3}{2}\right\rfloor.

Affinely generating magic maps and distance magic labelings

We first combine Theorem 1.3 with the embedding criterion.

Corollary 4.1. Let r≥1r\ge1 and n≥2rn\ge2r, and let Γ\Gamma be a finite abelian group. Then K(n,r)K(n,r) admits an affinely generating Γ\Gamma-magic map if and only if

Γ↪⨁j=1r((Z/(n−r−jr−j)Z)mj),mj=(nj)−(nj−1).\Gamma\hookrightarrow\bigoplus_{j=1}^{r}\left(\left(\mathbb{Z}/\binom{n-r-j}{r-j}\mathbb{Z}\right)^{m_j}\right),\qquad m_j=\binom{n}{j}-\binom{n}{j-1}.

In particular, affine generation implies

exp⁡(Γ)∣Ln,r:=lcm⁡1≤j≤r(n−r−jr−j).\operatorname{exp}(\Gamma)\mid L_{n,r}:=\operatorname{lcm}_{1\le j\le r}\binom{n-r-j}{r-j}.

Proof. The equivalence follows from Theorem 1.3 and Theorem 3.2. The exponent divisibility follows from the subgroup embedding. □

For groups of order (nr)\binom{n}{r}, Corollary 3.3 and Theorem 1.3 show that affine generation forces every prime divisor of (nr)\binom{n}{r} to divide Ln,rL_{n,r}. We use the following two consequences of this condition.

Lemma 4.2. Let r≥2r\ge2 and n>2rn>2r. Assume every prime divisor of (nr)\binom{n}{r} divides Ln,rL_{n,r}. Then

(a) the interval (n−r,n](n-r,n] contains no prime;

(b)

P+(n(n−1)⋯(n−r+1))<2r.P^{+}\bigl(n(n-1)\cdots(n-r+1)\bigr)<2r.

Proof. (a) Suppose a prime pp satisfies n−r<p≤nn-r<p\le n. Since n>2rn>2r, we have p>n−r>rp>n-r>r. Thus pp divides neither r!r! nor (n−r)!(n-r)!, whereas p∣n!p\mid n!, so p∣(nr)p\mid\binom{n}{r}. By hypothesis, p∣Ln,rp\mid L_{n,r}, and hence p∣(n−r−jr−j)p\mid\binom{n-r-j}{r-j} for some 1≤j≤r1\le j\le r. But n−r−j<pn-r-j<p, so none of the factors in the numerator of this binomial coefficient is divisible by pp, a contradiction.

(b) Let pp be a prime divisor of n(n−1)⋯(n−r+1)n(n-1)\cdots(n-r+1), say p∣n−ap\mid n-a with 0≤a≤r−10\le a\le r-1. If p≤rp\le r, then p<2rp<2r. Suppose instead that p>rp>r. Then p∤r!p\nmid r!, so p∣(nr)p\mid\binom{n}{r} and hence p∣Ln,rp\mid L_{n,r}. Thus p∣(n−r−jr−j)p\mid\binom{n-r-j}{r-j} for some 1≤j≤r−11\le j\le r-1. Since p>r≥r−jp>r\ge r-j, the denominator (r−j)!(r-j)! is coprime to pp, so pp divides one of the numerator factors

n−r−j, n−r−j−1,…, n−2r+1.n-r-j,\ n-r-j-1,\ldots,\ n-2r+1.

Hence p∣n−bp\mid n-b for some bb with r+j≤b≤2r−1r+j\le b\le2r-1. In particular, r+1≤b≤2r−1r+1\le b\le2r-1. Therefore p∣b−ap\mid b-a, and since 0<b−a≤2r−10<b-a\le2r-1, we obtain p≤2r−1p\le2r-1. □大小规律

Proposition 4.3. Let Γ\Gamma be an abelian group of order (nr)\binom{n}{r}. If K(n,r)K(n,r) admits an affinely generating Γ\Gamma-magic map, then

(n,r)=(9,2)andΓ≅Z/6Z⊕Z/6Z.(n,r)=(9,2) \qquad\text{and} \qquad\Gamma\cong\mathbb{Z}/6\mathbb{Z}\oplus\mathbb{Z}/6\mathbb{Z}.

Proof. Corollary 4.1 first excludes the boundary cases. If r=1r=1, then Ln,1=1L_{n,1}=1. If n=2rn=2r, then every binomial coefficient in Ln,rL_{n,r} is 11. In either case affine generation would force exp⁡(Γ)=1\exp(\Gamma)=1, which is impossible because ∣Γ∣=(nr)>1|\Gamma|=\binom{n}{r}>1. Hence r≥2r\ge2 and n>2rn>2r.

By Corollary 3.3 and Theorem 1.3, every prime divisor of (nr)\binom{n}{r} divides Ln,rL_{n,r}. Thus Lemma 4.2 applies. We use Theorem 3.5 with k=rk=r and x=n−rx=n-r. If

n−r≥max⁡{r+13,279262r},n-r\ge\max\left\{r+13,\frac{279}{262}r\right\},

then

P+(n(n−1)⋯(n−r+1))>2r,P^{+}\bigl(n(n-1)\cdots(n-r+1)\bigr)>2r,

contrary to Lemma 4.2(b). Hence

n<max⁡{2r+13,541262r}.(8)n<\max\left\{2r+13,\frac{541}{262}r\right\}. \tag*{(8)}

Suppose first that r≥25r\ge25. Both quantities on the right of (8) are smaller than 6r6r, so n<6rn<6r and hence 1.2(n−r)<n1.2(n-r)<n. Put x=n−rx=n-r. Since x>r≥25x>r\ge25, Theorem 3.4 gives a prime pp with

n−r=x<p<1.2x<n,n-r=x<p<1.2x<n,

contradicting Lemma 4.2(a).

It remains to consider 2≤r≤242\le r\le24. In this range 541262r≤2r+13\frac{541}{262}r\le2r+13, so (8) gives n≤2r+12≤60n\le2r+12\le60. By Lemma 4.2(a), the rr consecutive integers

n−r+1,n−r+2,…,nn-r+1,n-r+2,\ldots,n

are all composite. A direct check of the integers up to 60 shows that the maximum length of a block of consecutive composites is 5, and that all blocks of this length are

24,25,26,27,28;32,33,34,35,36;48,49,50,51,52;54,55,56,57,58.24,25,26,27,28;\qquad32,33,34,35,36;\qquad48,49,50,51,52;\qquad54,55,56,57,58.

Thus r≤5r\le5. For r∈{4,5}r\in\{4,5\} we have n≤22n\le22, and there is no run of four consecutive composites up to 22. Hence only r=2,3r=2,3 remain.

For r=2r=2, the values n≤16n\le16 for which n−1n-1 and nn are both composite are 9, 10, 15, 16. For r=3r=3, the values n≤18n\le18 for which n−2,n−1,nn-2,n-1,n are all composite are 10, 16. We now test the prime-divisor obstruction from Corollary 3.3, using Theorem 1.3:

(n,r)(n,r)(nr)\binom{n}{r}Ln,rL_{n,r}prime divisors of (nr)\binom{n}{r}all divide Ln,rL_{n,r}
(9,2)(9,2)3662, 3yes
(10,2)(10,2)4573, 5no
(15,2)(15,2)105123, 5, 7no
(16,2)(16,2)120132, 3, 5no
(10,3)(10,3)120152, 3, 5no
(16,3)(16,3)560662, 5, 7no

Table 1.

Thus (n,r)=(9,2)(n,r)=(9,2) is the only possible pair.

In this case ∣Γ∣=36|\Gamma|=36 and L9,2=6L_{9,2}=6. Corollary 4.1 gives exp⁡(Γ)∣6\exp(\Gamma)\mid6, while Lemma 3.1 shows that both 2 and 3 divide exp⁡(Γ)\exp(\Gamma). Hence exp⁡(Γ)=6\exp(\Gamma)=6. The unique abelian group of order 36 and exponent 6 is

Γ≅Z/6Z⊕Z/6Z.\Gamma\cong\mathbb{Z}/6\mathbb{Z}\oplus\mathbb{Z}/6\mathbb{Z}.

Proof of Theorem 1.4. (a) The forward implication is Proposition 4.3. Conversely, suppose that (n,r)=(9,2)(n,r)=(9,2) and Γ≅Z/6Z⊕Z/6Z\Gamma\cong\mathbb{Z}/6\mathbb{Z} \oplus\mathbb{Z}/6\mathbb{Z}. Theorem 1.3 gives

Sred(K(9,2))≅(Z/6Z)8.S_{\mathrm{red}}(K(9,2)) \cong(\mathbb{Z}/6\mathbb{Z})^{8}.

Thus Γ↪Sred(K(9,2))\Gamma\hookrightarrow S_{\mathrm{red}}(K(9,2)), and Corollary 4.1 gives an affinely generating Γ\Gamma-magic map.

(b) Assume that K(n,r)K(n,r) admits a Γ\Gamma-distance magic labeling ℓ\ell, where ∣Γ∣=(nr)|\Gamma|=\binom{n}{r}. The labeling ℓ\ell is affinely generating, so part (a) gives

(n,r)=(9,2),Γ≅Z/6Z⊕Z/6Z.(n,r)=(9,2), \qquad\Gamma\cong\mathbb{Z}/6\mathbb{Z} \oplus\mathbb{Z}/6\mathbb{Z}.

For each i∈[9]i \in[9], put

Ti=∑u∈([9]2)i∈uℓ(u),T_i=\sum_{\substack{u\in\binom{[9]}{2}\\i\in u}}\ell(u),

and put

σ=∑u∈([9]2)ℓ(u).\sigma=\sum_{u\in\binom{[9]}{2}}\ell(u).

Let μ\mu be the magic constant. If {i,j}\{i,j\} is a vertex, then its neighbors are precisely the pairs containing neither ii nor jj. Therefore

μ=σ−Ti−Tj+ℓ({i,j}),\mu=\sigma-T_i-T_j+\ell(\{i,j\}),

and hence

ℓ({i,j})=μ−σ+Ti+Tj.\ell(\{i,j\})=\mu-\sigma+T_i+T_j.

Since ℓ\ell is bijective, the 36 sums

Ti+Tj,1≤i<j≤9,T_i+T_j,\qquad1\leq i<j\leq9,

are pairwise distinct. If Ti=TjT_i=T_j for some i≠ji\ne j, then choosing h∉{i,j}h\notin\{i,j\} would give Ti+Th=Tj+ThT_i+T_h=T_j+T_h, a contradiction. Hence T1,…,T9T_1,\ldots,T_9 are pairwise distinct, and

T={T1,…,T9}T=\{T_1,\ldots,T_9\}

is a weak Sidon set of size 9 in Γ\Gamma.

The group Z/6Z⊕Z/6Z\mathbb{Z}/6\mathbb{Z}\oplus\mathbb{Z}/6\mathbb{Z} has exactly three elements of order two. Therefore Theorem 3.6 gives

∣T∣≤⌊4⋅36+4⋅3+5+32⌋=⌊161+32⌋=7,|T|\leq\left\lfloor\frac{\sqrt{4\cdot36+4\cdot3+5+3}}{2}\right\rfloor =\left\lfloor\frac{\sqrt{161}+3}{2}\right\rfloor=7,

contradicting ∣T∣=9|T|=9. □

Department of Mathematics, Izmir Institute of Technology, 35430, Urla, Izmir, Turkey

Email address: [email protected]

References

  1. [1]S. Arumugam, D. Froncek, N. Kamatchi, Distance magic graphs—a survey, J. Indones. Math. Soc., Special Edition (2011), 11–26.DOI
  2. [2]B. Bajnok, Additive Combinatorics: A Menu of Research Problems, Discrete Mathematics and Its Appli-cations, Chapman and Hall/CRC, Boca Raton, 2018.arxiv.org/abs/1705.07444
  3. [3]A. Batal, Algebraic characterizations of generating and affinely generating Γ-magic maps and Γ-distance magic labelings on regular graphs, arXiv:2609.05934 [math.CO] (2026).arxiv.org/abs/2609.05934
  4. [4]T. Bier, Remarks on recent formulas of Wilson and Frankl, European J. Combin. 14 (1993), no. 1, 1–8.DOI
  5. [5]S. Cichacz, D. Froncek, K. A. Sugeng, S. Zhou, Group distance magic and antimagic graphs, Acta Math. Sin. (Engl. Ser.) 32 (2016), no. 10, 1159–1176.
  6. [6]J. E. Ducey, L. Engltehaler, J. Gathje, B. Jones, I. Pfaff, J. Plute, Integer diagonal forms for subset intersection relations, Algebraic Combinatorics 8 (2025), no. 1, 29–57.
  7. [7]P. Frankl, Intersection theorems and mod p rank of inclusion matrices, J. Combin. Theory Ser. A 54 (1990), no. 1, 85–94.DOI
  8. [8]D. Froncek, Group distance magic labeling of Cartesian product of cycles, Australas. J. Combin. 55 (2013), 167–174.
  9. [9]C. Godsil, G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics 207, Springer, New York, 2001.DOI
  10. [10]H. Haanpää, P. R. J. Östergård, Sets in abelian groups with distinct sums of pairs, J. Number Theory 123 (2007), no. 1, 144–153.DOI
  11. [11]A. Kotzig, On well spread sets of integers, Tech. Report CRM-161, Centre de Recherches Mathématiques, Université de Montréal, 1972.
  12. [12]S. Laishram, T. N. Shorey, The greatest prime divisor of a product of consecutive integers, Acta Arith. 120 (2005), no. 3, 299–306.DOI
  13. [13]J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. 28 (1952), no. 4, 177–181.DOI
  14. [14]I. Ruzsa, Solving a linear equation in a set of integers I, Acta Arith. 65 (1993), no. 3, 259–282.DOI
  15. [15]R. M. Wilson, A diagonal form for the incidence matrices of t-subsets vs. k-subsets, European J. Combin. 11 (1990), no. 6, 609–615.DOI

Paper details

vlnc:W_dfyddf83
Version
v1 · latest
Published
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents