{'fraction_non_alphanumeric': 0.04951741502308015, 'fraction_numerical': 0.015145156983176287, 'mean_word_length': 4.023186739484526, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Survey on Hypergraph Products (Erratum)

A surprising diversity of different products of hypergraphs have been discussed in the literature. Most of the hypergraph products can be viewed as generalizations of one of the four standard graph products. The most widely studied variant, the so-called square product, does not have this property, however. Here we survey the literature on hypergraph products with an emphasis on comparing the alternative generalizations of graph products and the relationships among them. In this context the so-called 2-sections and L2-sections are considered. These constructions are closely linked to related colored graph structures that seem to be a useful tool for the prime factor decompositions w.r.t.\ specific hypergraph products. We summarize the current knowledge on the propagation of hypergraph invariants under the different hypergraph multiplications. While the overwhelming majority of the material concerns finite (undirected) hypergraphs, the survey also covers a summary of the few results on products of infinite and directed hypergraphs.


Part 1. Introduction
There are only four "standard graph products" that preserve the salient structure of their factors and behave in an algebraically reasonable way. Their structural This work was supported in part by the Deutsche Forschungsgemeinschaft (DFG) Project STA850/11-1 within the EUROCORES Programme EuroGIGA (project GReGAS) of the European Science Foundation.
features have been studied extensively over the last decades. It is well known how many of the important graph invariants propagate under product formation, and efficient algorithms have been devised to decompose graph products into their prime factors. Several monographs cover the topic in substantial detail and serve as standard references [40,41,31].
In contrast, very little is known about product structures of hypergraphs, even though hypergraphs have become increasingly important models of network structures. Here we survey the existing literature, focusing on the basic properties of the various hypergraph products and their mutual relationships. In this introductory part we will first investigate in which sense the standard graph products have distinguished properties. After introducing the necessary notation, and defining the most interesting hypergraph invariants we proceed to discuss a set of desirable properties of hypergraph products that generalize the situation in graphs. Much of the published literature is concerned with the so-called square product, which does not arise as a natural generalization of a graph product. Most of the other constructions, albeit less well investigated so far, can be described as generalizations of a corresponding graph product. The link between hypergraph products is also stressed by constructions such as 2-sections and L2-sections [6,10]. We therefore choose to emphasize the generalizations of graph products in our survey. The following sections are then concerned with a review of the literature on the individual notions of hypergraph products. The literature is complemented by several new results that bridge some of the obvious gaps in particular for the rarely studied products. Our survey also includes a complementary recursive exposition of several new constructions and their basic properties [36].

Graph Products
Graph products are natural structures in discrete mathematics [30,50] that arise in a variety of different contexts, from computer science [3,33,34] and computational engineering [45,46] to theoretical biology [21,22,12,60,62]. In this section we briefly outline the commonly investigated graph products and their most salient properties to provide a frame of reference for our subsequent discussion of hypergraph products.
We consider only finite and undirected graphs G = (V, E) with non-empty vertex set V and edge set E. A graph is non-trivial if it has at least two vertices. Graph products can be constructed in many different ways. For example, different constructions arise depending on whether loops are considered or not. There are, however, three basic properties that are required for any meaningful definition of a graph product: (P1) The vertex set of a product is the Cartesian product of the vertex sets of the factors. (P2) Adjacency in the product depends on the adjacency properties of the projections of pairs of vertices into the factors.
(P3) The product of a simple graph is a simple graph.
As shown in [39], there are 256 different possibilities to define a graph product satisfying (P1), (P2), and (P3). Only six of them are commutative, associative and have a unit. Only four products satisfy the following additional condition: (P4) At least one of the projections of a product onto its factors is a so-called weak homomorphism (edges are mapped to edges or to vertices).
These four products are known as the standard graph products [40,31]: the Cartesian product ✷, the direct product ×, the strong product ⊠, and the lexicographic product •.
In the Cartesian product vertices are adjacent if and only if they satisfy (i) or (ii). Consequently, the edges of a strong product that satisfy (i) or (ii) are called Cartesian edge, the others are the non-Cartesian edges. In the direct product vertices are only adjacent if they satisfy (iii). Thus, the edge set of the strong product is the union of edges in the Cartesian and the direct product. In the lexicographic product vertices are adjacent if and only if (x 1 , y 1 ) ∈ E(G 1 ) or they satisfy (ii).
Three of these products, the Cartesian, the direct and the strong product are commutative, associative, and distributive with respect to the disjoint union. The lexicographic product is associative, not commutative, and only left-distributive with respect to the disjoint union. All products have a unit element, that is the single vertex graph K 1 for the Cartesian, the strong and the lexicographic product, and the single vertex graph with a loop LK 1 for the direct product.
Connectedness of the products depends on the connectedness of the factors. The Cartesian and the strong product is connected if and only if all of its factors are connected. The direct product of non-trivial connected factors is connected if and only if at most one factor is bipartite. The lexicographic product • n i=1 G i is connected if and only if G 1 is connected. The costrong product G 1 * G 2 , with edge set E(G 1 • G 2 ) ∪ E(G 2 • G 1 ), can be seen as a symmetrized version of the lexicographic product. It is also closely related to the strong produce by virtue of the identity G 1 * G 2 = G 1 ⊠ G 2 [25].
Connected graphs have a unique Prime Factor Decomposition (PFD) w.r.t. the strong and the Cartesian product and connected non-bipartite graphs have a unique PFD w.r.t. the direct product. The PFD w.r.t. the lexicographic product is unique only under strict conditions w.r.t. connectivity properties based on the prime factors [31].

Hypergraphs
path partition number and will be denoted by ℘(H). Note, the path partion number satisfies ℘(H) ≤ |V (H)|, since there is always a partition of a hypergraph into paths of length 0. A cycle is a sequence (v 0 , e 1 , v 1 , e 2 , . . . , v k−1 , e k , v 0 ), such that P v0,v k−1 is a path. A p-path or a cycle is Hamiltonian in H if it contains all vertices of H. The length of a path or a cycle is the number of edges contained in the path or cycle, resp.
The distance d H (v, v ′ ) between two vertices v 0 , v k of H is the length of a shortest path joining them. We set d H (v, v ′ ) = ∞ if there is no such path. A hypergraph H = (V, E) is called connected, if any two vertices are joined by a path. A partial hypergraph H ′ ⊆ H is called convex, if all shortest paths in H between two vertices in H ′ are also contained in H ′ .

Homomorphisms and Covering Constructions
For two hypergraphs H 1 = (V 1 , E 1 ) and H 2 = (V 2 , E 2 ) a homomorphism from H 1 into H 2 is a mapping ϕ : homomorphism if edges are mapped either on edges or on vertices.
A homomorphism ϕ that is bijective is called an isomorphism if holds ϕ(e) ∈ E 2 if and only if e ∈ E 1 . We say, H 1 and H 2 are isomorphic, in symbols H 1 ∼ = H 2 if there exists an isomorphism between them. An isomorphism from a hypergraph H onto itself is an automorphism.
The hypergraph H is then called the quotient hypergraph of H ′ and π is called the covering projection [17]. If k = 2, H ′ is called double cover [16].

L2-sections
The notion of so-called L2-sections has proved to be an extremely useful tool for hypergraph product recognition algorithms. In the following we therefore consider the 2-section and L2-section of hypergraphs [6,10] in some detail. In the context of 2-sections and L2-sections we will consider only hypergraphs without loops throughout this survey.
Let P(X) denotes the power set of the set X. The L2-section [H] L2 of a hypergraph H = (V, E) is its 2-section together with a mapping L : . In addition to 2-sections, the L2-section also provides the possibility to trace back the information which of the edges of [H] 2 is associated to which of the hyperedges in H. Thus, the original hypergraph can be reconstructed from its L2-section. The inverse for all x, y ∈ V 1 and e ⊆ V 1 . Every hypergraph is uniquely (up to isomorphism) determined by its L2-section and vice versa [11,10]

Invariants
In the following paragraphs we briefly introduce the hypergraph invariants that are most commonly studied in the context of hypergraph products. We will assume throughout that H = (V, E) is a given hypergraph.
2.4.1. Independence, Matching and Cover. A set S ⊆ V is independent if it contains no edge of E; the maximum cardinality of an independent set is denoted by β(H) and is called the independence number of H. Some of the older literature, e.g. [7,61] use the term stable and stability number for this concept.
A set T ⊆ V is called a cover of H if it intersects every edge of H, i.e., T ∩ e = ∅ for all e ∈ E. The minimum cardinality of the covers is denoted by τ (H), and called the covering number of H. Cover and covering number are also known as transversal or transversal number [7].
A fractional cover of H is a mapping t : V → R + 0 such that v∈e t(v) ≥ 1 for all e ∈ E. The value min t v∈V t(v) over all fractional covers t is called fractional covering number and denoted by τ * (H). Note that every cover induces a fractional cover by defining t(v) = 1 if v ∈ T and t(v) = 0 else [6].
A subset M ⊆ E is a matching if every pair of edges from M has an empty intersection. The maximum cardinality of a matching M is called the matching number, denoted by ν(H) [6].
The partition number ρ(H) of H denotes the minimal number of pairwise disjoint edges of E which together cover V if such a partition exists, else we set ρ(H) = ∞ [2, 1].

Coloring.
A coloring of a hypergraph H is mapping c from either V or E into a set of colors C = {1, . . . , k}. We refer to c : E → C as an edge-coloring and to c : V → C as a vertex-coloring or simply coloring.
A proper coloring of a hypergraph H is a coloring c : V → C such that {v | c(v) = i} is an independent set for all i ∈ C. The chromatic number χ(H) is the minimal number of colors that admit a proper coloring of H. Hence, the chromatic number χ(H) is the minimum number of independent sets V 1 , · · · , V χ(H) into which V can be partitioned. A proper strong coloring of a hypergraph H is a proper coloring such that for all edges e ∈ E holds that c(v) = c(w) for all distinct vertices v, w ∈ e. The strong chromatic number χ s (H) is the minimal number k of colors that admit a strong k-coloring of H.
The (k-color) discrepancy of a hypergraph measures the deviation of a coloring c from a so-called balanced coloring, that is a coloring in which each hyperedge contains same number of vertices of each color. More formally, the discrepancy of a coloring c and the k-color discrepancy of H = (V, E) are defined as follows: A proper edge-coloring of a hypergraph H is a coloring c : E → C such that c(e) = c(f ) for all distinct incident edges e, f ∈ E. The chromatic index q(H) of H is the minimum number of colors that admit a proper edge-coloring. Clearly, q(H) ≥ ∆(H). A hypergraph has the colored hyperedge property if q(H) = ∆(H).

Helly Property.
For v ∈ V , a star H(v) of H with center v is the set of all edges e ∈ E such that v ∈ e. For a given simple hypergraph H a subset E ′ of E is an intersecting family if every pair of hyperedges of E ′ have a non-empty intersection. A hypergraph has the Helly property if each intersecting family is a star. An interesting characterization of Helly hypergraphs can be found in [5]: A hypergraph has the Helly property if and only if its dual is conformal.

Basic Properties of Hypergraph Products
Definitions of hypergraph products, to our knowledge, have never been compared systematically in a way similar to graph products. Most of the hypergraph products can be viewed as a generalization of respective graph products. However, one of the most studied hypergraph product, the so-called square product, does not provide this property. Therefore, it appears useful to make explicit the desirable properties of hypergraph products. We begin with the direct generalization of the requirements for graph products: (P1) The vertex set of a product is the Cartesian product of the vertex sets of the factors. (P2) Adjacency in the product depends only on the adjacency properties of the projections of pairs of vertices into the factors. (P3) The product of simple hypergraphs is again a simple hypergraph. (P4) At least one of the projections of a product onto its factors is a weak homomorphism.
Since graphs can be interpreted as the special hypergraphs with |e| ≤ 2 for all e ∈ E, we would like to consider hypergraph products that specialize to graph products: (P5) The hypergraph product of two graphs is again a graph.
For hypergraphs, these requirements appear to give more freedom than for graphs. Property (P2) posits that the presence of an edge (x 1 , x 2 ) ∼ (y 1 , y 2 ) must be determined by the presence or absence of the adjacencies x 1 ∼ y 1 and x 2 ∼ y 2 and a rule deciding whether x 1 = y 1 and x 2 = y 2 is to be treated like an edge or its absence, leading to 2 8 = 256 distinct operations, see [39]. For hypergraphs, however, this leads only to a restriction on edges but does not provide a complete recipe for the construction of the edge set of the product. As a consequence, it is possible to find several non-equivalent generalizations of the standard graph products as we shall see throughout this survey. As in the case of usual graph products at least associativity is desirable. All products that are treated in this survey are associative. We omit the proofs for this, since they can be done equivalently to the proofs as in [31]. Thus, the hypergraph products of finitely many factors are well defined and it suffices to prove the results for two (not necessarily prime) factors only. Furthermore, all products, except the lexicographic product are commutative.
Before we proceed with our analysis of hypergraph products, we need to introduce some specific notations: be an arbitrary hypergraph product. The projection p j : V → V (H j ) is defined by v = (v 1 , . . . , v n ) → v j . We will call v j the j-th coordinate of the vertex v ∈ V . For a given vertex w ∈ V (H) the H j -layer through w is the partial hypergraph of H . . , n we will denote this hypergraph simply by H ⊛n .
Let U denote the unit element, if one exists, of an arbitrary product ⊛, i.e., H = H ⊛ U for all hypergraphs H. Since all hypergraph products considered here have vertex set V 1 × V 2 the unit must always be a hypergraph with a single vertex. A hypergraph is said to be prime if the identity H = H 1 ⊛ H 2 implies that H 1 ∼ = U or H 2 ∼ = U . Not all hypergraph products have a unit element. Prime factors and a prime factor decomposition cannot be meaningfully defined unless there is a unit.

Definition and Basic Properties
The Cartesian product is associative, commutative, distributive with respect to the disjoint union and has the single vertex graph K 1 as a unit element [37]. The Cartesian product of two simple hypergraphs is a simple hypergraph. A Cartesian product hypergraph, furthermore, is connected if and only if all of its factors are connected [37]. For the rank and anti-rank, respectively, of a Cartesian product hypergraph H 1 ✷H 2 holds: The projections onto the factors are weak homomorphisms. According to [52] the Cartesian product of hypergraphs can be described in terms of projections as follows:  The H j -layer through w of a Cartesian product H is induced by all vertices of H that differ from w ∈ V (H) exactly in the j-th coordinate. Moreover, H w j ∼ = H j .

Relationships with Graph Products
The restriction of the Cartesian product to graphs coincides with the usual Cartesian graph product. The 2-sections of hypergraphs are also well-behaved: This observation suggested the definition of the Cartesian product of L2sections by constructing an appropriate labeling function for the product:  [11,10]).
and a labeling function Proof. Combining the results of Lemma 2.1, Lemma 4.2 and the well-known Distance Formula for the Cartesian graph product (Corollary 5.2 in [31]) yields to the result.

