# Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs

Alexandre Bazin, Laurent Beaudou, Giacomo Kahn, Kaveh Khoshkhah

► To cite this version:

Alexandre Bazin, Laurent Beaudou, Giacomo Kahn, Kaveh Khoshkhah. Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs. Discrete Mathematics and Theoretical Computer Science, 2023, vol. 23 no. 2, special issue in honour of Maurice Pouzet, 10.46298/dmtcs.7129. hal-01847459v7

HAL Id: hal-01847459

https://hal.science/hal-01847459v7

Submitted on 6 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Bounding the Number of Minimal Transversals in Tripartite 3-Uniform Hypergraphs

Alexandre Bazin<fnref n="1" />*
Giacomo Kahn<fnref n="3" />†

Laurent Beaudou<fnref n="2" />
Kaveh Khoshkhah<fnref n="4" />‡

received 25th Jan. 2021, revised 1st Feb. 2022, 19th Oct. 2022, accepted 23rd Feb. 2023.

We focus on the maximum number of minimal transversals in 3-partite 3-uniform hypergraphs on $n$ vertices. Those hypergraphs (and their minimal transversals) are commonly found in database applications. In this paper we prove that this number grows at least like $1.4977^n$ and at most like $1.5012^n$.

**Keywords:** Minimal transversals, hypergraphs, measure and conquer.

## 1 Introduction

Hypergraphs are a generalization of graphs where edges may have arities different than 2. They were formalized in the seventies by Berge and Minieka (1973). Formally, a hypergraph $\mathcal{H}$ is a pair $(V, \mathcal{E})$, where $V$ is a set of vertices and $\mathcal{E}$ a family of subsets of $V$ called hyperedges. In the following, we suppose that $V = \bigcup_{e \in \mathcal{E}} e$, i.e., the hypergraphs that we handle have no isolated vertices. The number of vertices of a hypergraph is called its order. When all the hyperedges of a hypergraph have the same arity $p$, we call it a *p-uniform hypergraph*. When the set of vertices of a hypergraph can be partitioned into $k$ sets such that every edge intersects each part at most once, the hypergraph is called *k-partite*. In the following, we are interested in tripartite, 3-uniform hypergraphs, sometimes known as (3, 3)-hypergraphs. A subset

<footnote n="1">¹ Université de Montpellier, CNRS, LIRMM, F-34095 Montpellier, France</footnote>

<footnote n="2">² Université Clermont Auvergne, Clermont Auvergne INP, CNRS, Mines Saint-Etienne, LIMOS, F-63000 Clermont-Ferrand, France</footnote>

<footnote n="3">³ Univ Lyon, Univ Lumière Lyon 2, INSA Lyon, Université Claude Bernard Lyon 1, DISP, EA4570, 69676 Bron, France</footnote>

<footnote n="4">⁴ Institute of Computer Science, University of Tartu, Tartu, Estonia</footnote>

<footnote>*Alexandre Bazin was supported by the European Union's EUROSTAR PSDP project.</footnote>

<footnote>†Giacomo Kahn was supported by the European Union's "Fonds Européen de Développement Régional (FEDER)" program through project AAP ressourcement S3 - DIS 4 (2015-2018).</footnote>

<footnote>‡Kaveh Khoshkhah was supported by the Estonian Research Council, ETAG (Eesti Teadusagentuur), through PUT Exploratory Grant #620.</footnote>
of the vertices of a hypergraph $\mathcal{H}$ is a *transversal* of $\mathcal{H}$ if it intersects every edge of $\mathcal{H}$ and is said to be a *minimal transversal* if none of its proper subsets is a transversal.

The problem of enumerating the minimal transversals of a given hypergraph has been extensively studied Eiter and Gottlob (1995); Fredman and Khachiyan (1996); Gunopulos et al. (1997). It is an important problem in theoretical computer science as it is equivalent to the dualization of monotone Boolean functions and the enumeration of maximal independent sets Eiter et al. (2008); Kanté et al. (2014). As such, it has many real-world applications in artificial intelligence Eiter and Gottlob (2002), biology Damaschke (2006), mobile communication Sarkar and Sivarajan (1998) and data mining Gunopulos et al. (1997); Stavropoulos et al. (2016); Adaricheva and Nation (2017); Van Lierde and Chow (2019), among others.

Since the number of minimal transversals of a hypergraph may be exponential in the order of the hypergraph, the complexity of enumeration algorithms is often expressed as a function of the size of both their input and their output Strozecki et al. (2019). The maximum number of minimal transversals in a class of hypergraph can then be an important parameter for the real world applications of those theoretical algorithmic evaluations.

Here, we are interested in the number of minimal transversals that arise in tripartite 3-uniform hypergraphs. Such hypergraphs correspond to 3-dimensional Boolean datasets, e.g. data describing *objects* by sets of *attributes* under different *conditions* (not to be mistaken for the notion of condition used in Section 3), and the enumeration of their minimal transversals is involved in the mining of different patterns such as triadic concepts Ignatov et al. (2015); Ignatov (2018), implications Ryssel et al. (2014); Sertkaya (2009) and association rules Missaoui and Kwuida (2011). This work comes from an interest in bounding the number of triadic concepts as studied in triadic concept analysis Lehmann and Wille (1995).

We denote by $f_3(n)$ the maximum number of minimal transversals in tripartite 3-uniform hypergraphs of order $n$.

