Clique-Symmetric Uniform Hypergraphs

John P. McSorley Department of CCTM, London Metropolitan University, 100 Minories, London. EC3N 1JY mcsorley60@hotmail.com

Thomas D. Porter Department of Mathematics, Southern Illinois University, Carbondale. IL 62901-4408 tporter@math.siu.edu

Abstract

Let H be an r-uniform hypergraph of order p, and {H_{p1}, H_{p2}, …} be a countable sequence of r-uniform hypergraphs with H_{pn} having pn vertices. The sequence is H-removable if H_{p1} ≅ H and H_{pn} − S ≅ H_{p(n−1)} where S is any vertex subset of H_{pn} that induces a copy of H. This paper deals with the case H = K_{p}^{r}. It provides a construction of hypergraphs with a high degree of symmetry; where for any such hypergraph, all the ways of removing the vertices of any fixed number of disjoint K_{p}^{r}’s yields the same subgraph. The case r = 2 was studied by the authors in [3]. This paper gives the generalization to r-uniform hypergraphs for all r = 2, 3, . . ..

Keywords: clique, eulerian digraph, hypergraph, m-partite, Stirling number

1 The Case r = 2

We first briefly list the previous ideas in [3] and [4] concerning the case r = 2. The same vocabulary and definitions will be needed in our subsequent sections.

In general we follow the notation in [5]. In particular if W is a subset of the vertices of a graph G, then G[W] denotes the subgraph of G induced by W. The digraphs and graphs we consider are loopless and without multiple arcs or edges. We also use [p] = {1, …, p}.

Call a countable sequence of graphs {G_{pn}} = {G_{p1}, G_{p2}, …} K_{p}-removable if it satisfies the following two properties:

P1: G_{p1} ≅ K_{p}

P2: G_{pn}−W ≅ G_{p(n−1)} for every n ≥ 2 and every vertex subset W ⊂ V (G_{pn}) that induces a K_{p} in G_{pn}, i.e., G_{pn} ≅ K_{p}.

We often write G_{1} = G_{2} in place of G_{1} ≅ G_{2}.

Let D⃗ be a digraph of order p, with d^{+}(u) = d^{−}(u) for every vertex u in V (D⃗). Then D⃗ is an eulerian digraph if D⃗’s underlying ‘undirected’ graph is of one component, otherwise D⃗ is eulerian on each of its underlying components. Let N^{+}(i) denote the out-neighborhood of vertex i.

Consider a copy of K_{p} with vertices labelled {(1, 1), …, (p, 1)} = {(i, 1) | i ∈ [p]}; call these vertices vertices at level 1, and call this graph D_{1}(K_{p}). Now consider another copy of K_{p} with vertices labelled {(i, 2) | i ∈ [p]}, these are vertices at level 2. For any vertex (i, 2) join it to the vertices {(i′, 1) | i′ ∈ N^{+}(i)} at level 1, so we see that these edges are derived from the digraph D⃗. We call the graph so formed D_{2}(K_{p}). Now consider a third K_{p} with vertices labelled {(i, 3) | i ∈ [p]}, at level 3. Join any vertex (i, 3) to vertices {(i′, 2) | i′ ∈ N^{+}(i)} at level 2 and to vertices {(i′, 1) | i′ ∈ N^{+}(i)} at level 1; this is D_{3}(K_{p}).

Now, for any n ≥ 1, consider the graph which has been constructed level by level, up to n levels, according to the previous definition; call this graph D_{n}(K_{p}) or simply D_{n} when p is clear. We say the digraph D⃗ generates the sequence {D_{n}}. The vertices of D_{n}, V (D_{n}), are of the form (i, j) for every i ∈ [p] and every 1 ≤ j ≤ n, where j is their level; and the edges are of two types:

(i) fixed-level edges, say at level j

((i_{1}, j), (i_{2}, j)) is an edge for all i_{1}, i_{2} ∈ [p] where i_{1} ≠ i_{2}; and (ii) cross-level edges, for j > j′

((i, j), (i′, j′)) is an edge if and only if i′ ∈ N^{+}(i).

For any fixed i ∈ [p], let I_{i} = {(i, 1), …, (i, n)} = {(i, j) | 1 ≤ j ≤ n} be the set of vertices of D_{n} in ‘column i’. Then, because i ∉ N^{+}(i), i.e., because D⃗ doesn’t have loops, this is an independent set of vertices. Now let W be a subset of V (D_{n}) that induces a p-clique; then each of the p independent sets I_{1}, …, I_{p} contain exactly one vertex from W.