Prime Factor Decomposition
Theorem 4.6 (UPFD [37]). Every connected hypergraph has a unique prime factor decomposition w.r.t. the Cartesian product.
The PFD of disconnected hypergraphs is in general not unique [40,31]. Theorem 4.6 was also obtained in [49] using a different approach that generalizes this result to infinite and directed hypergraphs, see Part 7.
Imrich and Peterin devised an algorithm for computing the PFD of connected graphs (V, E) in O(|E|) time and space [42]. Bretto and Silvestre adapted this algorithm for the recognition of Cartesian products of hypergraphs [10]. To this end, the L2-sections of hypergraphs are used. We give here a short outline of this algorithm.
time, the check-and-merging-process together with the build back part for the PFD of H is more time-consuming and one ends in an overall time complexity of O((log 2 |V |) 2 ·r(H) 3 ·|E|·∆(H) 2 ) for a given hypergraph H. The PFD of connected simple hypergraphs H = (V, E) with fixed maximum degree and fixed rank can then be computed in O(|V ||E|) time [10]. The currently fastest algorithm is due to Hellmuth and Lehner [35]. In distinction from the method of Bretto et al. this algorithm is in a sense conceptually simpler, as (1) it is not needed to transform the hypergraph H into its so-called L2-section and back and (2) the test which (collections) of the putative factors are prime factors of H follows a complete new idea based on increments of fixed vertex-coordinate positions, that allows an easy and efficient check to determine the PFD of H.