In 1965, Moon and Moser (1965) provided a construction of a graph of order $n$ that contains $3^{n/3}$ independent sets. This number is reached by using a disjoint union of $K_3s$. The same construction can be adapted to (3, 3)-hypergraphs as illustrated in Figure 1: a set of disjoint 3-edges will form a (3, 3)-hypergraph with $3^{n/3} = 1.4422^n$ minimal transversals, hence $f_3(n) \ge 1.4422^n$.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Moon and Moser's construction (left) and its analogue for (3, 3)-hypergraphs (right).</figcaption></figure>

Moreover, let $\mathcal{H}$ be a (3, 3)-hypergraph which vertices are partitioned into three sets $S_1, S_2$, and $S_3$ that each intersect each hyperedge at most once. For a given vertex set $X \subseteq S_1 \cup S_2$, there is only one possible $Y \subseteq S_3$ such that $X \cup Y$ is a minimal transversal. By supposing that all subsets of $S_1 \cup S_2$ can appear in minimal transversals, we obtain $2^{n-|S_3|}$ minimal transversals. If we choose the smallest of the three sets to be $S_3$, then $S_3$ has at most $n/3$ vertices and so we obtain an upper bound of $2^{n/3} \times 2^{n/3} = 4^{n/3} \approx 1.5874^n$ minimal transversals.

Thus, for any integer $n$, $1.4422^n \le f_3(n) \le 1.5874^n$. In this paper, we improve those bounds through two theorems.
**Theorem 1.** There exists a constant $c$ such that for any integer $n \ge 15$,

$$f_3(n) \ge c1.4977^n.$$

**Theorem 2.** For any integer $n$,

$$f_3(n) \le 1.5012^n.$$

We prove Theorem 1 through a construction based on a hypergraph on fifteen vertices found via computer search. The proof of Theorem 2 relies on a technique introduced by Kullmann (1999) and used by Lonc and Truszczyński (2008) on rank 3 hypergraphs. This class contains (3, 3)-hypergraphs but is much larger, and the bound they obtain is greater than the trivial one implied by the tripartition in our case. This proof technique resembles measure and conquer, an approach used in the analysis of exact exponential-time algorithms, see for example Fomin et al. (2009).

## 2 Lower Bound

We consider tripartite 3-uniform hypergraphs. In this section, we improve the lower bound of $1.4422^n$ for $f_3(n)$ by exhibiting a construction that reaches $c1.4977^n$ minimal transversals, where $c$ is a constant. To this end, we first make an observation that allows us to multiply the number of minimal transversals while only summing the orders of hypergraphs.

**Observation 3.** Let $\mathcal{H}_1$ and $\mathcal{H}_2$ be two hypergraphs of order $n_1$ and $n_2$ with, respectively, $t_1$ and $t_2$ minimal transversals. Then, the disjoint union of $\mathcal{H}_1$ and $\mathcal{H}_2$ has $n_1 + n_2$ vertices and exactly $t_1t_2$ minimal transversals. To put it into words, we sum the orders while multiplying the number of minimal transversals.

A computer search of the space of small hypergraphs allows us to make the following observation.

**Observation 4.** There is a tripartite 3-uniform hypergraph on fifteen vertices with four hundred and twenty-eight minimal transversals.

As such,

$$f_3(15) \ge 428.$$

The hypergraph mentioned in Observation 4 is described in Figure 2 and Figure 3. We denote this hypergraph by $\mathcal{H}_{15}$. Its minimal transversals can be computed using any available software, such as the one maintained by Takeaki Uno$^{(i)}$.

**Theorem 1.** There exists a constant $c$ such that for any integer $n \ge 15$,

$$f_3(n) \ge c1.4977^n.$$

**Proof:**

Let $n$ be an integer greater than 15. There are two unique integers $k$ and $r$ such that $r$ is in $[0, 14]$ and $n = 15k + r$. We aim to build a hypergraph on $n$ vertices with many minimal transversals. The idea is to make the disjoint union of copies of $\mathcal{H}_{15}$. To reach exactly $n$ vertices, the last copy is modified in the following way. Let $\mathcal{H}_{15}^r$ be the hypergraph $\mathcal{H}_{15}$ with $r$ more vertices $v_1, \dots, v_r$. In order for the edges

<footnote>(i) http://research.nii.ac.jp/~uno/dualization.html with the data file at http://giacomo.kahn.science/resources/H15.txt</footnote>
<table><caption>Fig. 2: $\mathcal{H}_{15}$ has fifteen vertices that can be partitioned into three sets $\{\alpha, \beta, \gamma, \delta, \epsilon\}$, $\{1, 2, 3, 4, 5\}$, and $\{a, b, c, d, e\}$. It has four hundred and twenty-eight minimal transversals.</caption><tr><td>{α, 1, a}</td><td>{β, 1, b}</td><td>{γ, 1, c}</td><td>{δ, 1, d}</td><td>{ε, 1, e}</td></tr><tr><td>{α, 2, b}</td><td>{β, 2, c}</td><td>{γ, 2, d}</td><td>{δ, 2, e}</td><td>{ε, 2, a}</td></tr><tr><td>{α, 3, c}</td><td>{β, 3, d}</td><td>{γ, 3, e}</td><td>{δ, 3, a}</td><td>{ε, 3, b}</td></tr><tr><td>{α, 4, d}</td><td>{β, 4, e}</td><td>{γ, 4, a}</td><td>{δ, 4, b}</td><td>{ε, 4, c}</td></tr><tr><td>{α, 4, e}</td><td>{β, 5, a}</td><td>{γ, 5, b}</td><td>{δ, 5, c}</td><td>{ε, 5, d}</td></tr></table>

