SuperHyperGraph Coloring Game and SuperHyperGraph Domination Game

Takaaki Fujita1,∗

1 Independent
Researcher, Tokyo, Japan.
Email: Takaaki.fujita060@[Link]

Abstract
A finite hypergraph generalizes an ordinary graph by allowing each hyperedge to connect
an arbitrary nonempty subset of vertices, thereby modeling genuinely multiway interactions.
Taking this idea one step further, a finite SuperHyperGraph is obtained by iterating the powerset
construction: set-valued objects created at one level can serve as vertices (or edge endpoints) at
the next. This yields a principled formalism for hierarchical, multi-layer relational structure.
Vertex coloring is a classical theme in graph theory. One assigns colors to vertices so that
adjacent vertices receive distinct colors and seeks to minimize the number of colors used, namely
the chromatic number. In parallel, there is a broad literature on coloring games and coloring
dynamics, where colors evolve through local updates governed either by competing players (as
in game-chromatic variants) or by prescribed interaction rules (as in stochastic or rule-based
recoloring processes). In particular, what is often called the HyperGraph Coloring Game in the
dynamical setting is not a two-player optimization game, but rather a local recoloring process
(typically a finite-state Markov chain) whose transitions are determined by selecting a hyperedge
and updating colors on that hyperedge according to a specified rule. By contrast, the Graph
Domination Game is a genuine two-player game: players alternately select vertices, each move
must newly dominate at least one previously undominated vertex (the chosen vertex or one of
its neighbors), and Dominator aims to finish in as few moves as possible.
In this paper, we introduce two further generalizations within the powerset-based Super-
HyperGraph framework. First, we define the SuperHyperGraph Coloring Game as a natural
SuperHyperGraph-level analogue of the HyperGraph recoloring process, and we explicitly in-
terpret it as a coloring dynamics on supervertices. Second, we define the SuperHyperGraph
Domination Game as an extension of the HyperGraph Domination Game.
Keywords: HyperGraph, SuperHyperGraph, Graph Domination Game, Coloring Game
2020 Mathematics Subject Classification: 05C65 (Hypergraphs)

1. Introduction

1.1 HyperGraph and SuperHyperGraph

Graphs are a standard language for representing relational data: vertices model entities, and edges
encode pairwise interactions. Many systems of practical interest, however, exhibit higher-order
dependence—simultaneous interactions among three or more participants—that cannot be captured
faithfully by binary edges alone. Finite hypergraphs address this limitation by allowing a hyperedge to
connect an arbitrary nonempty subset of vertices, thereby modeling genuinely multiway relations [1,2].
Beyond high arity, complex datasets often display pronounced hierarchy: groups contain sub-
groups, components are built from modules, and networks form layered architectures. A convenient
way to encode such nested structure is to iterate the powerset construction. This leads to finite
SuperHyperGraphs, in which set-valued objects created at one level may serve as vertices at the next,
producing families of supervertices organized across multiple scales [3–5]. Accordingly, SuperHyper-
Graphs unify two complementary forms of expressiveness: multiway incidence (as in hypergraphs)
and aggregation through levels (e.g., groups, groups of groups, and so on). Related hierarchical
modeling viewpoints also arise in applied sciences and the study of complex networks [6, 7].
Unless stated otherwise, the index n in P n (·) and the level n of an n–SuperHyperGraph are taken
to be nonnegative integers. For quick reference, Table 1.1 summarizes the essential distinctions among
graphs, hypergraphs, and n-SuperHyperGraphs.
∗ Corresponding author (Takaaki.fujita060@[Link])
Aspect Graph Hypergraph n-SuperHyperGraph
Objects Vertices, edges. Vertices, hyperedges. n-supervertices, superhyper-
edges.
Links connect Two vertices. Any nonempty vertex subset. Nonempty supervertex sub-
sets (with nested superver-
tices).
Formal model V
. SHG(n) = (V, E), V ⊆


G = (V, E), E ⊆ 2
H = (V, E), E ⊆ P(V ) \ {∅}.
P n (V0 ), E ⊆ P(V ) \ {∅}.
Main emphasis Pairwise relations. Higher-order relations. Higher-order and hierarchi-
cal (multi-level) relations.

Table 1.1: Compact comparison of graphs, hypergraphs, and n-SuperHyperGraphs.

1.2 Graph Coloring Game

Vertex coloring is one of the central themes of graph theory: one assigns colors to vertices so that
adjacent vertices receive distinct colors, and one aims to minimize the number of colors (the chromatic
number). This paradigm has been extended in several directions, including hypergraph coloring [8–10]
and, more recently, SuperHyperGraph coloring [11], where the objects to be colored and the incidence
constraints reflect higher-order and hierarchical structure.
A complementary line of research studies coloring games and recoloring dynamics, in which colors
evolve through local updates. Here it is important to distinguish two common usages of the term
“game.” On the one hand, there are genuine two-player coloring games, where players alternate moves
and strategic objectives (e.g., the game chromatic number) are central; the Graph Coloring Game is
a prominent example [12, 13]. On the other hand, some works use “coloring game” more loosely to
refer to rule-based (often stochastic) coloring processes in which a local neighborhood is selected and
recolored according to a prescribed interaction rule; the resulting evolution is naturally modeled as a
finite-state Markov chain. In this dynamical sense, the HyperGraph Coloring Game [14] is best viewed
as a recoloring dynamics rather than a competitive two-player game. These perspectives connect
combinatorial coloring to algorithmic, probabilistic, and game-theoretic viewpoints, and motivate
our subsequent SuperHyperGraph-level generalizations.