Invariants
Much of the literature on Cartesian hypergraph products is concerned with relationships of invariants of the factors with those of the product. In this section we compile the most salient results. [37]). The automorphism group of the Cartesian product of connected prime hypergraphs is isomorphic to the automorphism group of the disjoint union of the factors.
Theorem 4.15 (Hamiltonicity II [53]). Let H 1 be a hypergraph with n 1 ≥ 4 vertices containing an Hamiltonian cycle and H 2 ) be a hypergraph with that contains a Hamiltonian p-path with p ≤ 2⌊n 1 /4⌋. Then H 1 ✷H 2 contains a Hamiltonian cycle.

Part 3. Direct Products
In contrast to the Cartesian product, there are several different possibilities to construct a direct product. We will consider four constructions in detail: The direct product r , which is closed under the restriction on r-uniform hypergraphs, the direct product ⌣ ×, which preserves the minimal rank of the factors, the direct product ⌢ ×, which preserves the maximal rank of the factors and the direct product ×, which does not preserve any rank of its factors.
An alternative product, which we prefer to call the square product following the work of Nešetřil and Rödl [44], is also often called "direct product" in the literature. It will be discussed in detail in section 14.

The Direct Product for r-uniform Hypergraphs
An early construction of a direct hypergraph product [20] was motivated by the investigation of a category of hypergraphs. The following product is categorical in the category of r-uniform hypergraphs and is only defined for r-uniform hypergraphs.