Let W = {(1, v_{1}), …, (p, v_{p})} be an arbitrary vertex subset in D_{n} with exactly one vertex from each independent set I_{i}. Let W have vertices at m different levels: ℓ_{1}, …, ℓ_{m} where ℓ_{1} < ⋯ < ℓ_{m}. For 1 ≤ k ≤ m, let V_{k} = {i | v_{i} = ℓ_{k}} ≠ ∅ be the set of first coordinates of all vertices of W at level ℓ_{k}. Then the sets V_{1}, …, V_{m} partition [p].

In D_{n} consider two levels of vertices, V_{i} and V_{j} with l_{i} < l_{j} and let y ∈ V_{i} and x ∈ V_{j}. Then if the edge e = xy is in the induced subgraph D_{n}[W] of D_{n} we call the arc (x, y) in our original generating digraph D⃗ a W -skew arc. Hence a W -skew arc of D⃗ gives rise to edges in D_{n} which join different levels of W.

Let (A, B) denote the set of arcs in D from A to B, i.e., all arcs (a, b) with a ∈ A and b ∈ B.

Theorem 1.1 ([4]). With the above notation: a set W of vertices of D_{n} with level-partition V_{1}, V_{2}, …, V_{m}, induces a p-clique iff the associated W - skew arcs form a complete symmetric m-partite subdigraph in D⃗. □

Theorem 1.2 ([4]). Let D⃗ be any eulerian digraph of order p. Then its generated sequence of graphs {D_{n}} is K_{p}-removable. □

2 The Hypergraph Construction

The ideas and results in Section 1 lead to the following extension to hypergraphs. A hypergraph consists of a collection of vertices and a collection of edges; if the vertex set is V, then the edges are subsets of V. A hypergraph is r-uniform if all of its edges have size r. The complete r-uniform hypergraph of order p, denoted by K_{p}^{r}, is the hypergraph with vertex set V = [p] and with edges all of the \binom{p}{r} r-subsets of V.

For a fixed pair p and r, with p ≥ r ≥ 2, let {H_{pn}^{r}} = {H_{p1}^{r}, H_{p2}^{r}, H_{p3}^{r}, …} be a sequence of r-uniform hypergraphs where H_{pn}^{r} has pn vertices. Such a sequence is called K_{p}^{r}-removable if it satisfies the following properties:

P1 H_{p1}^{r} ≅ K_{p}^{r}

P2 H_{pn}^{r} − K_{p}^{r} ≅ H_{p(n−1)}^{r} for every n ≥ 2 and for every (induced) K_{p}^{r} in H_{pn}^{r}.

For each pair p and r, with p ≥ r ≥ 2, we show the existence of K_{p}^{r}- removable sequences.

Let (A_{1}, …, A_{m}) denote a partition of [p]. We define the complete mpartite r-uniform hypergraph of order p, denoted K_{|A_{1}|,...,|A_{m}|}^{r}, as follows: The vertex set is [p], and an r-subset, Q, of [p] is an edge if and only if Q contains at most r − 1 members from any class A_{j}. So, eg., K_{n,n}^{r} has 2n vertices and

\binom{n}{1}\binom{n}{r − 1} + \binom{n}{2}\binom{n}{r − 2} + ⋯ + \binom{n}{r − 1}\binom{n}{1} = \binom{2n}{r} − 2\binom{n}{r}

edges. Notice that for r = 2 we have the usual K_{n,n}^{2}, the complete bipartite graph with n^{2} edges. The number of edges in K_{|A_{1}|,...,|A_{m}|}^{r} is

e(K_{|A_{1}|,...,|A_{m}|}^{r}) = ∑ \binom{|A_{1}|}{k_{1}} ⋯ \binom{|A_{m}|}{k_{m}}

where the sum is over all k_{1} +⋯+k_{m} = r, with 0 ≤ k_{j} < r for all 1 ≤ j ≤ m.

Motivated by Theorem 1.1 we now construct K_{p}^{r}-removable sequences, {H_{pn}^{r}}, from each fixed partition (A_{1}, …, A_{m}) of [p].

With {H_{pn}^{r}} = {H_{p1}^{r}, H_{p2}^{r}, …} the construction is as follows:

1. H_{p(m−1)}^{r} ≅ (m − 1)K_{p}^{r}, i.e., we first start with m − 1 disjoint levelled copies of K_{p}^{r}.