1.3 Graph Domination Game

The Graph Domination Game is played by two players who alternately choose vertices, and each
move must newly dominate at least one previously undominated vertex (the chosen vertex or one of
its neighbors), with Dominator trying to finish in as few moves as possible [15–17]. The HyperGraph
Domination Game is the analogous game on a hypergraph: players alternately choose vertices, and
each move must newly dominate at least one previously undominated vertex (the chosen vertex or
any vertex that shares a hyperedge with it), with Dominator minimizing the number of moves.

1.4 Our Contributions

In this paper, we propose two further generalizations within the powerset-based SuperHyperGraph
framework. First, we define the SuperHyperGraph Coloring Game as an extension of the HyperGraph
Coloring Game. Second, we define the SuperHyperGraph Domination Game as an extension of the
HyperGraph Domination Game. We then investigate fundamental structural properties of the re-
sulting dynamics and explain how the classical graph- and hypergraph-based games are recovered as
special cases.

2
2. Preliminaries

This section establishes the notation used throughout the paper and reviews the basic set-theoretic
and combinatorial concepts needed in later sections.

2.1 SuperHyperGraphs
We begin with the set-theoretic operations underlying SuperHyperGraphs and then recall the relevant
graph-theoretic definitions.

Definition 2.1 (Base set). A base set S is the underlying universe of admissible objects in the setting
under consideration, i.e.,

S = { x | x is an admissible object in the given context }.

Accordingly, every element of P(S)—and, more generally, of any iterated powerset—is ultimately
formed from elements of S.

Definition 2.2 (Powerset). (see [18]) For a set S, its powerset is the family of all subsets of S:

P(S) = { A | A ⊆ S }.

In particular, ∅ ∈ P(S) and S ∈ P(S).

Definition 2.3 (Hypergraph). [19, 20] A hypergraph is an ordered pair H = (V, E) where

• V is a finite set of vertices, and

• E is a finite family of nonempty subsets of V , called hyperedges.

Thus a hyperedge may contain more than two vertices, allowing one to model genuinely multiway
relations.

Definition 2.4 (n-fold iterated powerset). [21] Let X be a set. Define P 1 (X) := P(X) and, for
n ≥ 1, set recursively
P n+1 (X) := P P n (X) .

When excluding the empty set, we write

P∗n (X) := P n (X) \ {∅}.

Definition 2.5 (n-SuperHyperGraph). (see [3,22]) Let V0 be a finite, nonempty base set, and define
the iterated powersets by

P 0 (V0 ) := V0 , P k+1 (V0 ) := P P k (V0 )

(k ∈ N ∪ {0}).

For n ≥ 0, an n-SuperHyperGraph on V0 is a pair

SHG(n) = (V, E)

satisfying
V ⊆ P n (V0 ) and E ⊆ P(V ) \ {∅}.

Elements of V are called n-supervertices, and elements of E are called superhyperedges; equivalently,
each superhyperedge is a nonempty subset of the supervertex set V .

3
2.2 HyperGraph Coloring Game
We formalize an interaction-based hypergraph coloring game as a discrete-time stochastic process on
the space of all vertex colorings. This framework captures multi-party simultaneous interactions: at
each round a hyperedge (group) is selected, and the colors of its vertices may change according to a
prescribed probability rule.

Definition 2.6 (Color set and coloring configurations). Let H = (V, E) be a finite hypergraph. Fix
a finite set of colors C with |C| = r. A (global) coloring configuration on H is a map

σ : V → C.

We denote by Ω := C V the state space of all colorings of V . For a hyperedge g ∈ E, the restriction of
σ to g is written σ|g ∈ C g .