to span all vertices, we add edges $\{v_i, 1, a\}$ for all $i$ from 1 to $r$. Observe that $\mathcal{H}_{15}^r$ has at least as many minimal transversals as $\mathcal{H}_{15}$. As a consequence of making the disjoint union of $k-1$ copies of $\mathcal{H}_{15}$ and one copy of $\mathcal{H}_{15}^r$, we obtain a tripartite 3-uniform hypergraph on $n$ vertices with at least $428^k$ minimal transversals. Since $k = \frac{n-r}{15}$ and $428^{\frac{1}{15}} > 1.4977$, fixing $c = 428^{-\frac{14}{15}}$ we conclude that for all $n$ greater than 15

$$f_3(n) \geq c \cdot 1.4977^n.$$

<figure><img src="image_3.png" /></figure>

Another way to see the hypergraph $\mathcal{H}_{15}$ is with a 3-dimensional cross table, where a cross in cell $(\alpha, 1, a)$ represents the edge $\{\alpha, 1, a\}$. Note that the crosses representing the 3-edges of this particular hypergraph are a solution to the 3-dimensional chess rook problem. This correspondence is probably devoid of any profound meaning.

<table><caption>Fig. 3: Another representation of $\mathcal{H}_{15}$. Each cross represents a 3-edge.</caption><thead><tr><th></th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th></tr></thead><tbody><tr><td>1</td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td>×</td><td></td><td></td></tr><tr><td>4</td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td>×</td><td></td></tr><tr><td>5</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td></td><td>×</td><td></td><td></td><td></td><td>×</td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td>α</td><td></td><td></td><td></td><td></td><td>β</td><td></td><td></td><td></td><td></td><td>γ</td><td></td><td></td><td></td></tr><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>δ</td><td></td><td></td><td>ε</td></tr></tbody></table>

## 3 Upper Bound

In this section, we prove that $f_3(n) \leq 1.5012^n$ (Theorem 2) by first proving the technical Lemma 10. The general structure of the proof is similar to Lonc and Truszczyński's proof of their bound to the maximal number of minimal transversals in 3-uniform hypergraphs in Lonc and Truszczyński (2008) and is as follows.

Given a rooted tree. If we have a probability distribution attributed to each internal node for picking one of its children, we may apply the following random process: start from the root, and follow the node distribution to pick one of its children until you reach a leaf. In this process, the probability to end up in some fixed leaf is the product of probabilities on the unique path from this leaf to the root. The sum over all leaves of these probabilities equals 1. Consider the smallest such probability $p$. Then the number of leaves is bounded above by $p^{-1}$. Actually, for any tree, there is such a probability distribution that assigns
the same probability to each leaf in the end. When facing an unknown structure, we may not be able to
find that optimum distribution, but this tool gives us some power to adjust the counting of the leaves.