2. For n ≥ m, the graph H_{pn}^{r} is defined as follows. First, take n disjoint levelled copies of K_{p}^{r}; the notation for the vertices introduced at level 1, level 2, …, level n, is the same as in Section 1, eg., the copy of K_{p}^{r} at level j has vertex set {(1, j), (2, j), …, (p, j)}. From the given partition (A_{1}, …, A_{m}) of [p], to each A_{j}, 1 ≤ j ≤ m, we select a distinct level l_{A_{j}}, where 1 ≤ l_{A_{j}} ≤ n. We use (A_{1}, …, A_{m}) → (l_{A_{1}}, …, l_{A_{m}}) to denote the selected levels. Notice that to the partition (A_{1}, …, A_{m}) there are m!\binom{n}{m} such level (l_{A_{1}}, …, l_{A_{m}}) selections.

To each fixed level selection (A_{1}, …, A_{m}) → (l_{A_{1}}, …, l_{A_{m}}) we identify the set A_{j} with their corresponding vertices in level l_{A_{j}}. The identification is through the first coordinates of the vertices in l_{A_{j}}. For example, if A_{j} = {x_{1}, …, x_{|A_{j}|}}, then we identify A_{j} with the vertices, Ã_{j} = {(x_{1}, l_{A_{j}}), (x_{2}, l_{A_{j}}), …, (x_{|A_{j}|}, l_{A_{j}})} in level l_{A_{j}} of H_{pn}^{r}. We then have (A_{1}, …, A_{m}) ≅ (Ã_{1}, …, Ã_{m}) with |Ã_{1}| + ⋯ + |Ã_{m}| = p, for each of the m!\binom{n}{m} such (Ã_{1}, …, Ã_{m})’s. We then add to the initial n disjoint copies of K_{p}^{r}, all edges in ⋃ E(K_{|Ã_{1}|,...,|Ã_{m}|}^{r}), where the union is over all

m!\binom{n}{m} such (Ã_{1}, …, Ã_{m})’s. We call this graph H_{pn}^{r}, the hypergraph generated by the partition (A_{1}, …, A_{m}).

We use the symbol gen(A_{1}, …, A_{m})^{r} to denote such a sequence {H_{pn}^{r}}. Notice by the construction, from (A_{1}, …, A_{m}) and a chosen level-(Ã_{1}, …, Ã_{m}), the vertices Ã_{1} ∪ Ã_{2} … ∪ Ã_{m} in V (H_{pn}^{r}) induce a K_{p}^{r}. The other K_{p}^{r}’s in H_{pn}^{r} are ‘fixed-level’ cliques, i.e., the K_{p}^{r} introduced at each level 1, …, n. For the vertex subsets I_{i}, as defined earlier, the construction yields edges which contain at most one vertex from any ‘column i’. Hence I_{i} is an independent set in H_{pn}^{r}. Also notice that each induced K_{p}^{r} contains exactly one vertex from each I_{i}, 1 ≤ i ≤ p.

For r = 2, the connection to the digraph D⃗ in Theorem 1.2 is as follows: Consider any complete m-partite graph G = K_{|A_{1}|,...,|A_{m}|}^{2}. Let D⃗ be the digraph formed from G by replacing each edge xy in G with two arcs (x, y) and (y, x). Then D⃗ is eulerian and it generates the K_{p}^{2}-removable sequence {D_{n}} as in Theorem 1.2. Suppose W induces a K_{p}^{r} in H_{pn}^{r}. Let the vertices of W be {(i, w_{i}) | 1 ≤ i ≤ p}. In the graph H_{pn}^{r} − W, the set I_{i}\{(i, w_{i})} is an independent set: call this the i-th independent set of H_{pn}^{r} − W. Now we construct an isomorphism ϕ between the vertices of H_{pn}^{r} −W and the vertices of H_{p(n−1)}^{r}. Under ϕ, for a fixed i ∈ [p], the vertices in the i-th independent set of H_{pn}^{r} − W, namely in the set I_{i}\{(i, w_{i})}, are mapped to the vertices in the i-th independent set of H_{p(n−1)}^{r}, namely to the set {(i, 1), …, (i, n − 1)}, as follows:

ϕ(i, j) = \begin{cases}(i, j − 1), & for w_{i} < j ≤ n \\ (i, j), & for 1 ≤ j < w_{i}. \end{cases}

In [3] it is shown that ϕ is an isomorphism. It is straightforward to show that ϕ moves edges in H_{pn}^{r} − W to edges in H_{p(n−1)}^{r}. We have:

Theorem 2.1. Let p ≥ r ≥ 2, and let (A_{1}, …, A_{m}) be any partition of [p]. Then the sequence of hypergraphs gen(A_{1}, …, A_{m})^{r} is a K_{p}^{r}-removable sequence. □