Definition and Basic Properties
Definition 5.1 (r-uniform direct product). For two r-uniform hypergraphs H 1 = (V 1 , E 1 ) and H 2 = (V 2 , E 2 ) their direct product H 1 r H 2 has vertex set V 1 × V 2 and the edge set This product is the restriction of minimal and maximal rank preserving products to r-uniform hypergraphs, defined in the following two sections. Most of the properties of the two products can indeed be inferred from the corresponding results for the r -product.

Relationships with Graph Products
For r = 2, r is the direct graph product in the simple graph. However, since it is only defined on r-uniform hypergraphs, it cannot be generalized on the class of graphs with loops. Since r coincides with the minimal rank preserving product ⌣ × on r-uniform hypergraphs all results concerning 2-sections and L2-sections can be inferred from the respective results of ⌣ ×. In general there is no unit element for r-uniform hypergraphs, hence the term prime cannot be defined for this product. As far as we know, nothing is known about the behavior of hypergraph invariants under this product.

The Minimal Rank Preserving Direct Product
If one considers the direct product H 1 r H 2 of two r-uniform hypergraphs H 1 and H 2 , one observes that an edge in E(H 1 r H 2 ) satisfies the following two properties: (E1) All vertices of an edge differ in each coordinate. (E2) The projection of an edge is an edge in the respective factor. If one tries to generalize the product r to arbitrary non-uniform hypergraphs, one always encounters edges in the corresponding hypergraph product that cannot satisfy both (E1) and (E2). Hence, a natural question is how to extend the direct product r to a product of two arbitrary, non-uniform hypergraphs in such a way that it satisfies at least one the properties.
If we insist on Property (E1) we enforce an additional constraint, that is, the projections of an edge of the product hypergraph into the factors is an edge in at least one factor and subsets of edges in the other factors. ¿From that point, we observe that the rank of the hypergraph product equals the minimal rank of the factors.

Definition and Basic Properties
This product was first defined by Sonntag in [57] using the term "Cartesian Product". Definition 6.1 (Minimal Rank Preserving Direct Product [57]). For two hyper- For two edges e 1 ∈ E 1 and e 2 ∈ E 2 let r − e1,e2 = min{|e 1 |, |e 2 |}. The edge set is the defined as: . , x r } is an edge in H 1 and {y 1 , . . . , y r } is the subset of an edge in H 2 , or (ii) {x 1 , . . . , x r } is the subset of an edge in H 1 and {y 1 , . . . , y r } is an edge in H 2 We have p 1 (e) = e 1 and p 2 (e) = e 2 provided |e 1 | = |e 2 |. If |e i | < |e j |, then p i (e) = e i and p j (e) ⊂ e j , i, j ∈ {1, 2}. Thus, the projections need not to be (weak) homomorphisms in general, but they preserve adjacency, i.e., two vertices in a direct product ⌣ × hypergraph are adjacent, whenever they are adjacent in both of the factors.
The direct product ⌣ × is associative, it is commutative as an immediate consequence of the symmetry of the definition. Simple set-theoretic considerations show that direct product ⌣ × is left and right distributive with respect to the disjoint union. The direct product ⌣ × of two connected hypergraphs is not necessarily connected, as one can observe for the simple case K 2 ⌣ × K 2 . For the rank and anti-rank, respectively, of the hypergraph H = H 1 ⌣ × H 2 holds: must hold and hence p 1 (e ′ ) = e ′ 1 . From this we can conclude |e| = |e 1 | = |e ′ 1 | = |p 1 (e ′ )| = |e ′ | and therefore e = e ′ .
The direct product ⌣ × does not have a unit, both in the class of simple and non-simple hypergraphs, i.e., neither the one vertex hypergraph K 1 , nor the vertex with a loop, LK 1 , is a unit for the direct product ⌣ ×.

Relationships with Graph Products
The restriction of the direct product ⌣ × to r-uniform hypergraphs is the product r defined in Equation (5.1), hence the restriction of ⌣ × simple graphs coincides with the direct graph product. But since the direct product ⌣ × has no unit, we can conclude that it does not coincide with the direct graph product in the class of graphs with loops.
× H ′′ is the direct product of the 2-section of H ′ and the 2-section of H ′′ , more formally: Proof ) and a labeling function A short direct computation shows that holds for all simple hypergraphs H, H ′ . where it is understood that d H ((x 1 , x 2 ), (y 1 , y 2 )) = ∞ if no such n exists.
Proof. Combining the results of Lemma 2.1, Lemma 6.3 and the Distance Formula for the direct graph product (Proposition 5.8 in [31]) yields to the result.
Corollary 6.6. Let (x 1 , x 2 ) and (y 1 , y 2 ) be two vertices of the direct product H = The absence of a unit implies that there is no meaningful PFD. To the authors' knowledge, hypergraphs invariants have not been studied for the product ⌣ ×.

The Maximal Rank Preserving Direct Product
As discussed in Section 6, if one tries to generalize the product r to arbitrary non-uniform hypergraphs, one always encounters edges in the corresponding hypergraph product that cannot satisfy both (E1) and (E2): (E1) All vertices of an edge differ in each coordinate. (E2) The projection of an edge is an edge in the respective factor.
In order to extend the direct product r to a product of two arbitrary, nonuniform hypergraphs in such a way that it satisfies at least one of the properties, we insist now on condition (E2) and claim that the size of an edge in the product hypergraph coincides with the size of at least one of its projections and thus, the rank of the product hypergraph is exactly the maximal rank of one of its factors.

Definition and Basic Properties Definition 7.1 (Maximal Rank Preserving Direct Product). For two hypergraphs
For two edges e 1 ∈ E 1 and e 2 ∈ E 2 let r + e1,e2 = max{|e 1 |, |e 2 |}. The edge set is the defined as: The direct product ⌢ × is associative, commutative, and distributive with respect to the disjoint union. Contrary to the direct product ⌣ ×, projections of a product hypergraph into the factors are, by definition, homomorphisms, i.e., projections of hyperedges are hyperedges in the respective factors.
The one vertex hypergraph with a loop LK 1 is a unit for the direct product ⌢ × in the class of hypergraphs with loops. In the class of simple hypergraphs, this product has no unit. The direct product ⌢ × of two connected hypergraphs is not necessarily connected, since it need not to be connected in the class of graphs. For the rank and anti-rank, respectively, of the hypergraph H 1 ⌢ × H 2 holds:

Relationships with Graph Products
If we restrict the direct product ⌢ × to r-uniform hypergraphs, we recover the product r defined by Equation (5.1). In particular, this product coincides with the direct graph product in the class of simple graphs. Moreover, the restriction of this product to graphs coincides with the direct graph product in general, also in the class of not necessarily simple graphs with loops.
In contrast to the direct product ⌣ ×, however, the 2-section of the direct product of two arbitrary hypergraphs is not the direct graph product of the 2sections of the hypergraphs, except in the special case of r-uniform hypergraphs. To see this, consider as an example the product K 2 Despite its appealing properties, the product ⌢ × has not been studied in the literature. It is unknown, in particular, under which conditions it admits a unique PFD. The prime factor theorems for the direct product need non-trivial preconditions even in the class of graphs. We do not expect that it will be a particularly simple problem to establish a general UPFD theorem.

A Direct Product that does not preserve Rank
For the sake of completeness, and as an example for the degrees of freedom inherent in the definition of hypergraph products that generalize graph products, we consider the product ×. Its restriction to 2-uniform hypergraphs coincides with the direct graph product. However, it does not preserve r-uniformity in general. For brevity we omit proofs, which can be found in [27], throughout this section.

Definition and Basic Properties
Definition 8.1 (non-rank-preserving Direct Product). For two hypergraphs H 1 = (V 1 , E 1 ) and H 2 = (V 2 , E 2 ), we define their direct product × by the edge set The projections p 1 and p 2 of a product hypergraph H = H 1 ×H 2 into its factors H 1 and H 2 , respectively, are homomorphisms.
It is not hard to verify that the direct product × is associative, commutative, and both left and right distributive together with the disjoint union as addition. The direct product H 1 ×H 2 of simple hypergraphs H 1 , H 2 is simple. The direct product × does not have a unit, neither in the class of simple hypergraphs, nor in the class of non-simple hypergraphs. The direct product × of two connected hypergraphs is not necessarily connected, as one can observe for the simple case K 2 ×K 2 . For the rank and anti-rank, respectively, of the hypergraph product H 1 ×H 2 holds: In general, therefore, the (anti-)rank of a product will not be the (anti-)rank of one of its factors.

Relationships with Graph Products
If we restrict the definition of this product to 2-uniform hypergraphs, i.e., simple graphs, we have: {x, x ′ } is an edge in G 1 and {y, y ′ } is an edge in G 2 . This is exactly the definition of the direct graph product.
Similar to the direct product ⌢ ×, the 2-section of the direct product of two arbitrary hypergraphs is not the direct graph product of the 2-sections of the hypergraphs. This can be easily verified on the product K 2 ×(V, {V }) with |V | = 3.
Since the direct product × has no unit, we can conclude that it does not coincide with the direct graph product in the class of graphs with loops. The absence of a unit implies that there is no meaningful PFD. To our knowledge, no further results are available on this product.

Part 4. Strong Products
The strong product of graphs can be interpreted as a superposition of the edges of the Cartesian and the direct graph products. Here we explore the corresponding constructions for hypergraphs: Let the edge set of a strong product H = H 1 * ⊠ H 2 , * = ⌢, ⌣ of two hypergraphs H 1 and H 2 be where E(H 1 * ×H 2 ) is the edge set of one of the respective direct products discussed in the previous section.

The Normal Product
This particular strong product was first introduced by Sonntag [54,55,58]. Following the terminology of Sonntag we call this product normal product ⌣ ⊠. An edge e that is of type (i) or (ii) is called Cartesian edge and it holds e ∈ E(H 1 ✷H 2 ), an edge e of type (iii) or (iv) is called non-Cartesian edge and it holds e ∈ E(H 1 ⌣ × H 2 ). Notice that |e ∩ e ′ | ≤ 1 holds for all e ∈ E(H 1 ✷H 2 ) and

Definition and Basic Properties
For the same reasons as for the direct product ⌣ ×, the projections need not to be (weak) homomorphisms in general, but they preserve adjacency or adjacent vertices are mapped into the same vertex. The normal product ⌣ ⊠ is associative, commutative, and distributive w.r.t the disjoint union and has K 1 as unit ele- Proof. This follows immediately from Lemma 6.2, the fact that the Cartesian product of simple hypergraphs is simple and that the intersection of a Cartesian and a non-Cartesian edge contains at most one vertex.

Relationships with Graph Products
The restriction of the normal product ⌣ ⊠ to 2-uniform hypergraphs coincides with the strong graph product. But it does not coincide with the strong graph product in the class of graphs with loops since the direct product ⌣ × does not coincide with the direct graph product within this class.
In the class of graphs there is a well known relation between the direct and the strong graph product. The strong product can be considered as a special case of the direct product [40]: for a graph G ∈ Γ let LG denote the graph in Γ 0 , which is formed from G by adding a loop to each vertex of G. On the other hand, for a graph G ′ ∈ Γ 0 let NG ′ denote the graph in Γ which emerges from G ′ by deleting all loops. Then we have for G 1 , G 2 ∈ Γ: This relationship, however, does not exist between the direct product One can therefore define a meaningful normal product of L2-sections: ) and a labeling function assigning to each edge e ′ = {(x 1 , y 1 ), (x 2 , y 2 )} ∈ E ′ a label Combining the results of Lemma 2.1, Lemma 9.2 and the well-known Distance Formula for the strong graph product (Corollary 5.5 in [31]) yields to the result.

Invariants
The normal product has not received much attention since its introduction by Sonntag [54]. In particular, it has not yet been investigated regarding PFDs.
(2) |V 1 | = 3 and H i is not isomorphic to P 3 or H j contains no Hamiltonian