Definition 2.7 (Local patterns and update operator). Let g ∈ E. A coloring pattern on g is any
map τ : g → C, i.e. τ ∈ C g . Given a global configuration σ ∈ Ω and a pattern τ ∈ C g , define the
updated configuration σ g←τ ∈ Ω by
(
τ (v), v ∈ g,
σ g←τ (v) :=
σ(v), v ∈ V \ g.

Definition 2.8 (Hypergraph coloring game (general interaction model)). [14] A hypergraph coloring
game on H = (V, E) with color set C is specified by a transition rule
G 
p:E×Ω× C g → [0, 1], (g, σ, τ ) 7→ p(g, σ, τ ),
g∈E

such that for every σ ∈ Ω, X X

p(g, σ, τ ) = 1.
g∈E τ ∈C g

The game evolves as a time-homogeneous Markov chain (Σt )t≥0 on Ω with

Pr Σt+1 = σ g←τ
 
Σt = σ = p(g, σ, τ ),

and no other transitions.

Proposition 2.1 (Well-defined Markov kernel). Let P : Ω × Ω → [0, 1] be defined by

1{σ 0 = σ g←τ } p(g, σ, τ ).

X X
P (σ, σ 0 ) :=
g∈E τ ∈C g

Then P is a stochastic matrix on Ω (i.e. P (σ, σ 0 ) = 1 for all σ).

P
σ 0 ∈Ω

Proof. Fix σ ∈ Ω. For each pair (g, τ ) there is exactly one resulting state σ g←τ ∈ Ω. Hence summing
over σ 0 ∈ Ω collapses the indicator and yields
X X X
P (σ, σ 0 ) = p(g, σ, τ ) = 1,
σ 0 ∈Ω g∈E τ ∈C g

by the defining condition of the interaction rule.

Definition 2.9 (Associated directed state graph). The state graph associated with the coloring game
is the weighted directed graph
H ∗ = (Ω, A, w),

where (σ, σ 0 ) ∈ A iff P (σ, σ 0 ) > 0, and the arc weight is w(σ, σ 0 ) := P (σ, σ 0 ). Equivalently, (σ, σ 0 ) is
an arc precisely when there exists some g ∈ E and τ ∈ C g with p(g, σ, τ ) > 0 and σ 0 = σ g←τ .

4
Remark 2.1 (Factorized form). Often one chooses a hyperedge first and then a pattern conditional
on it. Formally, one may write
p(g, σ, τ ) = µ(g) qg (σ, τ ),
where µ is a probability distribution on E (edge-selection rule) and qg (σ, ·) is a probability distribution
on C g (local update rule). This factorization is optional; the definition above allows p to encode both
choices jointly.

Definition 2.10 (Memoryless coloring game). The coloring game is memoryless if p(g, σ, τ ) does not
depend on the current configuration σ, i.e. there exist constants p(g, τ ) such that

p(g, σ, τ ) = p(g, τ ) for all g ∈ E, σ ∈ Ω, τ ∈ C g .

Definition 2.11 (Partially memoryless coloring game). Let P be the transition matrix of a (possibly
state-dependent) coloring game on Ω. We say the game is partially memoryless with parameter
β ∈ (0, 1] if there exist a memoryless transition matrix M on Ω and another transition matrix P0 on
Ω such that
P = βM + (1 − β)P0 .

2.3 HyperGraph Domination Game

In a HyperGraph Domination Game, players alternately choose vertices; each move must newly
dominate some undominated vertex (itself or sharing a hyperedge). Dominator minimizes moves,
Staller maximizes.

Definition 2.12 (Adjacency, neighborhoods, and domination in a hypergraph). Let H = (V, E) be a

finite hypergraph. Two distinct vertices x, y ∈ V are said to be adjacent if there exists an edge e ∈ E
such that {x, y} ⊆ e. For v ∈ V , define the open neighborhood and closed neighborhood by

NH (v) := { u ∈ V \ {v} | u is adjacent to v }, NH [v] := NH (v) ∪ {v}.

For S ⊆ V , define the dominated set (by S) as

DomH (S) :=
[
NH [v].
v∈S

A vertex x ∈ V is dominated by S if x ∈ DomH (S).

Definition 2.13 (HyperGraph Domination Game). Let H = (V, E) be a finite hypergraph. The
domination game on H is played by two players, Dominator and Staller, who alternately select
vertices
v1 , v2 , · · · ∈ V, Si := {v1 , . . . , vi }.
A move vi is called legal if it dominates at least one vertex not dominated before, i.e.,

DomH (Si ) ) DomH (Si−1 ) equivalently NH [vi ] \ DomH (Si−1 ) 6= ∅.

The game ends after k moves if DomH (Sk ) = V . Dominator aims to minimize the game length k,
while Staller aims to maximize k.
If Dominator starts and both players play optimally, the resulting number of moves is denoted by
γg (H) and called the game domination number of H. If Staller starts, the resulting number of moves
is denoted by γg0 (H).

Proposition 2.2 (Consistency with the classical graph domination game). Let G = (V (G), E(G))
be a finite simple graph and let HG = (V (G), E(HG )) be the 2-uniform hypergraph with E(HG ) :=
{{x, y} : xy ∈ E(G)}. Then a sequence of moves is legal in the domination game on G if and only

5
if it is legal in the HyperGraph Domination Game on HG , and the dominated sets coincide at each
stage. Consequently,
γg (HG ) = γg (G) and γg0 (HG ) = γg0 (G).

Proof. For every v ∈ V (G), the vertices adjacent to v in HG are exactly the graph-neighbors of
v in G, because {u, v} ∈ E(HG ) holds precisely when uv ∈ E(G). Hence NHG (v) = NG (v) and
therefore NHG [v] = NG [v]. Taking unions over the played set S yields DomHG (S) = v∈S NHG [v] =
S

v∈S NG [v], which is exactly the dominated set in the classical domination game on G. Thus, a move
S

is legal in one game if and only if it is legal in the other, and the termination condition Dom(·) = V
agrees as well. Therefore the optimal game lengths coincide.

3. SuperHyperGraph Coloring Game

We now extend the (hyper)graph recoloring dynamics to the SuperHyperGraph setting. The key
modeling gain is that the objects being colored are no longer atomic vertices, but n-supervertices—set-
valued entities encoding groups, groups of groups, and more general multi-level aggregates. A super-
hyperedge then represents an interaction group of aggregates. Thus a single local update can model
the coordinated evolution of multiple higher-level units, while the interaction rule may (optionally)
exploit their internal set-structure (overlaps, sizes, or constituent memberships) to capture genuinely
hierarchical coupling.

Definition 3.1 (SuperHyperGraph Coloring Game (stochastic recoloring dynamics)). Let SHG(n) =
(V, E) be an n-SuperHyperGraph (Definition 2.5), and let C be a finite set of colors. Let

Ω := C V

be the set of all colorings of the supervertex set V . For each e ∈ E and each local pattern τ ∈ C e ,
define σ e←τ ∈ Ω for σ ∈ Ω by
(
e←τ τ (v), v ∈ e,
σ (v) :=
σ(v), v ∈ V \ e.

A SuperHyperGraph Coloring Game on SHG(n) is a discrete-time Markov chain (Σt )t≥0 on Ω

specified by an interaction rule

(e, σ, τ ) | e ∈ E, σ ∈ Ω, τ ∈ C e −→ [0, 1],


pSHG :

such that for every σ ∈ Ω, X X

pSHG (e, σ, τ ) = 1,
e∈E τ ∈C e

and with one-step transition probabilities

Pr Σt+1 = σ e←τ
 
Σt = σ = pSHG (e, σ, τ ),

with no other transitions.

Remark 3.1 (Hierarchical interpretation and hierarchy-aware rules). When n ≥ 1, each supervertex
v ∈ V ⊆ P n (V0 ) is a set-valued object. Hence a color Σt (v) ∈ C can be interpreted as a macro-state
of an aggregate (e.g., a community label, an operational mode of a module, or a status of a group).
The recoloring step on e ∈ E updates the macro-states of all aggregates in the interaction group e.
To make the hierarchical nature explicit in the dynamics, one may choose pSHG to depend not
only on the current colors σ|e but also on structural features of supervertices in e, such as their

6
sizes or overlaps of underlying constituents. For example, one can define the flattening map Flatn :
P n (V0 ) → P(V0 ) by

Flat0 (x) := {x} (x ∈ V0 ), Flatr+1 (X) := Flatr (y) (X ∈ P r+1 (V0 )),
[

y∈X

and then let the interaction rule favor superhyperedges whose members share many constituents, e.g.,

pSHG (e, σ, τ ) ∝ w(e, σ) 1{τ ∈ A(e, σ)}, Flatn (u) ∩ Flatn (v) ,
X
w(e, σ) :=
{u,v}⊆e

for some admissible set of local patterns A(e, σ) ⊆ C e . Such choices preserve Definition 3.1 while
highlighting that the state space and the update selection can genuinely exploit multi-level structure.

Theorem 3.1 (SuperHyperGraph Coloring Games generalize HyperGraph Coloring Games). Every
HyperGraph Coloring Game is a special case of a SuperHyperGraph Coloring Game. More precisely,
let H = (V, E) be a finite hypergraph and let pH be any interaction rule defining a HyperGraph
Coloring Game on H with color set C and state space Ω = C V . Define the 0-SuperHyperGraph

SHG(0) := (V, E) (on the base set V0 := V , so P 0 (V0 ) = V ).

Then, by setting
pSHG (e, σ, τ ) := pH (e, σ, τ ) (e ∈ E, σ ∈ Ω, τ ∈ C e ),

the resulting SuperHyperGraph Coloring Game on SHG(0) has exactly the same transition matrix
(hence the same law) as the original HyperGraph Coloring Game on H.

Proof. Let H = (V, E) and SHG(0) = (V, E) be as in the statement. Because n = 0, the supervertex
set of SHG(0) is just V itself, hence both dynamics have the same state space Ω = C V . Moreover, for
any σ ∈ Ω, e ∈ E, and τ ∈ C e , the updated coloring σ e←τ is defined by the same replacement rule on
the same underlying set V . Therefore the one-step transition kernels coincide: for all σ, σ 0 ∈ Ω,

1{σ 0 = σ e←τ } pSHG (e, σ, τ ) = 1{σ 0 = σ e←τ } pH (e, σ, τ ) = PH (σ, σ 0 ).

X X X X
PSHG (σ, σ 0 ) =
e∈E τ ∈C e e∈E τ ∈C e

Hence the two Markov chains have identical transition matrices and thus the same law (for any initial
distribution on Ω).

Proposition 3.1 (Well-posedness and transition matrix). The rule pSHG in Definition 3.1 defines a
unique transition matrix P on Ω by

1{σ 0 = σ e←τ } pSHG (e, σ, τ ),

X X
P (σ, σ 0 ) := σ, σ 0 ∈ Ω,
e∈E τ ∈C e

and P is row-stochastic, i.e., P (σ, σ 0 ) = 1 for every σ ∈ Ω.

P
σ 0 ∈Ω

Proof. Fix σ ∈ Ω. For each pair (e, τ ), the updated coloring σ e←τ is a well-defined element of Ω by
construction. Hence the displayed formula defines a nonnegative number P (σ, σ 0 ) for each σ 0 ∈ Ω.
Summing over σ 0 ∈ Ω yields

1{σ 0 = σ e←τ } pSHG (e, σ, τ ) =

X X X X X X
P (σ, σ 0 ) = pSHG (e, σ, τ ) = 1,
σ 0 ∈Ω σ 0 ∈Ω e∈E τ ∈C e e∈E τ ∈C e

because for each fixed (e, τ ) there is exactly one state σ 0 = σ e←τ that activates the indicator. Thus
P is row-stochastic and defines a discrete-time Markov chain on the finite state space Ω.

7
Proposition 3.2 (Constructing hierarchy-aware interaction rules by normalization). Fix any function

(e, σ, τ ) | e ∈ E, σ ∈ Ω, τ ∈ C e → [0, ∞)

q:

such that for every σ ∈ Ω, X X

Z(σ) := q(e, σ, τ ) > 0.
e∈E τ ∈C e

Define
q(e, σ, τ )
pSHG (e, σ, τ ) := .
Z(σ)
Then pSHG satisfies the normalization condition of Definition 3.1 and therefore defines a SuperHy-
perGraph Coloring Game.

Proof. By definition pSHG (e, σ, τ ) ≥ 0. For fixed σ ∈ Ω,

X X 1 X X
pSHG (e, σ, τ ) = q(e, σ, τ ) = 1.
Z(σ)
e∈E τ ∈C e e
e∈E τ ∈C

Thus the required condition holds.

Definition 3.2 (State digraph). Given an interaction rule pSHG , define the directed graph Γ(pSHG )
on vertex set Ω by declaring an arc σ → σ 0 whenever P (σ, σ 0 ) > 0, where P is as in Proposition 3.1.

Theorem 3.2 (Irreducibility and strong connectivity). The SuperHyperGraph Coloring Game is
irreducible (as a Markov chain on Ω) if and only if the state digraph Γ(pSHG ) is strongly connected.

Proof. By definition, P (σ, σ 0 ) > 0 if and only if the chain can move from σ to σ 0 in one step with
positive probability. Therefore σ can reach σ 0 in t steps with positive probability if and only if there
exists a directed path of length t from σ to σ 0 in Γ(pSHG ). Hence the chain is irreducible (mutual
reachability for all pairs of states) if and only if Γ(pSHG ) is strongly connected.

Theorem 3.3 (A sufficient local condition for irreducibility). Assume that E covers V (i.e., e∈E e =
S

V ) and that the interaction rule satisfies the following single-supervertex recoloring property:
for every state σ ∈ Ω, every supervertex v ∈ V , and every target color c ∈ C, there exists a superhy-
peredge e ∈ E with v ∈ e and a pattern τ ∈ C e such that

τ (v) = c, τ (u) = σ(u) (u ∈ e \ {v}), and pSHG (e, σ, τ ) > 0.

Then the SuperHyperGraph Coloring Game is irreducible on Ω.

Proof. Fix σ, σ 0 ∈ Ω. List the supervertices as V = {v1 , . . . , vm }. We construct a positive-probability

path from σ to σ 0 by recoloring one supervertex at a time.
Let σ (0) := σ. For i = 1, . . . , m, apply the single-supervertex recoloring property to the current
state σ (i−1) , the supervertex vi , and the target color c := σ 0 (vi ). This yields some ei 3 vi and τi ∈ C ei
such that τi (vi ) = σ 0 (vi ), τi agrees with σ (i−1) on ei \ {vi }, and pSHG (ei , σ (i−1) , τi ) > 0. Define

ei ←τi
σ (i) := σ (i−1) . By construction, σ (i) (vi ) = σ 0 (vi ), and previously fixed colors σ (i) (vj ) = σ 0 (vj )
for j < i are unchanged because τi agrees with σ (i−1) on ei \ {vi }.
After m steps we obtain σ (m) = σ 0 and each step has positive probability, hence σ reaches σ 0 .
Since σ, σ 0 were arbitrary, the chain is irreducible.

Theorem 3.4 (Existence and uniqueness of a stationary distribution). The SuperHyperGraph Col-
oring Game admits at least one stationary distribution π on Ω (i.e., πP = π). If, moreover, the chain
is irreducible, then the stationary distribution is unique and satisfies π(σ) > 0 for all σ ∈ Ω.

8
Proof. Since Ω is finite, P is a finite row-stochastic matrix (Proposition 3.1). Consider the simplex
n X o
∆ := π ∈ RΩ π(σ) ≥ 0 ∀σ, π(σ) = 1 .
σ∈Ω

The map T : ∆ → ∆ given by T (π) = πP is continuous and maps the compact convex set ∆ into itself,
so T has a fixed point π (e.g., by Brouwer’s fixed-point theorem). This fixed point is a stationary
distribution.
If the chain is irreducible, standard Perron–Frobenius theory for nonnegative matrices implies
that the eigenvalue 1 of P is simple and the corresponding left eigenvector in ∆ is unique and strictly
positive on all states, giving uniqueness and π(σ) > 0 for all σ ∈ Ω.

Theorem 3.5 (Aperiodicity via laziness). Suppose there exists ε > 0 such that for every σ ∈ Ω,

P (σ, σ) ≥ ε.

Then the SuperHyperGraph Coloring Game is aperiodic. In particular, if it is also irreducible, then
it is ergodic and Σt converges in distribution to the unique stationary law.

Proof. If P (σ, σ) > 0 then σ can return to itself in one step, so the period of σ equals 1. If the chain
is irreducible, all states share the same period; hence the period is 1 for every state, i.e., the chain is
aperiodic. The final convergence claim is the standard ergodic theorem for finite irreducible aperiodic
Markov chains.

4. SuperHyperGraph Domination Game

We next lift domination games to the SuperHyperGraph setting. Here the hierarchical modeling
advantage is especially transparent: the playable objects are n-supervertices, i.e., set-valued aggregates
(groups, groups of groups, …), and a single move selects an aggregate that can dominate other
aggregates through shared membership in a common interaction group (a superhyperedge). Thus the
game provides a principled way to model strategic influence, monitoring, or coverage in multi-layer
systems: one may place “resources” on higher-level modules while the induced dominance propagates
across higher-level interaction groups. Importantly, the combinatorial rules remain well-posed for all
n, while the hierarchical semantics enter through the nature of the supervertices themselves.

Definition 4.1 (SuperHyperGraph domination game). Let SHG(n) = (V, E) be an n-SuperHyperGraph

(Definition 2.5). Two distinct supervertices x, y ∈ V are said to be adjacent (in SHG(n) ) if there exists
a superhyperedge e ∈ E such that {x, y} ⊆ e. For v ∈ V , define the open and closed neighborhoods by

NSHG (v) := { u ∈ V \ {v} | u is adjacent to v }, NSHG [v] := NSHG (v) ∪ {v}.

For S ⊆ V , define the dominated set by

DomSHG (S) :=
[
NSHG [v] ⊆ V.
v∈S

The SuperHyperGraph Domination Game on SHG(n) is the two-player game between Dominator
and Staller in which they alternately select supervertices

v1 , v2 , · · · ∈ V, Si := {v1 , . . . , vi }.

A move vi is legal if it newly dominates at least one previously undominated supervertex, i.e.,

DomSHG (Si ) ) DomSHG (Si−1 ) ⇐⇒ NSHG [vi ] \ DomSHG (Si−1 ) 6= ∅.

9
The game ends after k moves if DomSHG (Sk ) = V . Dominator aims to minimize k, whereas Staller
aims to maximize k.
If Dominator starts and both players play optimally, the resulting length is denoted by γg (SHG(n) )
and called the game domination number of SHG(n) . If Staller starts, the optimal length is denoted
by γg0 (SHG(n) ).

Remark 4.1 (Hierarchy-aware interpretations and variants). When n ≥ 1, each supervertex v ∈

V ⊆ P n (V0 ) encodes a multi-level aggregate. Thus selecting v can be interpreted as placing a resource
at the aggregate level (e.g., selecting a module, a team-of-teams, or a subsystem), and adjacency
via superhyperedges models higher-level coupling among aggregates. The rules above deliberately keep
domination purely combinatorial on (V, E), ensuring that the game is well-defined for every n.
If one wishes to make the hierarchy operationally explicit, one may refine adjacency or dominance
using structural features of set-valued supervertices (e.g., overlaps of their flattened constituents).
Such hierarchy-aware variants can be obtained by replacing the adjacency predicate with an alternative
that depends on the underlying set-structure, while keeping the legality and termination conditions
unchanged.

Theorem 4.1 (SuperHyperGraph domination games generalize hypergraph domination games). Ev-
ery HyperGraph Domination Game is a special case of a SuperHyperGraph Domination Game. More
precisely, let H = (V, E) be a finite hypergraph, and consider it as the 0-SuperHyperGraph

SHG(0) := (V, E) (on the base set V0 := V , so P 0 (V0 ) = V ).

Then:

(i) adjacency in SHG(0) coincides with adjacency in H;

(ii) for every S ⊆ V , one has DomSHG (S) = DomH (S);

(iii) a move sequence is legal in the SuperHyperGraph Domination Game on SHG(0) if and only if it
is legal in the HyperGraph Domination Game on H; and consequently

γg (SHG(0) ) = γg (H), γg0 (SHG(0) ) = γg0 (H).

Proof. Since n = 0, the supervertex domain of SHG(0) is the same set V , and the superhyperedge
family is the same E. For distinct x, y ∈ V , the definition of adjacency in SHG(0) asserts that x and
y are adjacent iff there exists e ∈ E with {x, y} ⊆ e, which is exactly the standard adjacency relation
for the hypergraph H. Hence NSHG (v) = NH (v) and therefore NSHG [v] = NH [v] for all v ∈ V .
Taking unions over v ∈ S yields

DomSHG (S) = NH [v] = DomH (S)

[ [
NSHG [v] =
v∈S v∈S

for all S ⊆ V . Thus, for any position Si−1 and candidate move vi , the legality condition NSHG [vi ] \
DomSHG (Si−1 ) 6= ∅ holds iff NH [vi ] \ DomH (Si−1 ) 6= ∅ holds, so the sets of legal moves coincide.
The termination condition Dom(·) = V also coincides. Therefore both games have identical game
trees and hence identical optimal lengths for each starting player, proving the equalities of the game
domination parameters.

Proposition 4.1 (Monotonicity of dominated sets). For any S ⊆ T ⊆ V one has

DomSHG (S) ⊆ DomSHG (T ).

In particular, along any play Si = {v1 , . . . , vi }, the dominated sets form a monotone chain

DomSHG (S0 ) ⊆ DomSHG (S1 ) ⊆ · · · ⊆ V.

10
Proof. If S ⊆ T , then {NSHG [v] | v ∈ S} ⊆ {NSHG [v] | v ∈ T }. Taking unions yields

DomSHG (S) = NSHG [v] = DomSHG (T ).

[ [
NSHG [v] ⊆
v∈S v∈T

The chain claim follows by applying this with Si−1 ⊆ Si .

Proposition 4.2 (Legality is equivalent to covering a new vertex). Let S ⊆ V and v ∈ V . Then v
is a legal move after the position S if and only if

NSHG [v] 6⊆ DomSHG (S) ⇐⇒ / DomSHG (S).

∃u ∈ NSHG [v] with u ∈

Proof. By Definition 4.1, v is legal after S precisely when

DomSHG (S ∪ {v}) ) DomSHG (S).

Using DomSHG (S ∪ {v}) = DomSHG (S) ∪ NSHG [v], strict containment holds if and only if NSHG [v] \
DomSHG (S) 6= ∅, which is equivalent to the displayed condition.

Theorem 4.2 (Termination and trivial bounds). Every play of the SuperHyperGraph Domination
Game terminates after at most |V | moves. In particular,

1 ≤ γg (SHG(n) ) ≤ |V |, 1 ≤ γg0 (SHG(n) ) ≤ |V |.

Moreover, if SHG(n) has an isolated supervertex (i.e., some v ∈ V with NSHG (v) = ∅), then every
legal play must include v at some point.

Proof. By Proposition 4.2, each legal move increases the dominated set by at least one previously
undominated supervertex. Since V is finite, after at most |V | moves all supervertices are dominated,
so the game terminates. This yields the upper bounds γg , γg0 ≤ |V | and the lower bounds γg , γg0 ≥ 1
are immediate.
If v is isolated, then NSHG [v] = {v}. Thus v can be dominated only by selecting v itself; no other
move can add v to the dominated set. Hence any terminating legal play must include v.

Definition 4.2 (Dominating number of a SuperHyperGraph). A set S ⊆ V is a dominating set if

DomSHG (S) = V . The minimum size of a dominating set is denoted by γ(SHG(n) ) and is called the
domination number of SHG(n) .

Theorem 4.3 (Game domination vs. domination number). For every n-SuperHyperGraph SHG(n) =
(V, E),

γ(SHG(n) ) ≤ γg (SHG(n) ) ≤ 2 γ(SHG(n) ) − 1, γ(SHG(n) ) ≤ γg0 (SHG(n) ) ≤ 2 γ(SHG(n) ).

Proof. The lower bounds γ ≤ γg and γ ≤ γg0 hold because the set of vertices selected in any ter-
minating play is a dominating set: if the game ends at k moves, then DomSHG (Sk ) = V , so Sk is
dominating and |Sk | = k ≥ γ.
For the upper bounds, fix a minimum dominating set D ⊆ V with |D| = γ. Consider the
Dominator-start game. Dominator follows the strategy: whenever possible, choose a vertex in D that
is still undominated (or, more generally, that newly dominates at least one vertex not yet dominated).
Such a choice is always legal unless the game is already over. Each Dominator move can be charged
to (at least) one previously unused element of D, so Dominator makes at most γ moves.
Between two consecutive Dominator moves, Staller makes at most one move. Therefore the total
number of moves satisfies
γg (SHG(n) ) ≤ 2γ − 1.
If Staller starts, the same reasoning gives at most γ Dominator moves and at most γ Staller moves,
hence γg0 (SHG(n) ) ≤ 2γ.

11
Theorem 4.4 (Universal vertices yield immediate bounds). Suppose there exists a supervertex u ∈ V
such that NSHG [u] = V (i.e., u dominates all supervertices). Then

γ(SHG(n) ) = 1, γg (SHG(n) ) = 1, γg0 (SHG(n) ) ∈ {1, 2}.

More precisely, γg0 (SHG(n) ) = 1 if Staller starts by playing u, and otherwise γg0 (SHG(n) ) = 2.

Proof. Since NSHG [u] = V , the singleton {u} is a dominating set, so γ = 1. If Dominator starts,
playing u is legal and immediately dominates all of V , so the game ends in one move and γg = 1. If
Staller starts, then playing u ends the game in one move; otherwise the position after Staller’s first
move still allows Dominator to play u, which ends the game on the second move. Hence γg0 ∈ {1, 2}
with the stated refinement.

5. Conclusion

In this paper, we introduced two further generalizations within the powerset-based SuperHyperGraph
framework. First, we defined the SuperHyperGraph Coloring Game as a natural extension of the
HyperGraph Coloring Game. Second, we defined the SuperHyperGraph Domination Game as an
extension of the HyperGraph Domination Game. In future work, we hope to pursue quantitative
investigations via computational experiments, to develop efficient algorithms for these games, and to
explore uncertainty-aware extensions based on Fuzzy Graphs [23, 24], Neutrosophic Graphs [25, 26],
and Plithogenic Graphs [27].

Funding

This study was conducted without any financial support from external organizations or grants.

Acknowledgments

We would like to express our sincere gratitude to everyone who provided valuable insights, support,
and encouragement throughout this research. We also extend our thanks to the readers for their
interest and to the authors of the referenced works, whose scholarly contributions have greatly influ-
enced this study. Lastly, we are deeply grateful to the publishers and reviewers who facilitated the
dissemination of this work.

References
[1] Yue Gao, Zizhao Zhang, Haojie Lin, Xibin Zhao, Shaoyi Du, and Changqing Zou. Hypergraph learning: Methods
and practices. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(5):2548–2566, 2020.
[2] Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings
of the AAAI conference on artificial intelligence, volume 33, pages 3558–3565, 2019.
[3] Florentin Smarandache. Extension of HyperGraph to n-SuperHyperGraph and to Plithogenic n-SuperHyperGraph,
and Extension of HyperAlgebra to n-ary (Classical-/Neutro-/Anti-) HyperAlgebra. Infinite Study, 2020.
[4] Takaaki Fujita and Florentin Smarandache. HyperGraph and SuperHyperGraph Theory with Applications (III): In-
tersection Graph and Graph Labeling, volume III of HyperGraph and SuperHyperGraph Theory with Applications.
Neutrosophic Science International Association (NSIA) Publishing House, 2026.
[5] Takaaki Fujita and Florentin Smarandache. HyperGraph and SuperHyperGraph Theory with Applications (IV):
Uncertain Graph Theory, volume IV of HyperGraph and SuperHyperGraph Theory with Applications. Neutrosophic
Science International Association (NSIA) Publishing House, 1.0 edition, 2026.
[6] Berrocal Villegas Salomón Marcos, Montalvo Fritas Willner, Berrocal Villegas Carmen Rosa, Flores Fuentes
Rivera María Yissel, Espejo Rivera Roberto, Laura Daysi Bautista Puma, and Dante Manuel Macazana Fernández.
Using plithogenic n-superhypergraphs to assess the degree of relationship between information skills and digital
competencies. Neutrosophic Sets and Systems, 84:513–524, 2025.
[7] Nelly Hodelín Amable, Elizabeth Esther Vergel De Salazar, Martha Gloria Martínez Isaac, Olivia Catalina Olavar-
ría Sánchez, and Johanna Mariuxi Solís Palma. Representation of motivational dynamics in school environments
through plithogenic n-superhypergraphs with family participation. Neutrosophic Sets and Systems, 92:570–583,
2025.
[8] Stefan Felsner and William T Trotter. Dimension, graph and hypergraph coloring. Order, 17(2):167–177, 2000.

12
 [9] Irit Dinur*, Oded Regev, and Clifford Smyth. The hardness of 3-uniform hypergraph coloring. Combinatorica,
25(5):519–535, 2005.
[10] Venkatesan Guruswami, Johan Hastad, and Madhu Sudan. Hardness of approximate hypergraph coloring. SIAM
Journal on Computing, 31(6):1663–1686, 2002.
[11] Takaaki Fujita and Florentin Smarandache. HyperGraph and SuperHyperGraph Theory with Applications. Neu-
trosophic Science International Association (NSIA) Publishing House, 2026.
[12] Hal A Kierstead. Asymmetric graph coloring games. Journal of Graph Theory, 48(3):169–185, 2005.
[13] Eurinardo Costa, Victor Lage Pessoa, Rudini Sampaio, and Ronan Soares. Pspace-completeness of two graph
coloring games. Theoretical Computer Science, 824:36–45, 2020.
[14] Fan Chung and Alexander Tsiatas. Hypergraph coloring games and voter models. In International Workshop on
Algorithms and Models for the Web-Graph, pages 1–16. Springer, 2012.
[15] Boštjan Brešar, Sandi Klavžar, and Douglas F Rall. Domination game and an imagination strategy. SIAM Journal
on Discrete Mathematics, 24(3):979–991, 2010.
[16] Noga Alon, József Balogh, Béla Bollobás, and Tamás Szabó. Game domination number. Discrete mathematics,
256(1-2):23–33, 2002.
[17] Csilla Bujtás. On the game domination number of graphs with given minimum degree. arXiv preprint
arXiv:1406.7372, 2014.
[18] Thomas Jech. Set theory: The third millennium edition, revised and expanded. Springer, 2003.
[19] Alain Bretto. Hypergraph theory. An introduction. Mathematical Engineering. Cham: Springer, 1, 2013.
[20] Claude Berge. Hypergraphs: combinatorics of finite sets, volume 45. Elsevier, 1984.
[21] Florentin Smarandache. Foundation of superhyperstructure & neutrosophic superhyperstructure. Neutrosophic
Sets and Systems, 63(1):21, 2024.
[22] Florentin Smarandache. Introduction to the n-SuperHyperGraph-the most general form of graph today. Infinite
Study, 2022.
[23] Azriel Rosenfeld. Fuzzy graphs. In Fuzzy sets and their applications to cognitive and decision processes, pages
77–95. Elsevier, 1975.
[24] John N Mordeson and Premchand S Nair. Fuzzy graphs and fuzzy hypergraphs, volume 46. Physica, 2012.
[25] Said Broumi, Mohamed Talea, Assia Bakali, and Florentin Smarandache. Single valued neutrosophic graphs.
Journal of New theory, (10):86–101, 2016.
[26] Said Broumi, Mohamed Talea, Assia Bakali, and Florentin Smarandache. Interval valued neutrosophic graphs.
Critical Review, XII, 2016:5–33, 2016.
[27] Fazeelat Sultana, Muhammad Gulistan, Mumtaz Ali, Naveed Yaqoob, Muhammad Khan, Tabasam Rashid, and
Tauseef Ahmed. A study of plithogenic graphs: applications in spreading coronavirus disease (covid-19) globally.
Journal of ambient intelligence and humanized computing, 14(10):13139–13159, 2023.

13