In the following let S(m, t) be the Stirling numbers of the second kind. Notice, by the above construction of gen(A_{1}, …, A_{m})^{r} = {H_{pn}^{r}}, H_{pn}^{r}

contains essentially two types of induced K_{p}^{r}’s, either fixed-level or crosslevel. The vertices of a K_{p}^{r} are either all at a fixed level, or are at exactly m different levels. However, by the isomorphism ϕ, the removal of any one of these two types of induced K_{p}^{r}’s yields up to isomorphism the same subhypergraph. So, the hypergraph construction gives the clique-symmetric uniform hypergraph we were searching for that does not simply possess n fixed-level type K_{p}^{r}’s.

We remark that the gen(A_{1}, …, A_{m})^{r} construction can be slightly modified to also contain cross-level K_{p}^{r}’s containing vertices from exactly t levels, for all 2 ≤ t ≤ m − 1, as follows: The partition (A_{1}, …, A_{m}) of [p] is given. For fixed t, 2 ≤ t ≤ m − 1, let (b_{1}, …, b_{t}) be a partition of [m]. From (b_{1}, …, b_{t}) define the corresponding (B_{1}, …, B_{t}) where B_{j} = ⋃_{k∈b_{j}} A_{k}. Notice

that (B_{1}, …, B_{t}) is then a partition of [p]. Also notice that K_{|B_{1}|,...,|B_{t}|}^{r} is a complete t-partite sub-hypergraph of K_{|A_{1}|,...,|A_{m}|}^{r}; and there are t!S(m, t) such possible (b_{1}, …, b_{t})’s, and hence t!S(m, t) such possible (B_{1}, …, B_{t})’s. We remark that in general, for any complete m-partite graph, where m ≥ 3, there are S(m, t) complete t-partite spanning subgraphs, where 2 ≤ t ≤ m − 1. As before, each (B_{1}, …, B_{t}) is assigned a level-selection (ℓ_{B_{1}}, …, ℓ_{B_{t}}) producing the corresponding (B̃_{1}, …, B̃_{t}). Now define X_{t} = ⋃ E(K_{|B̃_{1}|,...,|B̃_{t}|}^{r}), where

the union is over all (B̃_{1}, …, B̃_{t})’s. For the generalized construction from a given (A_{1}, …, A_{m}), we again start with n disjoint levelled K_{p}^{r}’s. We add to these the edges X_{2} ∪ X_{3} ⋯ ∪ X_{m}. It can be shown the isomorphism ϕ works for this graph as well.

We call such a K_{p}^{r}-removable sequence {H_{pn}^{r}} as constructed above a tgen(A_{1}, …, A_{m})^{r} sequence. We note that for a given (B_{1}, …, B_{t}) and its associated t!\binom{n}{t} corresponding (B̃_{1}, …, B̃_{t})’s, that any permutation σ(B_{1}, …, B_{t}) of (B_{1}, …, B_{t}), yields the same set of (B̃_{1}, …, B̃_{t})’s as (B_{1}, …, B_{t}) does. Hence there are t!S(m, t)\binom{n}{t} such (B̃_{1}, …, B̃_{t})’s, for each 2 ≤ t ≤ m. By the construction every K_{p}^{r} in H_{pn}^{r} is in one-to-one correspondence with a fixed (B̃_{1}, …, B̃_{t}). For the case t = 1, we interpret the (B̃_{1})’s as the beginning n-level copies of K_{p}^{r}, so X_{1} ≅ nK_{p}^{r}. Hence we have a rather nice formula for the number of K_{p}^{r}’s in H_{pn}^{r}.

Theorem 2.2. Let (A_{1}, …, A_{m}) be a partition of [p]. For the K_{p}^{r}-removable

sequence t-gen(A_{1}, …, A_{m})^{r} = \{H_{pn}^{r}\}, the hypergraph H_{pn}^{r} has ∑_{t=1}^{m} t!S(m, t)\binom{n}{t}

= n^{m} K_{p}^{r}’s. □

More directly, the value n^{m} in Theorem 2.2 can be interpreted as follows: From the given initial partition (A_{1}, …, A_{m}) of [p] we embed each A_{j} (by our definition of Ã_{j}) into any of the n levels, level 1, …, level n, thus creating (B̃_{1}, …, B̃_{t}). Hence there are n^{m} such embeddings. We remark also that, by the defined construction, for each embedding (B̃_{1}, …, B̃_{t}) the vertices B̃_{1} ∪ ⋯ ∪ B̃_{t} induce a K_{p}^{r} in H_{pn}^{r}.