The Strong Product
Given the "nice" properties of the direct product ⌢ ×, the best candidate for a standard strong product of hypergraphs is
An edge e that is of type (i) or (ii) is called Cartesian edge and it holds e ∈ E(H 1 ✷H 2 ), an edge e of type (iii) or (iv) is called non-Cartesian edge and it The strong product ⌢ ⊠ is associative, commutative, and distributive w.r.t. the disjoint union and has K 1 as unit element. The projections into the factors are weak homomorphisms. Since E(H 1 ✷H 2 ) is a spanning partial hypergraph of  Proof. Due to the fact that the Cartesian product and the direct product ⌢ × of simple hypergraphs is simple, it remains to show, that no Cartesian edge is contained in any non-Cartesian edge or vice versa. Therefore, let e be a Cartesian edge and e ′ a non-Cartesian edge with p i (e ′ ) = e ′ i for some e ′ i ∈ E i , i = 1, 2. Suppose first, e ′ ⊆ e. Thus |p i (e)| = 1 for an i ∈ {1, 2} and therefore |p i (e ′ )| = 1, but p i (e ′ ) must be an edge in H i . Hence, one of the factors would not be simple. Now let e ⊆ e ′ . W.l.o.g. suppose |p 1 (e)| = 1, hence p 2 (e) = e 2 for some e 2 ∈ E 2 . Since p 2 (e) ⊆ p 2 (e ′ ) = e ′ 2 and H 2 is simple, we can conclude e 2 = e ′ 2 . If |e ′ | = |e ′ 1 |, then p 1 (x) = p 1 (y) must hold for all x, y ∈ e ′ with x = y ′ , and therefore |e| = 1 and hence |e 2 | = 1, which contradicts the fact that H 2 is simple. If conversely |e ′ | = |e ′ 2 |, we can conclude that |e ′ | = |e|, hence e = e ′ and |e ′ 1 | = |p 1 (e ′ )| = 1 which implies that H 1 is not simple, a contradiction.

Relationships with Graph Products
The restriction of the strong product ⌢ ⊠ to (not necessarily simple) graphs (with or without loops) coincides with the strong graph product. For simple hypergraphs H 1 and H 2 without loops, furthermore, we have Thus, the strong product can be considered as a special case of the direct product, generalizing the well-known results about the direct and strong graph product, see Equ.(9.1).
In contrast to the direct product Proof
Although ⌢ ⊠ appears to be the most promising strong product of hypergraphs, it has not been investigated in any detail so far.

Alternative Constructions Generalizing the Strong Graph Product
In order to generalize the strong graph product one can draw on an abundance of ways to define strong hypergraph products. To complete this part, we suggest a few of possibilities that have not been considered in the literature so far but might warrant further attention.

The Lexicographic Product
The lexicographic product is the only non-commutative product treated in this survey. The lexicographic product of hypergraphs has received considerable attention in the literature [56,58,26,19,29,28,8,16].

Definition and Basic Properties
Definition 12.1 (The Lexicographic Product [19]). Let H 1 = (V 1 , E 1 ) and H 2 = (V 2 , E 2 ) be two hypergraphs. The lexicographic product H = H 1 • H 2 has vertex set V (H) = V 1 × V 2 and edge set Since |p 1 (e)| = |e| there are |e| vertices of e that have pairwise different first coordinates. A related construction was also explored in [19]: Definition 12.2 (X-join of hypergraphs). Let X = (V (X), E(X)) be a hypergraph and let {H(x) | x ∈ V (X)} be a set of arbitrary pairwise disjoint hypergraphs, each of them associated with a vertex x ∈ V (X). The X-join of (H(x)) and e ∈ E(Z) ⇔e ∈ E(H(x)), or If X ∼ = K 2 , then Z is also called join of H 1 and H 2 , Z = H 1 ⊕ H 2 . The X-join is a generalization of the lexicographic product in the following sense: If Z is an The lexicographic product of two simple hypergraphs is simple. It is associative, has the single vertex graph K 1 as a unit element, and is right-distributive with respect to the join and the disjoint union of hypergraphs. Additionally, we have the following left-distributive properties w.r.t. join and disjoint union: for all hypergraphs H 1 , H 2 [19,26]. The lexicographic product is not commutative in general.

Relationships with Graph Products
The restriction of the lexicographic product on graphs coincides with the usual lexicographic graph product.
and a labeling function Proof. Combining the results of Lemma 2.1, Lemma 12.4 and the Distance Formula for the lexicographic graph product (Proposition 5.12 in [31]) yields to the result.

Prime Factor Decomposition
Similar conditions as for graphs are known for the uniqueness of the PFD of a hypergraph w.r.t. the lexicographic product: Lemma 12.7 ([26]). Let H be a hypergraph without isolated vertices and m, n natural numbers. Then K n • H + K m is prime with respect to the lexicographic product if and only if H • K n + K m is prime.
If H has no trivial join-components, then K n • H ⊕ K m is prime with respect to the lexicographic product if and only if H • K n ⊕ K m is prime.
Let H = P • K q be a PFD of H with P = K q • A + K m such that A has no non-trivial components. Then H = K q • R with R = A • K q + K m is also a PFD of H that arises by transposition of K q from H = P • K q . The transposition of K q is defined analoguously.  If there is a prime factorization of H without complete or totally disconnected graphs as factors, then H has a unique prime factor decomposition.
If there is a prime factorization of H in which only complete graphs as factors have trivial join-components and only totally disconnected factors have trivial components, then H has a unique prime factor decomposition.

Invariants
Definition 12.10 (Wreath Product of Automorphism Groups [19,26]). Let H = (V, E) and H ′ (V ′ , E ′ ) be hypergraphs. The wreath product of their automorphism groups is defined as The elements of Aut(H) • Aut(H ′ ) map H ′ -layer onto H ′ -layer and are therefore often called natural automorphisms. In [19] and [29] it is shown, under which conditions holds Aut(H) • Aut(H ′ ) = Aut(H • H ′ ). [16]). If the hypergraphs H 1 , H 2 are double cover hypergraphs then so is their lexicographic product H 1 • H 2 .