In this paper, we build a tree where the root is some specific hypergraph $\mathcal{H}_0$. All nodes will be hyper-
graphs and the leaves can be identified with minimal transversals of $\mathcal{H}_0$. We build an adequate probability
distribution by designing some measure function $\mu$ on our hypergraphs. For internal node $\mathcal{H}$, we shall
fix some value $\tau$ and give probability $\tau^{\mu(\mathcal{H}')} - \mu(\mathcal{H})$ to the transition towards its child $\mathcal{H}'$. This value $\tau$ is
uniquely defined since we want the sum to be equal to 1 at each step. In the end, if we manage to bound
all values $\tau$ above by some $\tau_0$ and if the leaves have non-negative measures, the product of all those
probabilities shall be bounded below by $\tau_0^{-\mu(\mathcal{H})}$ and thus the number of leaves is no more than $\tau_0^{\mu(\mathcal{H})}$.

<figure><img src="image_4.png" /><figcaption>Fig. 4: This small hypergraph shall serve as an example to illustrate the following concepts of condition, procedure and measure.</figcaption></figure>

Let us dive into the more technical part, illustrated with Figure 4’s example hypergraph. We use the
notion of *condition*, introduced thereafter.

**Definition 5.** *Given a set V of vertices, a condition on V is a pair (A<sup>+</sup>, A<sup>-</sup>) of disjoint sets of vertices. A condition is trivial if A<sup>+</sup> ∪ A<sup>-</sup> = ∅, and non-trivial otherwise.*

All the conditions that we handle are non-trivial. A set $T$ of vertices satisfies a condition $(A^+, A^-)$ if $A^+ \subseteq T$ and $T \cap A^- = \emptyset$. As such, having vertex sets satisfy a condition amounts to forcing a set of vertices to be present (the vertices in $A^+$) and forbidding other vertices (the vertices in $A^-$). For instance, $\{1, b\}$ is a minimal transversal of the hypergraph depicted in Figure 4 that satisfies the condition $(\{1\}, \{\gamma\})$ because it contains 1 but not $\gamma$.

Let $\mathcal{H}$ be a hypergraph and $(A^+, A^-)$ a condition. The hypergraph $\mathcal{H}_{(A^+, A^-)}$ is constructed from $\mathcal{H}$ and $(A^+, A^-)$ through the following procedure:

1. remove every edge that contains a vertex that is in $A^+$;

2. remove from every remaining edge the vertices that are in $A^-$;

3. remove redundant edges.

Vertices of $\mathcal{H}$ that appear in a condition $(A^+, A^-)$ are not in $\mathcal{H}_{(A^+, A^-)}$ as they are either removed from all the edges or all the edges that contain them have disappeared. For instance, if $\mathcal{H}$ is the hypergraph depicted in Figure 4 and $A = (\{1\}, \{\gamma\})$, the hypergraph $\mathcal{H}_{(\{1\}, \{\gamma\})}$ is the one depicted in Figure 5.
<figure><img src="image_5.png" /><figcaption>Fig. 5: Let $\mathcal{H}$ be the hypergraph in Figure 4. Then, this figure depicts $\mathcal{H}_{\{(1), (\gamma)\}}$. The edges that contained 1 were removed from the hypergraph and the vertex $\alpha$ was removed from the remaining edge.</figcaption></figure>

**Lemma 6.** Let $\mathcal{H}$ be a hypergraph, $(A^+, A^-)$ be a condition and $T$ be a set of vertices of $\mathcal{H}$. If $T$ is a minimal transversal of $\mathcal{H}$ and $T$ satisfies $(A^+, A^-)$, then $T \setminus A^+$ is a minimal transversal of $\mathcal{H}_{(A^+, A^-)}$.

**Proof:** The proof is straightforward from the construction of $\mathcal{H}_{(A^+, A^-)}$. $\square$

<figure><img src="image_6.png" /></figure>

A family of conditions is *complete* for the hypergraph $\mathcal{H}$ if the family is non-empty, each condition in the family is non-trivial, and every minimal transversal of $\mathcal{H}$ satisfies at least one condition of the family. For instance, $\{(\{1\}, \{\gamma\})\}$ is not a complete family of conditions for the hypergraph depicted in Figure 4 because there is a minimal transversal, $\{\gamma, \delta\}$, that does not contain the vertex 1 and thus does not satisfy any of the conditions. However, $\{(\{1\}, \emptyset), (\emptyset, \{1\})\}$ is a complete family of conditions because all minimal transversals either contain or do not contain the vertex 1.

Let $C$ be the class of $k$-partite hypergraphs with $k \le 3$ such that their vertex set can be partitioned into $k$ independent sets in such a way that one of the parts is a minimal transversal. We suppose that they are implicitly partitioned in such a way and call $S$ the part that is a minimal transversal. Tripartite 3-uniform hypergraphs belong to this class. It is clear that $k$-partite hypergraphs do not become $(k+1)$-partite when vertices are removed from edges or edges are deleted. As such, if a hypergraph $\mathcal{H} = (V, \mathcal{E})$ belongs to the class $C$ and $A = (A^+, A^-)$ is a condition on $V$ such that the edges that contain vertices of $A^- \cap S$ also contain vertices of $A^+$, then $\mathcal{H}_A$ is in $C$. From now on, we suppose that all the conditions we handle respect this property.

A hypergraph is non-trivial if it is not empty. A *descendant function* for $C$ is a function that assigns to each non-trivial hypergraph in $C$ a complete family of conditions. Let $\rho$ be such a function.

Using $\rho$, we can construct a rooted labeled tree $T_{\mathcal{H}}$ for all hypergraphs $\mathcal{H}$ in $C$. When $\mathcal{H}$ is trivial, then $T_{\mathcal{H}}$ is a single node labeled with $\mathcal{H}$. When $\mathcal{H}$ is non-trivial, we create a node labeled with $\mathcal{H}$ and make it the parent of the root of all the trees $T_{\mathcal{H}_A}$, for $A \in \rho(\mathcal{H})$. Note that this construction is possible because $C$ is closed under the operation of removing edges and removing vertices from edges, and the number of vertices can only decrease when the transformation from $\mathcal{H}$ to $\mathcal{H}_A$ occurs. Such a rooted tree corresponding to our toy example is presented in Figure 6. One can check that all the conditions above are respected.

**Proposition 7.** Let $\rho$ be a descendant function for a hypergraph class closed under removing edges and removing vertices from edges. Then for all hypergraphs $\mathcal{H}$ in such a class, the number of minimal transversals is bounded above by the number of leaves of $T_{\mathcal{H}}$.

**Proof:** If $\mathcal{H}$ is trivial, then it has only one transversal, the empty set. If the empty set is an edge of $\mathcal{H}$, then $\mathcal{H}$ has no transversals. In both cases, the proposition follows directly from the definition of the tree. Let us assume now that $\mathcal{H}$ is non-trivial, and that the proposition is true for all hypergraphs with fewer vertices than $\mathcal{H}$.
<figure><img src="image_7.png" /><figcaption>Fig. 6: Example of a decomposition tree for our running example. The measure $\mu$ is given for each hypergraph, while the conditions are given on the edges.</figcaption></figure>
As $\mathcal{H}$ is non-trivial $\rho$ is well defined for $\mathcal{H}$ and $\rho(\mathcal{H})$ is a complete family of conditions. Let $X$ be a minimal transversal of $\mathcal{H}$. Then $X$ satisfies at least one condition $A$ in $\rho(\mathcal{H})$. From Lemma 6, we know that there is a minimal transversal $Y$ of $\mathcal{H}_A$ such that $Y = X \setminus A^+$. Then the number of minimal transversals of $\mathcal{H}$ is at most the sum of the number of minimal transversals in its children. $\square$

Bounding the number of leaves in $\mathcal{T}_\mathcal{H}$ for all hypergraphs $\mathcal{H} \in \mathcal{C}$ is thus bounding $f_3(n)$. In order to do that, we use Lemma 8 proven by Kullmann (1999). We denote by $L(\mathcal{T})$ the set of leaves of a rooted tree $\mathcal{T}$ and, for a leaf $\ell \in L(\mathcal{T})$, we denote by $P(\ell)$ the set of edges on the path from the root to $\ell$.

**Lemma 8** ((Kullmann, 1999, Lemma 8.1)). Consider a rooted tree $\mathcal{T}$ with an edge labeling $w$ with value in the interval $[0, 1]$ such that for every internal node, the sum of the labels on the edges from that node to its children is 1 (that is a transition probability).

Then,

$$|L(\mathcal{T})| \le \max_{\ell \in L(\mathcal{T})} \left( \prod_{e \in P(\ell)} w(e) \right)^{-1}.$$

In order to pick an adequate probability distribution, we use a measure. A measure $\mu$ is a function that assigns to any hypergraph $\mathcal{H}$ in $\mathcal{C}$ a real number $\mu(\mathcal{H})$ such that $0 \le \mu(\mathcal{H}) \le |V(\mathcal{H})|$. Let $A$ be a condition on the vertices of hypergraph $\mathcal{H}$ and $\mu$ be a measure. We define

$$\Delta(\mathcal{H}, \mathcal{H}_A) = \mu(\mathcal{H}) - \mu(\mathcal{H}_A).$$

If, for every condition $A$ in $\rho(\mathcal{H})$, $\mu(\mathcal{H}_A) \le \mu(\mathcal{H})$, then we say that $\rho$ is $\mu$-compatible. In this case, there is a unique positive real number $\tau \ge 1$ such that

$$\sum_{A \in \rho(\mathcal{H})} \tau^{-\Delta(\mathcal{H}, \mathcal{H}_A)} = 1.$$

When $\tau \ge 1$, $\sum_{A \in \rho(\mathcal{H})} \tau^{-\Delta(\mathcal{H}, \mathcal{H}_A)}$ is a strictly decreasing continuous function of $\tau$. For $\tau = 1$, it is at least 1, since $\rho(\mathcal{H})$ is not empty, and it tends to 0 when $\tau$ tends to infinity.

A descendant function defined on a class $\mathcal{C}$ is $\mu$-bounded by $\tau_0$ if, for every non-trivial hypergraph $\mathcal{H}$ in $\mathcal{C}$, $\tau \le \tau_0$.

Now, we adapt the $\tau$-lemma proven by Kullmann (1999) to our formalism.

**Theorem 9** (Kullmann (1999)). Let $\mu$ be a measure and $\rho$ a descendant function, both defined on a class $\mathcal{C}$ of hypergraphs closed under the operations of removing edges and removing vertices from edges. If $\rho$ is $\mu$-compatible and $\mu$-bounded by $\tau_0$, then for every hypergraph $\mathcal{H}$ in $\mathcal{C}$,

$$|L(\mathcal{T}_\mathcal{H})| \le \tau_0^{h(\mathcal{T}_\mathcal{H})}$$

where $h(\mathcal{T}_\mathcal{H})$ is the height of $\mathcal{T}_\mathcal{H}$.

We now use Theorem 9 to provide an upper bound to $f_3(n)$. We start by proving Lemma 10 using an approach similar to that of Lonc and Truszczyński (2008).

**Lemma 10.** There is a measure $\mu$ defined for every hypergraph $\mathcal{H}$ in $\mathcal{C}$ and a descendant function $\rho$ for $\mathcal{C}$ that is $\mu$-compatible and $\mu$-bounded by 1.8393.
**Proof:**

Let $\mathcal{H}$ be a hypergraph belonging to the class $\mathcal{C}$, i.e., a $k$-partite, $k \le 3$ hypergraph that contains a set $S$ of vertices that is a minimal transversal such that no two vertices of $S$ belong to a same edge. A 2-matching in a hypergraph is a set of pairwise disjoint 2-edges.

We choose, as the measure $\mu(\mathcal{H})$,

$$ \mu(\mathcal{H}) = |V(\mathcal{H})| - \alpha m(\mathcal{H}) $$

where $m(\mathcal{H})$ is the maximum number of pairwise disjoint 2-edges in $\mathcal{H}$ (i.e. the size of its maximum 2-matchings) and $\alpha = 0.145785$. The same measure is used in Lonc and Truszczyński (2008) (with a different $\alpha$).

We use Theorem 9 to bound the number of leaves in the tree $\mathcal{T}_{\mathcal{H}}$ and thus the number of minimal transversals in $\mathcal{H}$. To do so, we define a descendant function $\rho$ that assigns a family of conditions to $\mathcal{H}$ depending on its structure. This takes the form of a case analysis.

In each case, we consider a vertex $a \in S$ and its neighbours. The conditions are chosen in such a way that they are pairs $(A^+, A^-)$ of subsets of these neighbours and are sometimes strengthened to contain $a$ if and only if its presence in $A^+$ or $A^-$ is implied by our hypotheses. This causes every condition $A$ to respect the property that $A^+$ intersects all the edges containing a vertex of $A^- \cap S$, which lets $\mathcal{H}_A$ remain in the class $\mathcal{C}$.

In each case $i$ and for every condition $A \in \rho(\mathcal{H})$, we find a bound $k_{\mathcal{H},A}$ such that

$$ k_{\mathcal{H},A} \le \Delta(\mathcal{H}, \mathcal{H}_A) $$

and a unique positive real number $\tau_i$ that satisfies the equation

$$ \sum_{A \in \rho(\mathcal{H})} \tau_i^{-k_{\mathcal{H},A}} = 1 \qquad (1) $$

We show that $\tau_i \le 1.8393$ for all $i$. Let $\tau_0 = 1.8393$.

As all our conditions involve at least one element from $V(\mathcal{H}) \setminus S$, the height of $\mathcal{T}_{\mathcal{H}}$ is bounded by $|V(\mathcal{H})| - |S|$. Hence, we have

$$ |L(\mathcal{T}_{\mathcal{H}})| \le \tau_0^{|V(\mathcal{H})| - |S|} $$

In the remainder of the proof, we will write conditions as sets of expressions of the form $a$ and $\bar{b}$ where $a$ means that $a$ is in $A^+$ and $\bar{b}$ means that $b$ is in $A^-$. For example, the condition $(\{a, c\}, \{b, d, e\})$ will be written as $ac\bar{b}de$ and the condition $(\{b, c\}, \emptyset)$ will be written as $bc$. For a vertex $v$, we denote by $d_2(v)$ the number of 2-edges that contain $v$, and by $d_3(v)$ the number of 3-edges that contain $v$.

For each case, we suppose that the previous ones do not apply.

**Case 1:** $d_2(a) \ge 2$. The hypergraph $\mathcal{H}$ contains a vertex $a$ from $S$ that belongs to at least two 2-edges $\{a, b\}$ and $\{a, c\}$ (Figure 7).
<figure><img src="image_8.png" /><figcaption>Fig. 7: Case 1: The vertex $a \in S$ is in at least two 2-edges and may be part of some other 2-edges or 3-edges.</figcaption></figure>

A minimal transversal of $\mathcal{H}$ either contains or does not contain $b$, and as such $\{b, \bar{b}\}$ is a complete family of conditions for $\mathcal{H}$. Similarly, a minimal transversal of $\mathcal{H}$ either contains or does not contain $c$ so $\{bc, \bar{b}, \bar{b}\}$ is also a complete family of conditions. Minimal transversals of $\mathcal{H}$ that do not contain $b$ or $c$ necessarily contain $a$ (as $\{a, b\}$ or $\{a, c\}$ would not be covered otherwise). Hence $\{bc, ab\bar{c}, a\bar{b}\}$ is a complete family of conditions for $\mathcal{H}$.

Let $M$ be a maximum set of pairwise distinct 2-edges of $\mathcal{H}$. By removing $k$ vertices we decrease the size of a maximum 2-matching by at most $k$. Hence, $|V(\mathcal{H}_A)| \le |V(\mathcal{H})| - 2$ and $m(\mathcal{H}_A) \ge m(\mathcal{H}) - 2$ when $A \in \{bc, a\bar{b}\}$. Similarly, $|V(\mathcal{H}_{ab\bar{c}})| \le |V(\mathcal{H})| - 3$ and $m(\mathcal{H}_{ab\bar{c}}) \ge m(\mathcal{H}) - 3$. Thus, we have

$$ \Delta(\mathcal{H}, \mathcal{H}_A) \ge \begin{cases} 2 - 2\alpha & \text{for } A \in \{bc, a\bar{b}\} \\ 3 - 3\alpha & \text{for } A = ab\bar{c} \end{cases}. \qquad (2) $$

Equation (1) becomes $2\tau_1^{2\alpha-2} + \tau_1^{3\alpha-3} = 1$. For our chosen $\alpha$, we have that $\tau_1 \le \tau_0$.

**Case 2:** $d_2(a) = 1$. The hypergraph $\mathcal{H}$ contains a vertex $a$ from $S$ that belongs to a unique 2-edge $\{a, b\}$ (Figure 8). We break down this case into two sub-cases depending on whether or not $a$ belongs to some 3-edges: $d_3(a) = 0$ and $d_3(a) \ge 1$.

<figure><img src="image_9.png" /><figcaption>Fig. 8: Case 2: The vertex $a$ is part of only one 2-edge $\{a, b\}$ and may be part of other 3-edges.</figcaption></figure>

Since $a$ is in only one 2-edge, removing both $a$ and $b$ decreases the size of a maximum 2-matching by at most 1.

* $d_3(a) = 0$: $a$ is in a single 2-edge $\{a, b\}$ and no 3-edges. A minimal transversal of $\mathcal{H}$ either contains or does not contain $b$. As such, $\{b, \bar{b}\}$ is a complete family of conditions for $\mathcal{H}$. As $\{a, b\}$ is the only edge containing $a$, a minimal transversal of $\mathcal{H}$ that contains $b$ cannot contain $a$. Similarly, every minimal transversal of $\mathcal{H}$ that does not contain $b$ necessarily contains $a$. This makes $\{b\bar{a}, a\bar{b}\}$ a complete family of conditions for $\mathcal{H}$.
Let $M$ be a maximum set of pairwise disjoint 2-edges of $\mathcal{H}$. As $\{a, b\}$ is the only edge containing $a, b$ belongs to one of the edges in $M$. The hypergraphs $\mathcal{H}_{b\bar{a}}$ and $\mathcal{H}_{a\bar{b}}$ contain all the edges in $M$ except for the one containing $b$. Thus, $m(\mathcal{H}_{b\bar{a}}) = m(\mathcal{H}_{a\bar{b}}) \ge m(\mathcal{H}) - 1$. Since $|V(\mathcal{H}_{b\bar{a}})| = |V(\mathcal{H}_{a\bar{b}})| \le |V(\mathcal{H})| - 2$, we have

$$ \Delta(\mathcal{H}, \mathcal{H}_A) \ge 2 - \alpha \text{ for } A \in \{b\bar{a}, a\bar{b}\}. \quad (3) $$

Equation (1) becomes $2\tau_{2.1}^{\alpha-2} = 1$. For our chosen $\alpha$, we have that $\tau_{2.1} \le \tau_0$.

<figure><img src="image_10.png" /><figcaption>Fig. 9: Case 2.2: The vertex $a$ is part of only one 2-edge $\{a, b\}$ and at least one 3-edge $\{a, c, d\}$.</figcaption></figure>

* $d_3(a) \ge 1$: $a$ is in a single 2-edge and in some 3-edges, one of which being $\{a, c, d\}$ (Figure 9). We start with the complete family of conditions $\{bc, bd\bar{c}, b\bar{c}\bar{d}, \bar{b}\}$. Any minimal transversal of $\mathcal{H}$ that does not contain either $b$ or both $c$ and $d$ necessarily contains $a$. This makes $\{bc, bd\bar{c}, ab\bar{c}\bar{d}, a\bar{b}\}$ a complete family of conditions for $\mathcal{H}$. Removing either $b, c$ or $d$ from the hypergraph decreases the size of the maximum 2-matching by at most one. As mentioned previously, removing both $a$ and $b$ cannot decrease the size of the maximum 2-matching by more than 1. As such, $m(\mathcal{H}_A) \ge m(\mathcal{H}) - |A|$ when $A \in \{bc, bd\bar{c}, a\bar{b}\}$ and $m(\mathcal{H}_{a\bar{b}\bar{c}\bar{d}}) \ge m(\mathcal{H}) - 3$. We obtain

$$ \Delta(\mathcal{H}, \mathcal{H}_A) \ge \begin{cases} 2 - 2\alpha & \text{if } A = bc \\ 3 - 3\alpha & \text{if } A = bd\bar{c} \\ 4 - 3\alpha & \text{if } A = ab\bar{c}\bar{d} \\ 2 - \alpha & \text{if } A = a\bar{b} \end{cases} \quad (4) $$

Equation (1) becomes $\tau_{2.2}^{2\alpha-2} + \tau_{2.2}^{3\alpha-3} + \tau_{2.2}^{3\alpha-4} + \tau_{2.2}^{\alpha-2} = 1$. For our chosen $\alpha$, we have that $\tau_{2.2} \le \tau_0$.

**Case 3:** $d_2(a) = 0$ and $d_3(a) \ge 1$. The hypergraph $\mathcal{H}$ contains a vertex $a$ from $S$ that is in no 2-edge and in some 3-edges, one of which being $\{a, b, c\}$ (Figure 10).

<figure><img src="image_11.png" /><figcaption>Fig. 10: Case 3: The vertex $a$ is in at least one 3-edge, but in no 2-edge.</figcaption></figure>
We start with the conditions {$b, c\bar{b}, \bar{b}c$}. Any minimal transversal that does not contain $b$ and $c$ necessarily contains $a$ so we strengthen the family of conditions to {$b, c\bar{b}, ab\bar{c}$}. Since we do not have any 2-edge anymore (because previous cases do not apply), we cannot decrease the size of a maximum 2-matching. We obtain

$$ \Delta(\mathcal{H}, \mathcal{H}_A) \ge \begin{cases} 1 & \text{if } A = b \\ 2 & \text{if } A = c\bar{b} \\ 3 & \text{if } A = ab\bar{c} \end{cases} \qquad (5) $$

Equation (1) becomes $\tau_3^{-1} + \tau_3^{-2} + \tau_3^{-3} = 1$. For our chosen $\alpha$, we have that $\tau_3 \le \tau_0$. $\square$

This proof ensures that there is a measure $\mu$ and a descendant function $\rho$ for our class of hypergraphs such that $\rho$ is $\mu$-bounded by 1.8393. This allows us to formulate the following theorem.

**Theorem 11.** Let $C$ be the class of $k$-partite hypergraphs with $k \le 3$ such that their vertex set can be partitioned into $k$ independent sets in such a way that one of the parts, $S$, is a minimal transversal.

The number of minimal transversals in a hypergraph belonging to the class $C$ is less than $1.8393^{n-|S|}$.

**Proof:** Let $\mu$ and $\rho$ be the measure and descendant function used in Lemma 10's proof. The height $h(\mathcal{T}_H)$ of the tree is less than $n - |S|$ so applying Theorem 9 yields the result. $\square$

Theorem 2 is a straightforward corollary of Theorem 11.

**Theorem 2.** For any integer $n$,

$$ f_3(n) \le 1.8393^{2n/3} \le 1.5012^n. $$

**Proof:** The vertices of a tripartite 3-uniform hypergraph can be partitioned into three minimal transversals so any of them can be $S$. The minimization of the bound is achieved by using the biggest set which, in the worst case, has size $n/3$. $\square$

# 4 Discussion and Conclusion

In this paper, we showed that the maximum number of minimal transversals in (3, 3)-hypergraphs of order $n$ is between $c1.4977^n$, where $c$ is a constant, and $1.5012^n$. Both bounds can be used to better analyse the worst-case complexity of algorithms for mining 3-dimensional Boolean data, such as TRIAS Jaschke et al. (2006), Data-Peeler Cerf et al. (2008) or the one proposed by Makhalova and Nourine (2017).

As a future work, the upper bound could be improved through the same approach by choosing a better measure or branching. The lower bound could maybe be improved by finding other worst cases through computer search. The worst cases we managed to find all corresponded to solutions of the chess rook problem in $\frac{n}{3} \times \frac{n}{3} \times \frac{n}{3}$ matrices up to $n = 5$ (see Figure 3). However, this did not seem to be the case for $n = 6$ so we postulate that it does not work for $n > 5$.

There is also a growing interest for pattern mining in $k$-dimensional datasets with $k > 3$ as reality cannot always be represented by mere ternary relations. For this reason, it would be interesting to devise a more general proof, following the same schema, to bound the maximal number of minimal transversals in $(k, k)$-hypergraphs.
References

K. Adaricheva and J. B. Nation. Discovery of the d-basis in binary tables based on hypergraph dualization.
*Theoretical Computer Science*, 658:307–315, 2017.

C. Berge and E. Minieka. *Graphs and hypergraphs*. North-Holland publishing company Amsterdam, 1973.

L. Cerf, J. Besson, C. Robardet, and J.-F. Boulicaut. Data-peeler: Constraint-based closed pattern mining in n-ary relations. In *proceedings of the 2008 SIAM International conference on Data Mining*, pages 37–48. SIAM, 2008.

P. Damaschke. Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. *Theoretical Computer Science*, 351(3):337–350, 2006.

J. David, L. Lhote, A. Mary, and F. Rioult. An average study of hypergraphs and their minimal transversals. *Theoretical Computer Science*, 596:124–141, 2015.

T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. *SIAM Journal on Computing*, 24(6):1278–1304, 1995.

T. Eiter and G. Gottlob. Hypergraph transversal computation and related problems in logic and ai. In *European Workshop on Logics in Artificial Intelligence*, pages 549–564. Springer, 2002.

T. Eiter, K. Makino, and G. Gottlob. Computational aspects of monotone dualization: A brief survey. *Discrete Applied Mathematics*, 156(11):2035–2049, 2008.

F. V. Fomin and D. Kratsch. *Exact Exponential Algorithms*. Springer Science & Business Media, 2010.

F. V. Fomin, F. Grandoni, and D. Kratsch. A measure & conquer approach for the analysis of exact algorithms. *J. ACM*, 56(5):25:1–25:32, 2009. doi: 10.1145/1552285.1552286. URL http://doi.acm.org/10.1145/1552285.1552286.

M. L. Fredman and L. Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. *Journal of Algorithms*, 21(3):618–628, 1996.

B. Ganter and R. Wille. *Formal concept analysis: mathematical foundations*. Springer Science & Business Media, 2012.

D. Gunopulos, H. Mannila, R. Khardon, and H. Toivonen. Data mining, hypergraph transversals, and machine learning. In *Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems*, pages 209–216, 1997.

D. I. Ignatov. On closure operators related to maximal tricliques in tripartite hypergraphs. *Discrete Applied Mathematics*, 249:74–84, 2018.

D. I. Ignatov, D. V. Gnatyshak, S. O. Kuznetsov, and B. G. Mirkin. Triadic formal concept analysis and triclustering: searching for optimal patterns. *Machine Learning*, 101(1-3):271–302, 2015.
R. Jaschke, A. Hotho, C. Schmitz, B. Ganter, and G. Stumme. Trias-an algorithm for mining iceberg tri-lattices. In *Sixth International Conference on Data Mining (ICDM'06)*, pages 907-911. IEEE, 2006.

M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. *SIAM Journal on Discrete Mathematics*, 28(4):1916-1929, 2014.

O. Kullmann. New methods for 3-sat decision and worst-case analysis. *Theor. Comput. Sci.*, 223 (1-2):1-72, 1999. doi: 10.1016/S0304-3975(98)00017-6. URL https://doi.org/10.1016/S0304-3975(98)00017-6.

F. Lehmann and R. Wille. A triadic approach to formal concept analysis. In *International Conference on Conceptual Structures*, pages 32–43. Springer, 1995.

Z. Lonc and M. Truszczyński. On the number of minimal transversals in 3-uniform hypergraphs. *Discrete Mathematics*, 308(16):3668-3687, 2008. doi: 10.1016/j.disc.2007.07.024. URL https://doi.org/10.1016/j.disc.2007.07.024.

T. Makhalova and L. Nourine. An incremental algorithm for computing n-concepts. In *Formal Concept Analysis for Knowledge Discovery. Proceedings of International Workshop on Formal Concept Analysis for Knowledge Discovery (FCA4KD 2017)*, Moscow, Russia, 2017.

R. Missaoui and L. Kwuida. Mining triadic association rules from ternary relations. In *International Conference on Formal Concept Analysis*, pages 204–218. Springer, 2011.

J. W. Moon and L. Moser. On cliques in graphs. *Israel journal of Mathematics*, 3(1):23–28, 1965.

U. Ryssel, F. Distel, and D. Borchmann. Fast algorithms for implication bases and attribute exploration using proper premises. *Annals of Mathematics and Artificial Intelligence*, 70(1):25–53, 2014.

S. Sarkar and K. N. Sivarajan. Hypergraph models for cellular mobile communication systems. *IEEE Transactions on Vehicular Technology*, 47(2):460–471, 1998.

B. Sertkaya. Some computational problems related to pseudo-intents. In *International Conference on Formal Concept Analysis*, pages 130–145. Springer, 2009.

E. C. Stavropoulos, V. S. Verykios, and V. Kagklis. A transversal hypergraph approach for the frequent itemset hiding problem. *Knowledge and information systems*, 47(3):625–645, 2016.

Y. Strozecki et al. Enumeration complexity. *Bulletin of EATCS*, 3(129), 2019.

H. Van Lierde and T. W. Chow. Query-oriented text summarization based on hypergraph transversals. *Information Processing & Management*, 56(4):1317-1338, 2019.