Example Let p = 5, r = 3, and (A_{1}, A_{2}, A_{3}) be the partition of {1, 2, 3, 4, 5} with A_{1} = {1, 2}, A_{2} = {3, 5}, and A_{3} = {4}. Consider the t-gen(A_{1}, A_{2}, A_{3})^{3} = \{H_{5n}^{3}\} sequence. The graph for n = 3, i.e., H_{(5)(3)}^{3} has 1!S(3, 1)\binom{3}{1}+2!S(3, 2)\binom{3}{2}+ 3!S(3, 3)\binom{3}{3} = 27 induced K_{5}^{3}’s. An example of one of these cliques for t = 2 is as follows: with (B_{1}, B_{2}) = (A_{1} ∪ A_{3}, A_{2}), let (B_{1}, B_{2}) → (ℓ_{B_{1}}, ℓ_{B_{2}}) = (3, 2) be a level-selection, giving (B̃_{1}, B̃_{2}). Then the vertices in V (H_{(5)(3)}^{3}), namely, B̃_{1} ∪ B̃_{2} = {(3, 1), (3, 2), (3, 4), (2, 3), (2, 5)}, induce a K_{5}^{3} in H_{(5)(3)}^{3}.

K_{pn}^{r} is the complete r-uniform hypergraph on pn vertices.

We end by showing, with the exception of {K_{pn}^{r}}, that for any K_{p}^{r}- removable sequence {H_{pn}^{r}}, with p ≥ r ≥ 2, any member H_{pn}^{r} of the sequence does not contain a K_{p+1}^{r}. So, e.g., for the case r = 2, the clique number is always ω(H_{pn}^{2}) = p for all n. We remark that the constructions given in this paper produce ways to generate K_{p}^{r}-removable sequences, we do not claim these are the only K_{p}^{r}-removable sequences. However, our final theorem applies to any K_{p}^{r}-removable sequence.

Theorem 2.3. Suppose the n-th member H_{pn}^{r} of a K_{p}^{r}-removable sequence contains a K_{p+1}^{r}, then H_{pn}^{r} is K_{pn}^{r}.

Proof. Suppose that H_{pn}^{r} contains a K_{p+1}^{r}. Without loss of generality, we assume V (H_{pn}^{r}) is partitioned into n K_{p}^{r}’s: L_{1}, L_{2}, …, L_{n}, so that some vertex y in L_{2} is such that L_{1} ∪ {y} is an induced K_{p+1}^{r} in H_{pn}^{r}. Let x be any vertex in L_{1}. Deleting the n − 1 K_{p}^{r}’s: L_{3}, L_{4}, …, L_{n}, L_{1} + {y} − {x}, in this order, we obtain L_{2} + {x} − {y}. Since {H_{pn}^{r}} is K_{p}^{r}-removable, L_{2} + {x} − {y} is necessarily a K_{p}^{r}. Hence, L_{2} ∪ {x} is a K_{p+1}^{r}, and the union of L_{1} and L_{2} is K_{2p}^{r}. Consequently the removal of any n − 2 disjoint K_{p}^{r}’s must produce K_{2p}^{r}. This implies that the union of every two levels L_{i} and L_{j} induce a K_{2p}^{r}; therefore, H_{pn}^{r} is K_{pn}^{r}.

For other papers on graph sequences see Barefoot, Entringer, and Jackson [1], and its bibliography; see also Duchet, Tuza, and Vestergaard [2].

References

[1] C.A. Barefoot, R.C. Entringer, D.E. Jackson, Graph theoretic modelling of cellular development II , Proc. 19-th Southeastern Internat. Conf. on Combinatorics, Graph Theory, and Computing, (Baton Rouge, LA, 1988), Congr. Numer. 65 (1988) 135–146.

[2] P. Duchet, Z. Tuza, P.D. Vestergaard, Graphs in which all spanning subgraphs with r fewer edges are isomorphic, Proc. 19-th Southeastern Internat. Conf. on Combinatorics, Graph Theory, and Computing, (Baton Rouge, LA, 1988), Congr. Numer. 67 (1988) 45–57.

[3] J.P. McSorley and T.D. Porter,K_{p}-removable sequences of graphs, to appear, Journal of Combinatorial Mathematics and Combinatorial Computing.

[4] J.P. McSorley and T.D. Porter, Generating sequences of clique-symmetric graphs via Eulerian digraphs, to appear, Discrete Mathematics.

[5] D.B. West, Introduction to Graph Theory, 2nd Edition, (Prentice Hall, 2001).