Theorem 12.11 (Double Covers
Theorem 12.13 (Hamiltonicity II [56]). Let H 1 = (V 1 , E 1 ) and H 2 = (V 2 , E 2 ) be two non-trivial hypergraphs. Then their lexicographic product H 1 • H 2 contains a Hamiltonian cycle if and only if there exists a walk . . , k}} = |V 2 | implies that v 0 = v k and there is an edge e in E 1 containing both v 0 and v k .

Definition and Basic Properties
Since the lexicographic product is not commutative, it appears natural to consider "symmetrized" variants of the lexicographic product. The costrong product H 1 * H 2 [26] has the edge set The costrong product is associative, commutative and has K 1 as unit [26]. The costrong product of two simple hypergraphs is not simple, unless both factors are r-uniform. The projections into the factors are neither (weak) homomorphisms nor preserve adjacency. Rank and anti-rank of the costrong hypergraph product Theorem 13.1 (UPFD [26]). Every finite coconnected hypergraph has a unique PFD w.r.t. the costrong product.
In [59] it is shown under which (quite complex) conditions the costrong product is Hamiltonian. Automorphism groups of costrong products have been considered by Gaszt and Imrich, [26].

Relationships with Graph Products
The restriction of the costrong product to graphs coincides with the respective costrong graph product. The costrong product of graphs can be obtained from the strong product by virtue of the identity G 1 * G 2 = G 1 ⊠ G 2 . This construction is not applicable to hypergraphs because no suitable definition of complements of hypergraphs has been proposed so far [25,26].
The L2-section of costrong products can be derived in a straightforward way from the definition of the L2-section of the lexicographic product. We omit an explicitly description here.

Part 6. Other Hypergraph Products
The hypergraph products discussed so far reduce to graph products at least in the class of simple graphs. In this part of the survey we summarize alternative constructions that have received considerable attention but do not correspond to graph products.

The Square Product
The literature is by no means consistent in its use of the terms "square product" and "direct product". In particular, many authors use the term for "direct product" for the square product, see e.g. [7,48,51,14,13,1,61,2,9,17,23,44,18]. We favor the term "square product" introduced by Nešetřil and Rödl [44], since it does not reduce to the direct product on graphs. To add to the confusion, some authors also used the term "strong product", see e.g. [9]. The square product seems to be the most widely studied of the hypergraph products.
The square product is associative, commutative, distributive w.r.t. the disjoint union and has the single vertex graph with loop LK 1 as unit element. The square product of two hypergraphs is connected if and only if both of its factors are connected, and it is a uniform hypergraph if an only if both of the factors are uniform hypergraphs. The square product of two simple hypergraphs is a simple hypergraph. The projections into the factors are homomorphisms [18]. For the rank and anti-rank, respectively, of the square product holds: Proposition 14.2 ( [7]). The dual hypergraph of a square product of two hypergraphs H 1 and H 1 is the square product of the dual hypergraphs of H 1 and H 2 . More formal: (

Relationships with Graph Products
The square product of two graphs is not a graph, but a 4-uniform hypergraph. Nevertheless, its 2-section has the structure of a graph product.
Note, in contrast to the other proofs we do not need the condition that p i (x) = p i (y), i = 1, 2. However, since x = y we can conclude that Combining the results of Lemma 2.1, Lemma 14.3 and the well-known Distance Formula for the strong graph product (Corollary 5.5 in [31]) yields to the result.
14.4. Invariants Theorem 14.7 (Automorphism Group [18]). Let H = H 1 . . . H n be the square product of prime hypergraphs H i fulfilling the following condition: For each pair of distinct vertices there exists an edge containing exactly one of those vertices. Furthermore, let ϕ ∈ Aut(H). Then there exists a permutation π of {1, . . . , n} and isomorphisms a i : Then the square product H ′ 1 H ′ 2 is a k 1 k 2 -fold cover of H 1 H 2 via a covering projection π induced naturally by p ′ 1 and p ′ 2 , i.e, define p by: , for e 1 ∈ E ′ 1 , e 2 ∈ E ′ 2 , Theorem 14.10 (Conformal Hypergraphs [9] [61,7]). For any two hypergraphs H = (V, E) and H ′ = (V ′ , E ′ ) with stability number β and β ′ , respectively, holds where H ′ runs over all hypergraphs.
Theorem 14.18 (Fractional Covering and Matching Number [6]). For every hypergraph H with Helly property holds: where H ′ runs over all hypergraphs.
Theorem 14.19 (Partition Number [1]). Let d ∈ N and H i = (V i , E i ), i = 1, . . . , n be hypergraphs such that Theorem 14.20 (Chromatic Number I [7]). For two hypergraphs H and H ′ we have: In [7] the authors asked whether the chromatic number of the square product of two hypergraphs goes to infinity if the chromatic numbers of both of the factors go to infinity. The following theorem, which is due to D. Mubayi and V. Rödl, refutes this conjecture. Moreover, in [48] the authors conjectured that for every r ≥ 2 there is a c ≥ 2 such that for every positive integer k there exists r-uniform hypergraphs G k and H k for which χ(G k ) > k, χ(H k ) > k and χ(G k H k ) ≤ c, and that this also true for the special case c = r = 2.
Other results concerning the chromatic number of a special case of square products, i.e., square products of complete graphs, are due to Sterboul and can be found in [61].
Theorem 14.22 (Discrepancy [15]). For any k ∈ N and any two hypergraphs H, H ′ it holds: A special partial hypergraph of the square product H d of a hypergraph H = (V, E) has found particular attention and is also called the d-fold symmetric product, defined as the subgraph {V d , {e d , e ∈ E}}, where M d denotes the usual d-fold Cartesian set product of the set M . In [14,13] the authors gave several upper and lower bounds for the discrepancy w.r.t. this product.

The Categorial Product
The following hypergraph product was motivated by the investigation of a category of hypergraphs [20]. It is categorical in the category of hypergraphs. It has rarely been studied since its introduction, however; to our knowledge, the only systematic account is a contribution by X. Zhu [64].
The categorial hypergraph product is associative, commutative, distributive w.r.t. the disjoint union and has the single vertex graph with loop LK 1 as unit element. The projections into the factors are, by definition, homomorphisms. However, the product of two simple hypergraphs is not a simple hypergraph and the product of two non-trivial uniform hypergraphs does not result in a uniform hypergraph. For the rank and anti-rank, respectively, of a hypergraph product holds: We have the following relations with other hypergraph products:  [64].

Relationships with Graph Products
The restriction of this product to graphs does not coincide with any known graph product. Moreover, the product G 1 ⊚ G 2 of two graphs G 1 and G 2 is no graph anymore, but a hypergraph of rank 4.
This result can be proved analogously to the proof of Lemma 14.3.

Invariants
Only the chromatic number of the categorial product H 1 ⊚ H 2 has been investigated in some detail [64].

Infinite Hypergraphs
Only finite hypergraphs and products of finitely many factors have been treated so far. It is possible to extend the definitions of the products to infinitely many finite and to infinite hypergraphs. For this purpose we need the following definition. For an arbitrary family of (vertex) sets V i , i ∈ I, their Cartesian set product Notice, that the Cartesian set product of an arbitrary family of sets is usually denoted by i∈I V i , but to emphasize the relation to the finite case, we use the term × i∈I V i instead. In this case, the projection p j : V → V j is defined by v → v j whenever v : j → v j . As before, we will call v j the j-th coordinate of the vertex v ∈ V .
Several of the hypergraph products discussed in the previous section are connected provided each of the the finitely many finite factors are connected. A corresponding result can be established for finitely many connected factors of infinite size using the Distance Formula for the respective product. In contrast, connectedness results do not necessarily carry over to products of infinitely many hypergraphs. As an example consider the Cartesian product of infinitely many factors. There are vertices that differ in infinitely many coordinates and thus, by the Distance Formula cannot be connected by a path of finite length, [49,38]. This in turn leads to difficulties concerning the prime factor decomposition. Again, consider the Cartesian product. An infinite connected hypergraph can have infinitely many prime factors. In this case it cannot be the Cartesian product of these factors, since the product is not connected, but a connected component of this product. For this purpose, the weak Cartesian product is presented which was first introduced by Sabidussi [52] for graphs and later generalized by Imrich [38].
Let {H i | i ∈ I} be a family of hypergraphs and let a i ∈ V (H i ) for i ∈ I. The weak Cartesian product H = ✷ i∈I (H i , a i ) of the rooted hypergraphs (H i , a i ) is defined by Note the weak Cartesian product does not depend on the "reference coordinates" a i ; furthermore, it reduced to the ordinary Cartesian product if I is finite. The weak Cartesian product is associative, commutative, distributive w.r.t. the disjoint union and has trivially K 1 as unit. Furthermore, the weak Cartesian product of connected hypergraphs is connected [38].
Theorem 16.1 (UPFD [49]). Every simple connected finite or infinite hypergraph with finitely or infinitely many factors has a unique PFD w.r.t. the weak Cartesian product.
We suspect that similar constructions can be used to define infinite versions of the other hypergraph products treated in this contribution.
Other results for infinite hypergraphs are known e.g. about the chromatic number of square products:

Directed Hypergraphs
Directed hypergraphs play a role e.g. as models of chemical reaction networks and in transit and satisfiability problems, see [24,63,4] for reviews. Directed hypergraphs can be defined in various ways. Here, we refer to the most general definition. A directed hypergraph − → H = (V, − → E ) consists of a vertex set V and a set of hyperarcs − → E , where each hyperarc − → e ∈ − → E is an ordered pair of nonempty, not necessarily disjoint subsets of V , − → e = (t(e), h(e)), the tail and head of − → e , respectively. We call a directed hypergraph simple, if t(e) ⊆ t(e ′ ) and h(e) ⊆ h(e ′ ) implies − → e = − → e ′ . The 2-section is then a directed graph with arc (x, y) if there is an edge (t(e), h(e)) with x ∈ t(e) and y ∈ h(e).
Product structures have not been studied extensively in a directed setting, even though there are some exceptions. The lexicographic product of directed graphs, for instance, appears in a general technique to amplify lower bounds for index coding problems [8].
The directed version of the Cartesian product was first introduced in [49]. The Cartesian product Basic properties of the Cartesian product of undirected hypergraphs can immediately be transferred to the directed case. Moreover, uniqueness of the PFD was shown in [49].
The definition of the square product might be transferred to hypergraphs as follows: The square product In [43] the authors introduce the square product of so-called N -systems, that is a special class of directed hypergraphs. More precisely, − → N = (V, − → E ) is an Nsystem if |t(e)| = 1 and t(e) ⊆ h(e) holds for all − → e ∈ − → E and − → e ∈ − → E t(e) = V . It is shown that the square product is closed in the class of N -systems, i.e., the square product of two N -systems is again an N -system.
, and connected, then − → N has a unique PFD with unique coordinatization.
The authors conjectured, furthermore, that the condition of thinness can be omitted as long as one is satisfied with a unique PFD without insisting on a unique coordinatization. Table 1 provides an overview of the properties of the hypergraph products discussed in this survey. Table 2 shows which hypergraph invariants can be transferred from factors to products at least under some additional conditions.

Summary
We considered the following properties: (P1) Associativity.   Table 2. Invariants and Hypergraph Products The two summary tables use symbol " √ " to indicate that a condition is satisfied, while "−" means that the product does not have the property in question. The question mark "?" implies that it is unknown at present whether a particular statement is true. Numbers in brackets refer to citations, while numbers without brackets refer to theorems listed in this survey that establish the property under certain additional preconditions or provides results on particular invariants. If (P7) holds only for weak homomorphisms we indicate this with "w". If (P7) and (P8) holds only for the projection onto the first factor we indicate this by "p 1 ".