# Knowledge-enhanced Neuro-Symbolic AI for Cybersecurity and Privacy

Aritran Piplai1, Anantaa Kotal1, Seyedreza Mohseni1, Manas Gaur1, Sudip
Mittal2, and Anupam Joshi1

1 Dept. of CSEE, University of Maryland, Baltimore County, Maryland, USA,
21250  2 Dept. of CSE, Mississippi State University, Mississippi State, MS,
USA, 39762

###### Abstract

Neuro-Symbolic Artificial Intelligence (AI) is an emerging and quickly
advancing field that combines the subsymbolic strengths of (deep) neural
networks and explicit, symbolic knowledge contained in knowledge graphs to
enhance explainability and safety in AI systems. This approach addresses a key
criticism of current generation systems, namely their inability to generate
human-understandable explanations for their outcomes and ensure safe
behaviors, especially in scenarios with unknown unknowns (e.g. cybersecurity,
privacy). The integration of neural networks, which excel at exploring complex
data spaces, and symbolic knowledge graphs, which represent domain knowledge,
allows AI systems to reason, learn, and generalize in a manner understandable
to experts. This article describes how applications in cybersecurity and
privacy, two most demanding domains in terms of the need for AI to be
explainable while being highly accurate in complex environments, can benefit
from Neuro-Symbolic AI.

###### Index Terms:

Knowledge-infused Learning, Knowledge Graphs, Cybersecurity, Privacy, Neuro-
Symbolic AI

##  I Introduction and Background

Neuro-Symbolic AI refers to the integration of neural network-based methods
with symbolic knowledge-based approaches. It combines the strengths of both
approaches to leverage the representational power of neural networks and the
logical reasoning capabilities of symbolic approaches. Neural networks are
excellent at large-scale data processing and the extraction of intricate
patterns and characteristics from unprocessed input. However, they often
struggle to provide explicit explanations for their decisions [1]. This is one
of the reasons why, after a promising decade of work from the mid 80s, Neural
networks never made it beyond academic and industrial research labs. On the
other hand, symbolic knowledge-based approaches, such as rule-based systems or
expert systems, utilize explicit knowledge representations and logical
reasoning mechanisms. They can capture domain-specific knowledge and provide
transparent explanations for their conclusions [1, 2]. However, these
approaches may struggle with handling uncertain or incomplete information and
have limited capacity to learn from large-scale data [1].

A combination of these two paradigms, called Neuro-Symbolic AI, has started to
see popularity among the AI community over the last five years. The idea for
this combination is not new, with the term Neural Symbolic being used at least
as far back as the early 2000s [2]. In the 90s, there were several efforts to
marry connectionist approaches with fuzzy rules, for instance [3]. Indeed, it
can (and has) been argued that the kernel of this idea can be found in the
McColloch and Pitts’ paper titled “A logical calculus of the ideas immanent in
nervous activity”. There are multiple reasons for this renewed popularity. We
describe these reasons in the context of cybersecurity.

First, a combination of symbolic reasoning and data-driven methods can be used
to extract the sequence of steps or events that triggered the conclusion that
the model reached. This is a great motivation for Neuro-Symbolic approaches to
be used in cybersecurity and privacy, especially in solving problems such as
threat detection and analysis, which require not just patterns to be detected,
but such detected patterns from disparate systems across time to be put into a
common context [4]. Neuro-Symbolic approaches can do this while preserving
privacy (e.g. incorporating privacy policies, regulations, compliance). For
example, a Neuro-Symbolic model can reason about sensitive network flow data
usage by the neural network detector based on explicit privacy policies and
ensure compliance by incorporating privacy-preserving techniques such as
differential privacy or secure multi-party computation.

Second is keeping AI systems secure and safe. The rise in data-driven models
for automating vulnerability assessment of systems limits safety, since the
system learns only the vulnerabilities it is trained on. In a Neuro-Symbolic
approach, the AI-based software systems would be trained with experts acting
as adversaries and the AI model would learn to infer policies/rules
dynamically [1]. Further, with knowledge in security specification documents
explicitly captured using symbolic approaches and used as constraints on
behavior, the AI system would be more robust and safe. This is of immediate
interest to regulators and legislators in many countries as advanced AI
systems have a high probability for generating risky/harmful information,
without the control of human knowledge/expertise.

Another reason why a combination of rules and data-driven methods may be
useful is the lack of high-quality data to make reliable inferences. This
problem can be found in domains where the data for experiments is either hard
to obtain, or difficult to share because it may be sensitive. However,
alternate sources such as text descriptors of the sensitive data may be
available. Rules can be derived from these alternate sources that are
shareable. If the available data alone is insufficient to infer reliable
conclusions, these rules can be used to augment the conclusions derived from
the data [5]. They can also be provided as an input to the data-driven model
during the learning process.

Some domains may also be very dynamic and so the data may be representative
for only a brief period of time. The conclusions derived from the data may
also be valid for a brief period of time. This is a problem in domains such as
cybersecurity and fraud-detection. The patterns that we derive from our
existing dataset may be useful for some cyber-attacks that are happening right
now, but they may not be useful in the future. Combining Deep network based
detectors with explicit rules that capture data drift or the temporal limits
on the usefulness of a model can help in such situations.

##  II Neuro-Symbolic AI in Cyber

In the context of cybersecurity, Neuro-Symbolic AI can be applied to enhance
various aspects of security systems, such as intrusion detection, malware
analysis, vulnerability assessment, and threat intelligence. Very broadly, it
can assist in creating the next generation Security Operations Center (SoC)
which combines AI approaches with a human either in or on the loop.

Let us consider a scenario of security analysts, who work in a SoC and play a
major role in ensuring the security of an organization. The amount of
background knowledge they have about evolving and new attacks makes a
significant difference in their ability to detect attacks from the output of
deep neural networks or machine learning (ML) based systems that today analyze
the sensed data stream. We can assist an analyst by capturing information
available in open-source threat intelligence sources, such as text
descriptions of cyber-attacks or threat feeds, and store them in a structured
fashion in a cybersecurity knowledge graph (CKG). We describe two methods in
which structured cyber information present in CKGs can be used for downstream
tasks, with focus on explainability (reasoning and inference). The first
method involves creating sophisticated rules based on real data, and an
existing knowledge engine (rule base framework). The second method involves
using existing rules in downstream data-driven AI models and creating new
policies for cybersecurity (knowledge-guided models).

In the rule base framework, the ultimate goal is to create the strongest and
closest rules for target machines to protect them from any type of threats and
adversary behaviors. Rules can be simple to complex and they will be consumed
by any system or subsystem which needs protection. In the knowledge-guided
models, we aim to tackle novel cyber-threats or mutated versions of older
cyber-threats that do not exist in existing datasets for data-driven
experimentation. Exploratory modeling techniques, such as reinforcement
learning (RL), are needed to discover new adversaries that can further lead to
new defenses. In our experiments, we see that CKGs can guide these exploratory
learning strategies to be faster, more effective, and explainable.

Figure 1: Neuro Symbolic Rule Base framework for dynamic rule inference and
generation in cybersecurity

###  II-A Modeling Cyber-Events

A plethora of information is available in unstructured text for cybersecurity.
This information can come from various sources such as social media posts,
user-written blogs, or published reports from large organizations. Through our
research, we were able to extract this unstructured information and convert it
into structured knowledge [6]. To achieve this, we utilize semantic triples,
which consist of a subject-predicate-object relationship. In other words, when
encountering two entities in a text, we aimed to deduce the relationship
between them. We use BERT embeddings, as well as neural models, to generate
these semantic triples. By analyzing 474 technical reports and numerous
smaller technical posts, we construct a knowledge graph (KG) using these
semantic triples.

In addition, software companies release information concerning cybersecurity
threats to help consumers identify vulnerabilities in their products. This
data can be accessed through TAXII (Trusted Automated eXchange of Intelligence
Information) servers and integrated into a centralized KG.

We model our CKG ontology based on the concepts used in Structured Threat-
Intelligence Exchange (STIX), an industry standard for exchanging cyber-threat
information. We further enrich this ontology with system attribute concepts
that describe the malware behavior. The rule base framework and the knowledge-
guided models for cybersecurity can use this ontology for generating new rules
and policies, and use it in downstream models for explainable intrusion and
malware detection [7].

#### Reasoning and Inference Examples:

The semantic triples extracted from open-source text are asserted with CKG.
This CKG can be leveraged, not just by human security analysts but also by
other data-driven models. We can see some examples of how security analysts
can use this CKG to uncover important insights about malware using SPARQL
queries seen below.

SELECT ?x where { ?x a FusedCKG:Malware; FusedCKG:uses
FusedCKG:588f41bbc[......].}

This query asks what malware(s) match a particular hash value.

SELECT DISTINCT ?x ?y ?z WHERE { ?x a FusedKG:Malware. FusedKG:hasHash
[b9d......] FusedKG:uses ?y. ?y a FusedKG:Attack-Pattern. ?z
FusedKG:parameterchange FusedKG:increases_meanchange.}

The query asks what malware has a particular hash and the associated attack
pattern for that malware. It also asks what system parameters show an increase
when the malware is active. If a framework employs a KG where such dynamic
information, in the form of observations, are recorded, then an AI model can
leverage such structured knowledge in creating rules when defending against
attacks.

###  II-B Rule Base Framework

The rule base framework is one such architecture that employs existing AI
models and transforms them into rule generators. The AI models focus on the
knowledge of events, their interlinking with other events or malware in CKG,
and a method for generating hypotheses or rules for inference (see Figure 1).
The three broad sections of this framework are as follows:

  * •

Event Parsing Engine: The network block grants access to uncontrolled and
unregulated networks. The packets are classified and distinguished to organize
and handle data according to their specific types. Administrators, typically
network admins, establish administrative policies that contribute to the
control and dependability of network traffic. These policies assist in the
creation of effective rules for the system.

  * •

Symbolic Engine: The Knowledge Graph Constructor serves as a graph builder,
while the CKG stores contextual knowledge used to generate hypotheses. The CKG
Constructor ensures the provision of valid and accurate context knowledge. The
Observation Constructor produces clear and consistent observations derived
from network packets and admin policies for integration into the KG. Also, the
knowledge test and verification process will be applied to test and verify the
alignment (e.g., simply using similarity measures) of both knowledge datasets
and observations prior to their incorporation into the CKG.

  * •

Reasoning Engine: In a Neuro-Symbolic framework, the Knowledge Extractor
component retrieves hypotheses from a KG and combines them with observations
to form entailments. These entailments, organized with start and separator
tokens, are then processed by a Reasoning Engine composed of transformer-based
AI models (e.g., GPT). This engine generates rankings and selects the most
suitable hypothesis [8]. The Neuro-Symbolic rule base framework collects and
categorizes network packets for use in symbolic engines, generating hypotheses
through observation sequences and correlation scores. These hypotheses are
combined with the GPT-Family models to create cybersecurity rules, providing
improved accuracy, dependability, and explainable behavior in AI malware
detection, surpassing traditional rule-based systems like SNORT.

###  II-C Rules For Knowledge-guided RL in Cybersecurity

The semantic knowledge embodied in KGs has the potential to direct algorithms
like RL through rewards. While KGs encompass well-established facts regarding
cyber incidents, they might not possess details about emerging threats in
unpredictable environments. Because of the exploratory nature of RL
algorithms, new rules can be inferred based on the static knowledge in KG,
systems’ data, and rules extracted from the rule base framework [4]. The
reward-based learning in RL allows the intrinsic deep learning AI algorithm to
be expressive over the rules and explainable in prediction.

In the scenario of malware detection, we show that knowledge-guided RL sees
even faster convergence, better efficiency, and better response time [4]. The
acquired knowledge is incorporated into the exploration phase of the RL
algorithm and higher rewards are assigned to states that align with our
knowledge sources. Specifically, when we integrate prior knowledge, we observe
an 8% reduction in the average episode time. Additionally, we conduct
experiments with offline RL algorithms to examine the influence of prior
knowledge. We discover that incorporating prior knowledge leads to a 4% rise
in detection in three out of four malware families [9].

In another study by Piplai et al., we show that employing knowledge-guided
reinforcement learning (RL) with rules on extensive Packet Capture (pcap)
files, which ranged from 3 to 4 GB in size, leads to more accurate decision-
making in countering attackers. In a two-player zero-sum game setup, both the
attacker and defender were simulated using a knowledge-guided RL algorithm. By
incorporating informed actions based on this approach, we demonstrate a
remarkable preservation of 78% network availability, in comparison to a mere
25% when knowledge guidance was not utilized [7]. In both the studies, the
knowledge-guided RL strategy would preserve trace to knowledge sources for
providing explanations to analysts.

##  III Cybersecurity and Privacy with Knowledge-guided AI and Rule base
Framework

Ensuring privacy in AI models is vital, similar to the importance of
cybersecurity. AI models that unintentionally reveal personally identifiable
information (PII) during defense against attacks can leave systems vulnerable
to future unpredictable attacks. The challenge lies in training AI models to
handle various cyber attacks while optimizing response time and preserving
privacy. Reliable datasets for privacy-preserving training are scarce, as
organizations are hesitant to share data that contains PII or sensitive
insights.

To overcome this, generative modeling methods like generative adversarial
networks (GANs) can produce surrogate datasets that protect privacy while
remaining useful for learning tasks. We utilized conditional GANs (CGANs)
along with the t-closeness principle to preserve privacy in tabular data
containing continuous and discrete variables [10]. However, training standard
CGANs on sensitive data has limitations, as it struggles to model
conditionally continuous variables and can only repeat discrete variable
values seen in the original dataset.

To address these limitations, we propose a dual approach using privacy-
preserving deep learning models, combining generative modeling and symbolic
knowledge graphs (KGs) that express domain knowledge. Domain-specific KGs like
the Unified Cyber Ontology (UCO) can guide the generative model by providing
standardized information [11]. By querying the KG, the CGAN can be trained
using a mix of original dataset and discrete values, ensuring that the
generated dataset contains observed values and other alternatives from the KG.
This approach enhances the privacy preservation in generated datasets for
downstream machine learning tasks.

##  IV Conclusion and Future Work

This article discusses two main approaches of Neuro-Symbolic AI in
cybersecurity and privacy: (a) the rule base framework and (b) knowledge-
guided AI using RL. Both these approaches intrinsically involve partitioning
CKG for solving tasks in our concerned domains and ensuring that the AI system
is explainable. Our perspective is based on the noticeable improvements over
traditional AI systems. However, additional research endeavors are required to
develop reasoning engines in cybersecurity and privacy for optimal and
explainable decision-making, focusing on the users, such as security analysts.
The combination of rules and ML/RL models can further be improved by focusing
on which information is more beneficial to the model. The application of
transformers, in this case, by selecting specific paths in the graph based on
real data is a promising idea. We can also improve this with the help of graph
embeddings of state spaces appended to data representation during training
time.

Neuro-Symbolic AI has the potential to address critical challenges in the
future, especially in domains like privacy in healthcare, where there is a
growing demand for explainability. The techniques we explored can be expanded
to biomedicine, where medical treatments and procedures are confidential. When
limited to specific domains, GANs can only replicate treatment procedures
based on the information they were trained on. However, incorporating a
Biomedical KG can enhance the GAN model by providing a broader range of
knowledge [12]. By delving into such methods of knowledge infusion, we can not
only contribute to the cause and effectively tackle the limitations associated
with purely data-driven approaches.

## Authors

Aritran Piplai is an Assistant Professor at The University of Texas at El Paso
(UTEP), starting Fall 2023. He is advised by Prof. Anupam Joshi at The
University of Maryland, Baltimore County (UMBC). You can contact him at
<EMAIL_ADDRESS>
Anantaa Kotal is a Ph.D. candidate advised by Prof. Anupam Joshi. You can
contact her at<EMAIL_ADDRESS>
Seyedreza Mohseni is a Ph.D. student advised by Prof. Manas Gaur. You can
contact him at<EMAIL_ADDRESS>
Manas Gaur is an assistant professor in the CSEE Department, UMBC. You can
contact him at<EMAIL_ADDRESS>
Sudip Mittal is an assistant professor at the Department of Computer Science &
Engineering at Mississippi State University (MSU). You can contact him at
<EMAIL_ADDRESS>
Anupam Joshi is the Oros Family Professor in the CSEE Department, and the
Acting Dean of the College of Engineering and Information Technology at UMBC.
He is also the Director of the UMBC’s Center for Cybersecurity. You can
contact him at<EMAIL_ADDRESS>
## References

  * [1] A. Sheth, K. Roy, and M. Gaur, “Neurosymbolic artificial intelligence (why, what, and how),” IEEE Intelligent Systems, vol. 38, no. 3, pp. 56–62, 2023\.
  * [2] S. Bader and P. Hitzler, “Dimensions of neural-symbolic integration-a structured survey,” arXiv preprint cs/0511042, 2005.
  * [3] A. Joshi, N. Ramakrishman, E. N. Houstis, and J. R. Rice, “On neurobiological, neuro-fuzzy, machine learning, and statistical pattern recognition techniques,” IEEE Transactions on Neural Networks, vol. 8, no. 1, pp. 18–31, 1997.
  * [4] A. Piplai, P. Ranade, A. Kotal, S. Mittal, S. N. Narayanan, and A. Joshi, “Using knowledge graphs and reinforcement learning for malware analysis,” in 2020 IEEE International Conference on Big Data (Big Data), pp. 2626–2633, IEEE, 2020.
  * [5] S. Kambhampati, “Polanyi’s revenge and ai’s new romance with tacit knowledge,” Communications of the ACM, vol. 64, no. 2, pp. 31–32, 2021\.
  * [6] A. Piplai, S. Mittal, A. Joshi, T. Finin, J. Holt, and R. Zak, “Creating cybersecurity knowledge graphs from malware after action reports,” IEEE Access, vol. 8, pp. 211691–211703, 2020.
  * [7] A. Piplai, M. Anoruo, K. Fasaye, A. Joshi, T. Finin, and A. Ridley, “Knowledge guided two-player reinforcement learning for cyber attacks and defenses,” in 2022 21st IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 1342–1349, IEEE, 2022.
  * [8] D. Paul and A. Frank, “Social commonsense reasoning with multi-head knowledge attention,” arXiv preprint arXiv:2010.05587, 2020.
  * [9] A. Piplai, A. Joshi, T. Finin, et al., “Offline rl+ ckg: A hybrid ai model for cybersecurity tasks,” in AAAI Spring Symposium on Challenges Requiring the Combination of Machine Learning and Knowledge Engineering, 2023\.
  * [10] A. Kotal, A. Piplai, S. S. L. Chukkapalli, and A. Joshi, “Privetab: Secure and privacy-preserving sharing of tabular data,” in Proceedings of the 2022 ACM on International Workshop on Security and Privacy Analytics, pp. 35–45, 2022\.
  * [11] Z. Syed, A. Padia, T. Finin, L. Mathews, and A. Joshi, “Uco: A unified cybersecurity ontology,” UMBC Student Collection, 2016.
  * [12] L. Elluri, A. Piplai, A. Kotal, A. Joshi, and K. P. Joshi, “A policy-driven approach to secure extraction of covid-19 data from research papers,” Frontiers in big Data, vol. 4, p. 701966, 2021.


# Hypergraphs with Polynomial Representation:
Introducing $r$-splits

Mohammed Haddad, François Pitois,
Hamida Seba, Olivier Togni

###### Abstract

Inspired by the split decomposition of graphs and rank-width, we introduce the
notion of $r$-splits. We focus on the family of $r$-splits of a graph of order
$n$, and we prove that it forms a hypergraph with several properties. We prove
that such hypergraphs can be represented using only $\mathcal{O}(n^{r+1})$ of
its hyperedges, despite its potentially exponential number of hyperedges. We
also prove that there exist hypergraphs that need at least $\Omega(n^{r})$
hyperedges to be represented, using a generalization of set orthogonality.

##  1 Introduction

Graph decomposition is a major aspect of graph theory, it is mainly used to
run efficient algorithms and solve combinatorial problems on graphs that can
be well decomposed. A decomposition of a graph is an alternative way to
represent a graph, usually to highlight some structure in the graph. One large
family of decompositions is that of width decomposition, which aims at
decomposing a graph while minimizing a parameter, and such that this
decomposition can be used to run efficient algorithms under this
parameterization [12]. For example, tree-width decomposes a graph into a tree
structure that minimizes the size of some bags [16]; rank-width decomposes a
graph into an unrooted binary tree structure such that each edge represents a
cut of bounded rank over $\mathbb{F}_{2}$ [13, 15]; clique-width decomposes a
graph using some allowed operations between a bounded number of classes of
vertices [5]; and more recently, twin-width decomposes a graph by mimicking
cograph decomposition and minimizing the number of errors through the
decomposition [1]. Some other decompositions include modular decomposition
[11] and split decomposition [7, 6]. Here, we focus on _split decomposition_.
Informally, a split is a cut (or 2-partition) of a graph that looks like a
complete bipartite graph plus one stable set on each side of the cut.

Figure 1: An example of a split

It was improved in [10] to give birth to a decomposition that both represents
all the edges of a graph together with all its splits. The split decomposition
of a graph is a powerful tool. For example, it is used to recognize distance-
hereditary graphs [9]. However, there is a family of graphs, called _prime
graphs_ , that have no splits besides trivial ones. A trivial split is a split
with one part of size 0 or 1. It is called trivial because a 2-partition with
one part of size 0 or 1 is always a split by definition. This means that these
techniques cannot be used on prime graphs. The goal of this paper is to extend
this kind of decompositions to prime graphs by generalizing the definition of
a split as well as related concepts such as symmetric crossing families [7]
and orthogonality [4]. We take inspiration from the rank-width decomposition
to generalize splits into $r$-splits. The family of all splits of a graph has
the property of being a _symmetric crossing family_. Hence, our approach
consists in proving some properties about the family of $r$-splits of a graph.
We also generalize _orthogonality_. Usually, orthogonality is defined on
partitive families and modular decomposition [11, 4]. Since these notions are
very close to symmetric crossing families and split decomposition [2], we
allow ourselves to extend this notion and the associated vocabulary. In [4],
two sets of vertices are orthogonal (or non-overlapping) if one is included in
the other or if their intersection is empty. Orthogonality can be used to
compute the split decomposition in linear time [4]. In [8], two sets of
vertices are non-crossing if they are non-overlapping or if their union is the
set of all vertices of the graph. This notion was used to define and prove
properties of split decompositions in the first place [7]. In this paper, we
generalize the notion of being non-crossing, and give it the name
$r$-orthogonality. We use it to prove lower bounds, and we hope it could be
used to define a general $r$-split decomposition.

###  1.1 General definitions

A split can be defined as a cut of rank at most 1. In a natural way, we
introduce an $r$-split as a cut of rank at most $r$.

######  Definition 1.

Let $G=(V,E)$ be a graph. Let $(X,\overline{X})$ be a cut (i.e., a 2-partition
of $V$). The _rank_ of this cut, noted $\rho(X)$, is equal to the rank of the
adjacency matrix of $G$ where the rows are restricted to $X$, and the columns
are restricted to $\overline{X}$. This matrix is called the
$[X,\overline{X}]$-adjacency matrix of $G$, and is noted
$A(G)[X,\overline{X}]$. The rank is computed over the finite field of two
elements $\mathbb{F}_{2}$. The cut $(X,\overline{X})$ is an _$r$ -split_ if
$\rho(X)\leq r$. For convenience, we identify the cut $(X,\overline{X})$ with
the set of vertices $X$.

Since the rank of a matrix is always less than or equal to the number of its
rows and less than or equal to the number of its columns, we know that
$\rho(X)\leq\min(|X|,|\overline{X}|)$. This motivates us to focus on the case
where this inequality becomes an equality.

######  Definition 2.

A cut $(X,\overline{X})$ is said to be _trivial_ if
$\rho(X)=\min(|X|,|\overline{X}|)$.

In other words, the cut $(X,\overline{X})$ is trivial if the
$[X,\overline{X}]$-adjacency matrix of $G$ has full-rank in $\mathbb{F}_{2}$.

abcdefghi

$\displaystyle\begin{array}[]{cc}&\begin{array}[]{ccccccccc}a&b&c&d&e&f&g&h&i\end{array}\\\
\begin{matrix}a\\\ b\\\ c\\\ d\\\ e\\\ f\\\ g\\\ h\\\
i\end{matrix}&\begin{bmatrix}0&1&0&0&0&1&1&0&0\\\ 1&0&0&1&1&1&0&1&0\\\
0&0&0&0&1&0&1&1&0\\\ 0&1&0&0&0&0&0&0&0\\\ 0&1&1&0&0&0&0&0&0\\\
1&1&0&0&0&0&0&0&0\\\ 1&0&1&0&0&0&0&0&1\\\ 0&1&1&0&0&0&0&0&0\\\
0&0&0&0&0&0&1&0&0\end{bmatrix}\end{array}$

Figure 2: A graph and its adjacency matrix $\displaystyle
A(G)[\\{a,b,c,d,e\\},\\{f,g,h,i\\})]=\begin{array}[]{cc}&\begin{array}[]{ccccccccc}f&g&h&i\end{array}\\\
\begin{matrix}a\\\ b\\\ c\\\ d\\\ e\end{matrix}&\begin{bmatrix}1&1&0&0\\\
1&0&1&0\\\ 0&1&1&0\\\ 0&0&0&0\\\ 0&0&0&0\\\ \end{bmatrix}\end{array}$ Figure
3: The cut $(\\{a,b,c,d,e\\},\\{f,g,h,i\\})$ is a 2-split

######  Example 1.

In the graph of Figure 2, the set of vertices $\\{a,b,c,d,e\\}$ is a 2-split,
as the rank of the matrix given in Figure 3 is 2. Note that the rank is
computed over $\mathbb{F}_{2}$. This means that additions and multiplications
are done modulo 2. For example, the first three lines of the matrix ($[1\ \ 1\
\ 0\ \ 0]$, $[1\ \ 0\ \ 1\ \ 0]$ and $[0\ \ 1\ \ 1\ \ 0]$) sum to $[0\ \ 0\ \
0\ \ 0]$, since $1+1=0\mod 2$.

We focus on the set of $r$-splits of a graph for a fixed $r$. Function $\rho$
has several properties [15] which carry over to $r$-splits. The first one is a
very well-known property that comes directly from properties of the rank.

######  Lemma 1.

For all $X\subseteq V$, we have $\rho(X)\leq|X|$ and $\rho(X)=\rho(V\setminus
X)$.

Another useful property of $\rho$ is _submodularity_ , which is stated as
follows:

######  Lemma 2 ([15]).

For all $X,Y\subseteq V$, we have $\rho(X\cup Y)+\rho(X\cap
Y)\leq\rho(X)+\rho(Y)$.

Furthermore, we need the notion of _$r$ -rank connectivity_, which is defined
as follows:

######  Definition 3 ([14]).

A graph $G$ is _$r$ -rank connected_ if each $k$-split for $k<r$ is trivial.

This definition allows to fully characterize the trivial $r$-splits of a
graph. As a consequence of the definition of trivial $r$-split and $r$-rank
connectivity, we get the following lemma:

######  Lemma 3.

Let $G$ be a graph. If a set of vertices $X$ is a trivial $r$-split, then
$|X|\leq r$ or $|\overline{X}|\leq r$. If $G$ is $r$-rank connected, this
implication is an equivalence.

An another direct consequence of $r$-rank connectivity is this lemma:

######  Lemma 4.

Let $G$ be an $r$-rank connected graph. Let $X$ be a set of vertices such that
$r\leq|X|\leq|V|-r$. Then $\rho(X)\geq r$.

###### Proof.

Suppose for a contradiction that $\rho(X)<r$. This means that $X$ is a
$(r-1)$-split. By $r$-rank connectivity, $X$ is trivial. By definition of
being trivial, $\rho(X)=\min(|X|,|\overline{X}|)$. Hence,
$\min(|X|,|\overline{X}|)<r$, which contradicts the fact that
$r\leq|X|\leq|V|-r$. ∎

Combined with submodularity, we get the following lemma:

######  Lemma 5.

If $X$ and $Y$ are two $r$-splits of an $r$-rank connected graph $G$ and if
$|X\cap Y|\geq r$, then $X\cup Y$ is also an $r$-split.

###### Proof.

First, if $|X\cup Y|\leq r$ or $|\overline{X\cup Y}|\leq r$, then $\rho(X\cup
Y)\leq\min(|X\cup Y|,|\overline{X\cup Y}|)\leq r$, meaning that $X\cup Y$ is
an $r$-split.

Then, if $|\overline{X\cap Y}|\leq r$, it means that $|\overline{X\cup
Y}|\leq|\overline{X\cap Y}|\leq r$, so we are in the same case as previously,
and $X\cup Y$ is an $r$-split.

Otherwise, the number of vertices of $X\cup Y$ and $X\cap Y$ is both between
$r$ and $|V|-r$. Hence, by $r$-rank connectivity of $G$, $\rho(X\cup Y)\geq r$
and $\rho(X\cap Y)\geq r$. Since $X$ and $Y$ are $r$-splits, we know that
$\rho(X)\leq r$ and $\rho(Y)\leq r$. By submodularity, we deduce that
$\rho(X\cup Y)+\rho(X\cap Y)\leq 2r$. All in all, $\rho(X\cup Y)=\rho(X\cap
Y)=r$, which concludes the proof. ∎

This property is powerful as it organizes the set of all $r$-splits of a
graph. In fact, we show in Section 2 that given an $r$-rank connected graph
$G$ with $n$ vertices, there exists a subset of $r$-splits of size
$\mathcal{O}(n^{r+1})$ that fully characterizes the whole set of $r$-splits.

###  1.2 Hypergraph of $r$-splits

Let $G=(V,E)$ be an $r$-rank connected graph with vertex set $V=[n]$. Let us
denote by $H_{r}(G)$ the hypergraph whose set of vertices is the same as $G$,
namely $V(H_{r}(G))=[n]$, and whose set of hyperedges $\mathcal{E}$ is the set
of all $r$-splits of $G$. From Lemmas 1 and 2, we know that $H_{r}(G)$
satisfies the following properties: (1) if $A\in\mathcal{E}$, then $V\setminus
A\in\mathcal{E}$; (2) for every set of vertices $X\subseteq V$, if $|X|\leq
r$, then $X\in\mathcal{E}$; (3) if $A,B\in\mathcal{E}$ and $|A\cap B|\geq r$,
then $A\cup B\in\mathcal{E}$. Therefore, we consider hypergraphs that satisfy
these properties.

Please note that in this paper, since every hypergraph has $V=[n]$ as set of
vertices, we identify a hypergraph $H=(V,\mathcal{E})$ with its set of
hyperedges $\mathcal{E}$. This means, for example, that we write
$A\in\mathcal{E}$ or $A\in H$ to denote a hyperedge $A$ of $H$, and we can
denote by $\\{A,B\\}$ the hypergraph with set of vertices $V=[n]$ and set of
hyperedges $\\{A,B\\}$.

######  Definition 4.

Let $\mathds{K}_{r}(n)$ be the class of hypergraphs with set of vertices
$V=[n]$ and set of hyperedges $\mathcal{E}$ that satisfies:

  * $\boldsymbol{R}_{{{\,\leq}}}:$

For every set of vertices $X\subseteq V$, if $|X|\leq r$, then
$X\in\mathcal{E}$.

  * $\boldsymbol{R}_{{{\,\neg}}}:$

If $A\in\mathcal{E}$, then $V\setminus A\in\mathcal{E}$.

  * $\boldsymbol{R}_{{\,\cup}}:$

If $A,B\in\mathcal{E}$ and $|A\cap B|\geq r$, then $A\cup B\in\mathcal{E}$.

By combining the three above rules, we can deduce other similar properties.

######  Lemma 6.

Let $H\in\mathds{K}_{r}(n)$ be a hypergraph with set of vertices $V=[n]$ and
set of hyperedges $\mathcal{E}$. Then $H$ satisfies:

  * $\boldsymbol{P}_{{{\geq}}}:$

For every set of vertices $X\subseteq V$, if $|X|\geq n-r$, then
$X\in\mathcal{E}$.

  * $\boldsymbol{P}_{{{\cap}}}:$

If $A,B\in\mathcal{E}$ and $|\overline{A\cup B}|\geq r$, then $A\cap
B\in\mathcal{E}$.

  * $\boldsymbol{P}_{{\setminus}}:$

If $A,B\in\mathcal{E}$ and $|A\setminus B|\geq r$, then $B\setminus
A\in\mathcal{E}$.

###### Proof.

Property $\boldsymbol{P}_{{{\geq}}}$ is obtained by combining rules
$\boldsymbol{R}_{{{\,\leq}}}$ and $\boldsymbol{R}_{{{\,\neg}}}$, while
properties $\boldsymbol{P}_{{{\cap}}}$ and $\boldsymbol{P}_{{\setminus}}$ are
obtained by combining rule $\boldsymbol{R}_{{\,\cup}}$ and rule
$\boldsymbol{R}_{{{\,\neg}}}$ multiple times.

First, let us prove property $\boldsymbol{P}_{{{\cap}}}$: Let
$A,B\in\mathcal{E}$ such that $|\overline{A\cup B}|\geq r$. By rule
$\boldsymbol{R}_{{{\,\neg}}}$, $\overline{A}\in\mathcal{E}$ and
$\overline{B}\in\mathcal{E}$. We know that
$|\overline{A}\cap\overline{B}|=|\overline{A\cup B}|\geq r$, so by rule
$\boldsymbol{R}_{{\,\cup}}$, $\overline{A}\cup\overline{B}=\overline{A\cap
B}\in\mathcal{E}$. Finally, by applying rule $\boldsymbol{R}_{{{\,\neg}}}$
again to $\overline{A\cap B}\in\mathcal{E}$, we get that $A\cap
B\in\mathcal{E}$.

In a similar way, we prove property $\boldsymbol{P}_{{\setminus}}$: Let
$A,B\in\mathcal{E}$ such that $|A\setminus B|\geq r$. By rule
$\boldsymbol{R}_{{{\,\neg}}}$, $\overline{B}\in\mathcal{E}$. We know that
$|A\cap\overline{B}|=|A\setminus B|\geq r$, so by rule
$\boldsymbol{R}_{{\,\cup}}$, $A\cup\overline{B}=\overline{B\setminus
A}\in\mathcal{E}$. Finally, by applying rule $\boldsymbol{R}_{{{\,\neg}}}$
again to $\overline{B\setminus A}\in\mathcal{E}$, we get that $B\setminus
A\in\mathcal{E}$. ∎

We note that for each $r$-rank connected graph $G$ of order $n$, the
hypergraph $H_{r}(G)$ made of all $r$-splits of $G$ belongs to the class
$\mathds{K}_{r}(n)$.

The class $\mathds{K}_{r}(n)$ has the property of being a _closure system_.
This means that: (1) the hypergraph with every possible hyperedge belongs to
$\mathds{K}_{r}(n)$; (2) if we take two hypergraphs
$H_{1},H_{2}\in\mathds{K}_{r}(n)$, then the intersection of $H_{1}$ and
$H_{2}$ is also in $\mathds{K}_{r}(n)$. We recall that the intersection of two
hypergraphs $H_{1}$ and $H_{2}$ is the hypergraph whose vertex set is the same
as $H_{1}$ and $H_{2}$ (namely, $[n]$), and whose hyperedge set is the
intersection of the set of hyperedges of $H_{1}$ and $H_{2}$.

######  Lemma 7.

The class $\mathds{K}_{r}(n)$ is a closure system.

###### Proof.

First, it is trivial that the hypergraph with all possible hyperedges
satisfies Definition 4, meaning that this hypergraph belongs to
$\mathds{K}_{r}(n)$. Secondly, let $H_{1},H_{2}\in\mathds{K}_{r}(n)$ and let
us prove that $H_{1}\cap H_{2}\in\mathds{K}_{r}(n)$. To this purpose, let
$A,B$ be hyperedges of $H_{1}\cap H_{2}$ and let $X$ be a subset of vertices
of $V$, and let us prove that they satisfy rules
$\boldsymbol{R}_{{{\,\leq}}},\boldsymbol{R}_{{{\,\neg}}},\boldsymbol{R}_{{\,\cup}}$
of Definition 4:

  * •

For $\boldsymbol{R}_{{{\,\leq}}}$: If $|X|\leq r$, then $X$ is a hyperedge of
$H_{1}$ as $H_{1}\in\mathds{K}_{r}(n)$, and $X$ is a hyperedge of $H_{2}$ as
$H_{2}\in\mathds{K}_{r}(n)$. Hence, $X$ is a hyperedge of $H_{1}\cap H_{2}$.

  * •

For $\boldsymbol{R}_{{{\,\neg}}}$: As $A$ is a hyperedge of $H_{1}\cap H_{2}$,
$A$ is a hyperedge of $H_{1}$, and $V\setminus A$ is also a hyperedge of
$H_{1}$ as $H_{1}\in\mathds{K}_{r}(n)$. For the same reason, $V\setminus A$ is
a hyperedge of $H_{2}$. Hence, $V\setminus A$ is a hyperedge of $H_{1}\cap
H_{2}$.

  * •

For $\boldsymbol{R}_{{\,\cup}}$: If $|A\cap B|\geq r$, then $A\cup B$ is a
hyperedge of $H_{1}$ as $H_{1}\in\mathds{K}_{r}(n)$. With the same argument,
$A\cup B$ is a hyperedge of $H_{2}$. Hence, $A\cup B$ is a hyperedge of
$H_{1}\cap H_{2}$.

In conclusion, $H_{1}\cap H_{2}$ fully satisfies Definition 4, proving that
$H_{1}\cap H_{2}\in\mathds{K}_{r}(n)$. ∎

Having a closure system is convenient, as it induces a _closure operator_ [3].
In our case, the closure operator is defined as follows:

######  Definition 5.

Let $H$ be a hypergraph with vertex set $V=[n]$. The _closure_ of $H$ in
$\mathds{K}_{r}(n)$, denoted ${<\\!\\!H\\!\\!>_{r}}$, is the hypergraph
defined as the intersection of all hypergraphs that contain $H$ and that
belong to $\mathds{K}_{r}(n)$. A hypergraph $H$ satisfying
${<\\!\\!H\\!\\!>_{r}}=H$ is called a _closed hypergraph for
${<\\!\\!\cdot\\!\\!>_{r}}$_, an $r$-closed hypergraph, or simply a closed
hypergraph when there is no ambiguity.

In other words, a set of vertices $A$ is a hyperedge of
${<\\!\\!H\\!\\!>_{r}}$ if and only if $A$ is a hyperedge of every hypergraph
of $\mathds{K}_{r}(n)$ that has $H$ as a sub-hypergraph. To better understand
the closure operator ${<\\!\\!\cdot\\!\\!>_{r}}$, let us see an example.

######  Example 2.

Let $n=8$ and $r=2$. Let $H$ be the hypergraph with vertex set $V=[n]$ and
hyperedge set $\mathcal{E}=\\{\\{1,2,3\\},\\{2,3,4,5\\}\\}$. Then, the
hypergraph ${<\\!\\!H\\!\\!>_{r}}$ is made of the following hyperedges:

  * •

all sets made of 0, 1 or 2 vertices, according to
$\boldsymbol{R}_{{{\,\leq}}}$,

  * •

all sets made of 6, 7 or 8 vertices, according to $\boldsymbol{P}_{{{\geq}}}$,

  * •

$\\{1,2,3\\}$ and $\\{2,3,4,5\\}$, because $H$ must be a sub-hypergraph of
${<\\!\\!H\\!\\!>_{r}}$,

  * •

$\\{4,5,6,7,8\\}$ and $\\{1,6,7,8\\}$, according to
$\boldsymbol{R}_{{{\,\neg}}}$,

  * •

$\\{1,2,3,4,5\\}$ according to $\boldsymbol{R}_{{\,\cup}}$,

  * •

$\\{6,7,8\\}$ according to $\boldsymbol{R}_{{{\,\neg}}}$ applied to
$\\{1,2,3,4,5\\}$.

This list proves that ${<\\!\\!H\\!\\!>_{r}}$ must contain all these
hyperedges. To prove that ${<\\!\\!H\\!\\!>_{r}}$ is indeed equal to this set
of hyperedges, one must prove that this whole set of hyperedges satisfies
rules $\boldsymbol{R}_{{{\,\leq}}}$, $\boldsymbol{R}_{{{\,\neg}}}$ and
$\boldsymbol{R}_{{\,\cup}}$.

Just like any closure operator, ${<\\!\\!\cdot\\!\\!>_{r}}$ is _extensive_
(for any hypergraph $H$, $H\subseteq{<\\!\\!H\\!\\!>_{r}}$), _monotone_ (for
any hypergraphs $H,H^{\prime}$, if $H\subseteq H^{\prime}$, then
${<\\!\\!H\\!\\!>_{r}}\subseteq{<\\!\\!H^{\prime}\\!\\!>_{r}}$), and
_idempotent_ (for any $H\in\mathds{K}_{r}(n)$, we have
${<\\!\\!H\\!\\!>_{r}}=H$) [3]. We can now use ${<\\!\\!\cdot\\!\\!>_{r}}$ to
formalize one of the main theorems of this paper.

######  Theorem 1.

Given an $r$-rank connected graph $G$ with $n$ vertices, there exists a
hypergraph $H$ with $\mathcal{O}(n^{r+1})$ hyperedges such that
${<\\!\\!H\\!\\!>_{r}}=H_{r}(G)$.

Section 2 is dedicated to the proof of this theorem.

###  1.3 Complementary results

The closure operator ${<\\!\\!\cdot\\!\\!>_{r}}$ is the main tool used to
represent hypergraphs through this paper. In this subsection, we study it in
more detail. To do so, we first introduce a related closure operator, which in
turn defines a relation between the hyperedges of a hypergraph.

######  Definition 6.

Let $\mathds{K}_{r}^{\circ}(n)$ be the class of hypergraphs with set of
vertices $V=[n]$ and set of hyperedges $\mathcal{E}$ that satisfies:

  * $\boldsymbol{R}_{{{\,\leq}}}:$

For every set of vertices $X\subseteq V$, if $|X|\leq r$, then
$X\in\mathcal{E}$.

  * $\boldsymbol{R}_{{{\,\neg}}}:$

If $A\in\mathcal{E}$, then $V\setminus A\in\mathcal{E}$.

The definition of $\mathds{K}_{r}^{\circ}(n)$ is similar to the definition of
$\mathds{K}_{r}(n)$. The only difference is that the rule
$\boldsymbol{R}_{{\,\cup}}$ is removed. In a very similar way, we can prove
that $\mathds{K}_{r}^{\circ}(n)$ is a closure system, and thus we can define
the corresponding closure operator ${<\\!\\!\cdot\\!\\!>^{\circ}_{r}}$. Now,
we define $r$-orthogonal hyperedges as follows:

######  Definition 7.

Let $A$ and $B$ be two hyperedges of a hypergraph $H$. Hyperedges $A$ and $B$
are $r$-orthogonal if
${<\\!\\!\\{A,B\\}\\!\\!>_{r}}={<\\!\\!\\{A,B\\}\\!\\!>^{\circ}_{r}}$. Here,
recall that $\\{A,B\\}$ denotes the hypergraph with vertex set $[n]$ and
hyperedge set $\\{A,B\\}$.

Section 3 is dedicated to the study of $r$-orthogonality. This relation
introduces a class of hypergraphs called $r$-cross-free hypergraphs, defined
as follows:

######  Definition 8.

A hypergraph is $r$-cross-free if each pair of hyperedges of $H$ are
$r$-orthogonal.

Such hypergraphs are interesting as they have a few number of hyperedges, but
each of them is important regarding the closure operator
${<\\!\\!\cdot\\!\\!>_{r}}$.

######  Theorem 2.

Let $H$ be a $r$-cross-free hypergraph with $n$ vertices. Then the number of
hyperedges of $H$ is at most $\mathcal{O}(n^{r+1})$.

######  Theorem 3.

There exists a hypergraph $H$ with $n$ vertices that is both $r$-cross-free
and $r$-closed such that for all sub-hypergraph $H^{\prime}$ of $H$ satisfying
${<\\!\\!H^{\prime}\\!\\!>_{r}}=H$, the number of hyperedges of $H^{\prime}$
is at least $\Omega(n^{r})$.

Section 4 is dedicated to proving these two theorems.
Theorems 1 and 3 together prove that some $r$-closed hypergraphs need at least
$\Omega(n^{r})$ hyperedges to be represented, while each $r$-closed hypergraph
needs at most $\mathcal{O}(n^{r+1})$ hyperedges to be represented.

##  2 Essential hyperedges and polynomial representation

The sketch of the proof of Theorem 2 is as follows: Given a hypergraph
$H\in\mathds{K}_{r}$, we define a notion of essential hyperedge of $H$, such
that the sub-hypergraph $H^{\prime}$ made of all essential hyperedges has a
closure equal to $H$. By being careful with the definition of essential
hyperedges, we ensure that there is no more than $\mathcal{O}(n^{r+1})$
essential hyperedges. This allows us to conclude.

This is done in three steps: First, we define what an essential hyperedge is.
To do so, we need some lemmas that ensure that this notion is well-defined.
Then, we prove that each hyperedge of the original hypergraph $H$ can be
obtained using essential hyperedges. Formally, this means that for each
hyperedge $A$ of $H$, there exists a hypergraph $H^{\prime}$ made of some
essential hyperedges such that $A$ is a hyperedge of
${<\\!\\!H^{\prime}\\!\\!>_{r}}$. Finally, this allows us to prove that the
hypergraph $H^{\prime}$ made of all essential hyperedges satisfies
$H\subseteq{<\\!\\!H^{\prime}\\!\\!>_{r}}$. Besides, since $H^{\prime}$ is a
subgraph of $H$, we have an equality. Hence, we have a result for every
hypergraph in $\mathds{K}_{r}$. Since $H_{r}(G)\in\mathds{K}_{r}$, we can
conclude.

###  2.1 Definition of essential hyperedges

We want to define essential hyperedges of a hypergraph $H\in\mathds{K}_{r}$
such that, using them together with rules $\boldsymbol{R}_{{{\,\leq}}}$,
$\boldsymbol{R}_{{{\,\neg}}}$, and $\boldsymbol{R}_{{\,\cup}}$, we can deduce
every other hyperedge of $H$. Rule $\boldsymbol{R}_{{{\,\neg}}}$ states that
if a hyperedge $A$ is in $H$, then its complement $\overline{A}$ is also in
$H$. This means that only half of the hyperedges are useful and that the other
half can be obtained using rule $\boldsymbol{R}_{{{\,\neg}}}$. For instance,
it motivates the fact that only hyperedges $A$ with a number of edges
satisfying $|A|\leq n/2$ should be essential.

Our idea is to define a function $\varphi_{H}$ as follows. We pick a set $X$
of ${r+1}$ vertices. If there exists a hyperedge $A$ of $H$ that contains $X$
such that $|A|\leq n/2$, then we map $X$ to the smallest such hyperedge (for
instance, either $A$ or a subset of $A$). Otherwise, it means that every
hyperedge of $H$ that contains $X$ has more than $n/2$ vertices. We decide to
map $X$ to nothing in this case and to remove $X$ from the domain of
$\varphi_{H}$.

First, we need to prove that, under some conditions, the intersection of two
hyperedges $A$ and $B$ of a hypergraph $H\in\mathds{K}_{r}(n)$ is also in $H$.
In $\mathds{K}_{r}(n)$, we have property $\boldsymbol{P}_{{{\cap}}}$ that
states that if $A$ and $B$ are two hyperedges of $H$ such that
$|\overline{A\cup B}|\geq r$, then $A\cap B$ is also a hyperedge of $H$. We
show that we can remove the condition $|\overline{A\cup B}|\geq r$ if we
consider only hyperedges with less than $n/2$ vertices.

######  Lemma 8.

Let $H\in\mathds{K}_{r}(n)$. Let $A$ and $B$ be two hyperedges of $H$ such
that $|A|\leq n/2$ and $|B|\leq n/2$. Then $A\cap B$ is a hyperedge of $H$.

###### Proof.

If $|A\cap B|\leq r$, then $A\cap B$ is a hyperedge of $H$ by rule
$\boldsymbol{R}_{{{\,\leq}}}$. Otherwise, we have $|A\cap B|>r$. Hence,
$|A\cup B|=|A|+|B|-|A\cap B|\leq n/2+n/2-r\leq n-r$. This means that
$|\overline{A\cup B}|\geq r$. By property $\boldsymbol{P}_{{{\cap}}}$, $A\cap
B$ is a hyperedge of $H$. ∎

We extend this lemma to more than two hyperedges by induction:

######  Corollary 1.

Let $H\in\mathds{K}_{r}(n)$. Let $X\subseteq V$ be a set of vertices. Let
$\mathcal{A}$ be the set of all hyperedges $A$ of $H$ satisfying $X\subseteq
A$ and $|A|\leq n/2$. Then, if $\mathcal{A}$ is nonempty, the intersection of
all hyperedges of $\mathcal{A}$ is also a hyperedge of $\mathcal{A}$.

We are now ready to define the notion of essential hyperedge.

######  Definition 9.

Let $H\in\mathds{K}_{r}(n)$. An _essential hyperedge_ is a hyperedge of the
form $\varphi_{H}(X)$ for some set of vertices $X\subseteq V$, where the
function $\varphi_{H}$ is defined as follows. It is a function that takes as
input a set of vertices $X\subseteq V$ of size $|X|=r+1$ and that returns
either:

  * •

A hyperedge $A$ of $H$ such that $X\subseteq A$, $|A|\leq n/2$, and such that
$A$ is the smallest such hyperedge.

  * •

A guaranty that each hyperedge $A$ of $H$ that contains $X$ has size
$|A|>n/2$. In this case, $\varphi_{H}(X)$ is undefined, and $X$ is not in the
input space of $\varphi_{H}$.

This function is well-defined, as the notion of “smallest such hyperedge”
exists thanks to Corollary 1.

###  2.2 Each hyperedge is the union of some essential hyperedges

In this section, we prove that if $A$ is a hyperedge of $H$, then there exists
a hypergraph $H^{\prime}$ made of some essential hyperedges such that $A$ is a
hyperedge of ${<\\!\\!H^{\prime}\\!\\!>_{r}}$. To prove this, we discuss the
number of vertices of the hyperedge $A$. The main case is the case where
$r+1\leq|A|\leq n/2$. Informally, the fact the $|A|\geq r+1$ guarantees that
we can pick a set of vertices $X\subseteq A$ of size $|X|=r+1$ to apply
$\varphi_{H}$ to; and the fact that $|A|\leq n/2$ guarantees that
$\varphi_{H}(X)$ is defined, meaning that we have at least one essential
hyperedge $\varphi_{H}(X)$ contained in $A$. The other cases (namely when
$|A|\leq r$ and when $|A|>n/2$) are treated easily afterward.

First, we need a lemma that states that the union of some essential hyperedges
of $H$ is a hyperedge (not necessarily essential) of $H$, providing some
conditions. To keep it as general as possible, we do not ask for the
hyperedges to be essential, but rather we just ask them to belong to a common
set of size at most $n/2$ vertices.

######  Lemma 9.

Let $H\in\mathds{K}_{r}(n)$ and let $A_{1},\ldots,A_{k}$ be $k$ hyperedges of
$H$. If for every $1\leq i<k$, we have $|A_{i}\cap A_{i+1}|\geq r$, then
$\bigcup_{i=1}^{k}A_{i}$ is a hyperedge of $H$.

###### Proof.

We prove it by induction. For $k=1$, the lemma is trivial, and for $k=2$, it
corresponds to $\boldsymbol{R}_{{\,\cup}}$. Suppose the lemma is true for $k$
hyperedges, and let us prove it for $k+1$. Let $A^{\prime}=A_{1}\cup\ldots\cup
A_{k}$. $A^{\prime}$ is a hyperedge of $H$ by induction. It remains to prove
that $A^{\prime}\cup A_{k+1}$ is a hyperedge of $H$. Since $A_{k}\subseteq
A^{\prime}$, we have $A_{k}\cap A_{k+1}\subseteq A^{\prime}\cap A_{k+1}$,
meaning that $|A^{\prime}\cap A_{k+1}|\geq|A_{k}\cap A_{k+1}|\geq r$. Finally,
by rule $\boldsymbol{R}_{{\,\cup}}$, $A^{\prime}\cup A_{k+1}$ is a hyperedge
of $H$. ∎

With this lemma, we can prove the first case of this section, namely that each
hyperedge $A$ with a size satisfying $r+1\leq|A|\leq n/2$ can be written as a
union of essential hyperedges.

######  Corollary 2.

Let $H\in\mathds{K}_{r}(n)$. Let $A$ be a hyperedge of $H$ such that
$r+1\leq|A|\leq n/2$. Then there exists a list of sets of vertices
$X_{1},\ldots,X_{k}$ and a hypergraph $H^{\prime}$ such that the hyperedges of
$H^{\prime}$ are exactly $\varphi_{H}(X_{1}),\ldots,\varphi_{H}(X_{k})$ and
such that $A\in{<\\!\\!H^{\prime}\\!\\!>_{r}}$.

###### Proof.

Let us write $A$ as $A=\\{u_{1},\ldots,u_{|A|}\\}$. For $1\leq i\leq|A|-r$,
let $X_{i}=\\{u_{i},\ldots,u_{i+r}\\}$. For each $X_{i}$, we have
$|X_{i}|=r+1$. Furthermore, $\varphi_{H}(X_{i})$ is not undefined, as there
exists a hyperedge in $H$ that contains $X_{i}$ and that has at most $n/2$
vertices, namely $A$.

Let us prove that $A\in{<\\!\\!H^{\prime}\\!\\!>_{r}}$ by applying Lemma 9
with hypergraph ${<\\!\\!H^{\prime}\\!\\!>_{r}}$ and the $k$ hyperedges
$\varphi_{H}(X_{1}),\ldots,\varphi_{H}(X_{k})$. To be allowed to apply this
lemma, we have to check that for all $i$,
$|\varphi_{H}(X_{i})\cap\varphi_{H}(X_{i+1})|\geq r$. This is true as
$X_{i}\subseteq\varphi_{H}(X_{i})$ and as $X_{i}\cap X_{i+1}=\\{u_{i+1},\ldots
u_{i+r}\\}$, which is a set of $r$ vertices. Hence,
$|\varphi_{H}(X_{i})\cap\varphi_{H}(X_{i+1})|\geq|X_{i}\cap X_{i+1}|=r$.

Therefore, $A\in{<\\!\\!H^{\prime}\\!\\!>_{r}}$. ∎

As a consequence, using the rule $\boldsymbol{R}_{{{\,\neg}}}$, we can deal
with the case $n/2\leq|A|\leq n-r-1$:

######  Corollary 3.

Let $H\in\mathds{K}_{r}(n)$. Let $A$ be a hyperedge of $H$ such that
$n/2\leq|A|\leq n-r-1$. Then there exists a list of sets of vertices
$X_{1},\ldots,X_{k}$ and a hypergraph $H^{\prime}$ such that the hyperedges of
$H^{\prime}$ are exactly $\varphi_{H}(X_{1}),\ldots,\varphi_{H}(X_{k})$ and
such that $A\in{<\\!\\!H^{\prime}\\!\\!>_{r}}$.

###### Proof.

Let $B=\overline{A}$. Then $r+1\leq|B|\leq n/2$. By Corollary 2, there exists
a list of sets of vertices $X_{1},\ldots,X_{k}$ and a hypergraph $H^{\prime}$
such that the hyperedges of $H^{\prime}$ are exactly
$\varphi_{H}(X_{1}),\ldots,\varphi_{H}(X_{k})$ and such that
$B\in{<\\!\\!H^{\prime}\\!\\!>_{r}}$. By rule $\boldsymbol{R}_{{{\,\neg}}}$,
$\overline{B}\in{<\\!\\!H^{\prime}\\!\\!>_{r}}$. ∎

Finally, it remains the cases where $|A|\leq r$ or $|A|\geq n-r$:

######  Lemma 10.

Let $H\in\mathds{K}_{r}(n)$. Let $A$ be a hyperedge of $H$ such that $|A|\leq
r$ or $|A|\geq n-r$. Then $A\in{<\\!\\!\emptyset\\!\\!>_{r}}$, where
$\emptyset$ represents the hypergraph with no hyperedge.

###### Proof.

If $|A|\leq r$, by applying rule $\boldsymbol{R}_{{{\,\leq}}}$ to the empty
hypergraph $\emptyset$, we have that $A\in{<\\!\\!\emptyset\\!\\!>_{r}}$. If
$|A|\geq n-r$, we apply property $\boldsymbol{P}_{{{\geq}}}$ to the empty
hypergraph $\emptyset$ to obtain that $A\in{<\\!\\!\emptyset\\!\\!>_{r}}$. ∎

All in all, given a hypergraph $H\in\mathds{K}_{r}(n)$ and a hyperedge $A$ of
$H$, there exists a list (that may be empty) of sets of vertices
$X_{1},\ldots,X_{k}$ and a hypergraph $H^{\prime}$ such that hyperedges of
$H^{\prime}$ are exactly $\varphi_{H}(X_{1}),\ldots,\varphi_{H}(X_{k})$ and
such that $A\in{<\\!\\!H^{\prime}\\!\\!>_{r}}$.

###  2.3 Polynomial representation

To finally prove Theorem 1, it remains to apply the results of Section 2.2 to
each hyperedge of the hypergraph $H$.

######  Lemma 11.

Given a hypergraph $H\in\mathds{K}_{r}(n)$, there exists a list of sets of
vertices $X_{1},\ldots,X_{k}$ and a hypergraph $H^{\prime}$ such that the
hyperedges of $H^{\prime}$ are exactly
$\varphi_{H}(X_{1}),\ldots,\varphi_{H}(X_{k})$ and such that
$H={<\\!\\!H^{\prime}\\!\\!>_{r}}$.

###### Proof.

For each hyperedge $A_{i}$ of $H$, we know that there exists a hypergraph
$H_{i}$ such that hyperedges of $H_{i}$ are of the form
$\varphi_{H}(X_{i_{1}}),\ldots,\varphi_{H}(X_{i_{k}})$ and such that
$A_{i}\in{<\\!\\!H_{i}\\!\\!>_{r}}$. Let $H^{\prime}$ be the union of all
$H_{i}$, and let us prove that $H={<\\!\\!H^{\prime}\\!\\!>_{r}}$.

First, we have:

$\displaystyle
H=\bigcup_{i}\\{A_{i}\\}\subseteq\bigcup_{i}{<\\!\\!H_{i}\\!\\!>_{r}}\mathop{\subseteq}\limits_{(1)}{<\\!\\!H^{\prime}\\!\\!>_{r}}.$

Inclusion $(1)$ is due to the monotone property of the closure operator
${<\\!\\!\cdot\\!\\!>_{r}}$ applied to $H_{i}$ and $H^{\prime}$ for all $i$.
This proves that for every $i$,
${<\\!\\!H_{i}\\!\\!>_{r}}\subseteq{<\\!\\!H^{\prime}\\!\\!>_{r}}$. Hence, the
union of ${<\\!\\!H_{i}\\!\\!>_{r}}$ is included in
${<\\!\\!H^{\prime}\\!\\!>_{r}}$.

Furthermore,

$\displaystyle
H^{\prime}=\bigcup_{i}H_{i}\mathop{\subseteq}\limits_{(2)}\bigcup_{i}H=H.$

Inclusion $(2)$ is due to the extensive property of the closure operator
${<\\!\\!\cdot\\!\\!>_{r}}$.

Hence, by the monotone property of the closure operator
${<\\!\\!\cdot\\!\\!>_{r}}$,
${<\\!\\!H^{\prime}\\!\\!>_{r}}\subseteq{<\\!\\!H\\!\\!>_{r}}$, and
${<\\!\\!H^{\prime}\\!\\!>_{r}}\subseteq H$ since $H\in\mathds{K}_{r}(n)$.

All in all, by double inclusion, $H={<\\!\\!H^{\prime}\\!\\!>_{r}}$. ∎

######  Corollary 4.

Given a hypergraph $H\in\mathds{K}_{r}(n)$, there exists a hypergraph
$H^{\prime}$ such that the number of hyperedges of $H^{\prime}$ is
$\mathcal{O}(n^{r+1})$ and such that $H={<\\!\\!H^{\prime}\\!\\!>_{r}}$.

###### Proof.

By applying Lemma 11, there exists $H^{\prime}$ made of hyperedges of the form
$\varphi_{H}(X_{i})$. The number of such hyperedges is $\mathcal{O}(n^{r+1})$
as every $X_{i}$ is made of $r+1$ vertices. ∎

Now, we can prove Theorem 1. Let us recall it.

######  Theorem 1.

Given an $r$-rank connected graph $G$ with $n$ vertices, there exists a
hypergraph $H$ with $\mathcal{O}(n^{r+1})$ hyperedges such that
${<\\!\\!H\\!\\!>_{r}}=H_{r}(G)$.

###### Proof.

Let $G$ be an $r$-rank connected graph $G$ with $n$ vertices. Then,
$H_{r}(G)\in\mathds{K}_{r}(n)$. By Corollary 4, there exists a hypergraph
$H^{\prime}$ such that the number of hyperedges of $H^{\prime}$ is
$\mathcal{O}(n^{r+1})$ and such that
$H_{r}(G)={<\\!\\!H^{\prime}\\!\\!>_{r}}$. ∎

##  3 Orthogonal hyperedges

In this section, we generalize the notion of $r$-orthogonal hyperedges. This
notion was introduced in the case $r=1$ under the name “non-crossing
hyperedges” [7]. We prefer to use the term “orthogonal hyperedges”, as it is
more common, notably in modular decomposition [11, 4]. Informally, two
hyperedges are orthogonal when they do not contribute to the existence of a
lot of new hyperedges in a hypergraph. The idea is that, given two hyperedges
of a hypergraph in $\mathds{K}_{r}(n)$, because of rules
$\boldsymbol{R}_{{{\,\leq}}}$, $\boldsymbol{R}_{{{\,\neg}}}$ and
$\boldsymbol{R}_{{\,\cup}}$, they can imply the existence of a lot of other
hyperedges. Namely, rules $\boldsymbol{R}_{{{\,\neg}}}$ and
$\boldsymbol{R}_{{\,\cup}}$ can imply up to eight new hyperedges ($A\cup
B,A\setminus B,B\setminus A,A\cap B$, and all their complement). In turn,
these new hyperedges can imply the existence of a lot of new hyperedges, which
implies at the end an explosion of the number of hyperedges in the whole
hypergraph. Without $\boldsymbol{R}_{{\,\cup}}$, the number of new hyperedges
is reduced by far, as one hyperedge implies only the existence of another
hyperedge (its complement).

Thus, the idea is to control how rule $\boldsymbol{R}_{{\,\cup}}$ applies to
hyperedges $A$ and $B$, so that the produced hyperedge $A\cup B$ could also be
obtained by using other rules, i.e., $\boldsymbol{R}_{{{\,\leq}}}$ and/or
$\boldsymbol{R}_{{{\,\neg}}}$. This notion depends only on the hyperedges $A$
and $B$: either $A\cup B$ can be obtained using only
$\boldsymbol{R}_{{{\,\leq}}}$ and/or $\boldsymbol{R}_{{{\,\neg}}}$; or
$\boldsymbol{R}_{{\,\cup}}$ is needed as well to obtain $A\cup B$. In the
first case, hyperedges $A$ and $B$ are said to be orthogonal. In the latter
case, they are said to cross. To formalize this, we introduce a new class of
hypergraphs and a new closure operator that uses only rules
$\boldsymbol{R}_{{{\,\leq}}}$ and $\boldsymbol{R}_{{{\,\neg}}}$, as announced
in Section 1.3:

######  Definition 10.

Let $\mathds{K}_{r}^{\circ}(n)$ be the class of hypergraphs with set of
vertices $V=[n]$ and set of hyperedges $\mathcal{E}$ that satisfies:

  * $\boldsymbol{R}_{{{\,\leq}}}:$

For every set of vertices $X\subseteq V$, if $|X|\leq r$, then
$X\in\mathcal{E}$.

  * $\boldsymbol{R}_{{{\,\neg}}}:$

If $A\in\mathcal{E}$, then $V\setminus A\in\mathcal{E}$.

######  Lemma 12.

The class $\mathds{K}_{r}^{\circ}(n)$ is a closure system.

###### Proof.

The proof is the same as the proof of Lemma 7, except we do not need to prove
the last point. ∎

This induces the following closure operator.

######  Definition 11.

Let $H$ be a hypergraph with vertex set $V=[n]$. The
$\mathds{K}_{r}^{\circ}$-closure of $H$, denoted
${<\\!\\!H\\!\\!>^{\circ}_{r}}$, is the hypergraph defined as the intersection
of all hypergraphs that contain $H$ and that belong to
$\mathds{K}_{r}^{\circ}(n)$. A hypergraph $H$ satisfying
${<\\!\\!H\\!\\!>^{\circ}_{r}}=H$ is called a _closed hypergraph for
${<\\!\\!\cdot\\!\\!>^{\circ}_{r}}$_.

We can now define the notion of $r$-orthogonality:

######  Definition 12.

Let $V=[n]$ be a set of vertices and let $A,B\subseteq V$ be two sets of
vertices. Hyperedges $A$ and $B$ are said to be _$r$ -orthogonal_ if
${<\\!\\!\\{A,B\\}\\!\\!>_{r}}={<\\!\\!\\{A,B\\}\\!\\!>^{\circ}_{r}}$. This is
noted $A\mathrel{\bot_{r}}B$. Recall that $\\{A,B\\}$ denotes the hypergraph
with vertex set $[n]$ and hyperedge set $\\{A,B\\}$.

In other words, two sets of vertices $A$ and $B$ are $r$-orthogonal if the
smallest hypergraph containing them as hyperedge and satisfying rules
$\boldsymbol{R}_{{{\,\leq}}}$ and $\boldsymbol{R}_{{{\,\neg}}}$ is the same as
the smallest hypergraph containing them as hyperedge and satisfying rules
$\boldsymbol{R}_{{{\,\leq}}}$, $\boldsymbol{R}_{{{\,\neg}}}$ and
$\boldsymbol{R}_{{\,\cup}}$. This is a way of guaranteeing that
$\boldsymbol{R}_{{\,\cup}}$ is useless with regard to $A$ and $B$.

######  Example 3.

Let $V=[n]$ with $n=12$, and let $r=3$. Let $A=\\{1,2,3\\}$,
$B=\\{2,3,4,5,6\\}$, $C=\\{1,2,3,4,5,6\\}$ and $D=\\{4,5,6,7,8,9\\}$. One can
prove that $A\mathrel{\bot_{r}}B$ and $C\mathrel{\bot_{r}}D$ using Definition
11. However, this can be a bit tedious. Hence, we develop the following lemmas
to prove some simple equivalences of the relation $\mathrel{\bot_{r}}$.

First, let us state some lemmas about the closure operator
${<\\!\\!\cdot\\!\\!>^{\circ}_{r}}$. A direct application of the definitions
of ${<\\!\\!\cdot\\!\\!>^{\circ}_{r}}$ gives the following lemma:

######  Lemma 13.

Let $V=[n]$ and let $\emptyset$ be the empty hypergraph with vertex set $V$.
Then
${<\\!\\!\emptyset\\!\\!>^{\circ}_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}=\\{A\subseteq
V\;|\;|A|\leq r\text{ or }|\overline{A}|\leq r\\}$.

######  Lemma 14.

Let $V=[n]$ and let $A\subseteq V$ and $B\subseteq V$ be two sets. Then we
have
${<\\!\\!\\{A,B\\}\\!\\!>^{\circ}_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,B,\overline{A},\overline{B}\\}$.

###### Proof.

Let $H=\\{A,B\\}$ and
$H^{\prime}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,B,\overline{A},\overline{B}\\}$.
First, let us prove that ${<\\!\\!H\\!\\!>^{\circ}_{r}}\subseteq H^{\prime}$.
Since ${<\\!\\!H\\!\\!>^{\circ}_{r}}$ is the smallest hypergraph that has $H$
as a sub-hypergraph and that satisfies rules $\boldsymbol{R}_{{{\,\leq}}}$ and
$\boldsymbol{R}_{{{\,\neg}}}$, it suffices to prove that $H^{\prime}$ has $H$
as a sub-hypergraph and that $H^{\prime}$ satisfies rules
$\boldsymbol{R}_{{{\,\leq}}}$ and $\boldsymbol{R}_{{{\,\neg}}}$:

  * •

$H^{\prime}$ has hyperedges $A$ and $B$, meaning that $H^{\prime}$ has $H$ as
a sub-hypergraph.

  * •

$H^{\prime}$ satisfies rule $\boldsymbol{R}_{{{\,\leq}}}$ since
${<\\!\\!\emptyset\\!\\!>_{r}}\subseteq H^{\prime}$ and
${<\\!\\!\emptyset\\!\\!>_{r}}$ satisfies $\boldsymbol{R}_{{{\,\leq}}}$ by
definition.

  * •

$H^{\prime}$ satisfies rule $\boldsymbol{R}_{{{\,\neg}}}$ since
${<\\!\\!\emptyset\\!\\!>_{r}}$ satisfies $\boldsymbol{R}_{{{\,\neg}}}$ by
definition, and $\\{A,B,\overline{A},\overline{B}\\}$ satisfies
$\boldsymbol{R}_{{{\,\neg}}}$ by construction.

Now, let us prove that $H^{\prime}\subseteq{<\\!\\!H\\!\\!>^{\circ}_{r}}$.
First, $A$ and $B$ are hyperedges of ${<\\!\\!H\\!\\!>^{\circ}_{r}}$ since
${<\\!\\!H\\!\\!>^{\circ}_{r}}$ has $H$ as a sub-hypergraph. Then,
$\overline{A}$ and $\overline{B}$ are hyperedges of
${<\\!\\!H\\!\\!>^{\circ}_{r}}$ since ${<\\!\\!H\\!\\!>^{\circ}_{r}}$
satisfies rule $\boldsymbol{R}_{{{\,\neg}}}$. Finally,
${<\\!\\!\emptyset\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>^{\circ}_{r}}\subseteq{<\\!\\!H\\!\\!>^{\circ}_{r}}$.
∎

######  Observation 1.

Let $H$ be a hypergraph. Then
${<\\!\\!H\\!\\!>^{\circ}_{r}}\subseteq{<\\!\\!H\\!\\!>_{r}}$.

Now, let us understand what it means for two hyperedges to be $r$-orthogonal.

######  Lemma 15.

Let $r\geq 0$ and $V=[n]$. Let $A\subseteq V$ and $B\subseteq V$ be two sets.
We have the following equivalence.

$\displaystyle A\mathrel{\bot_{r}}B\iff$ $\displaystyle(|A\cap B|\geq
r\implies A\cup B=A\mathrel{\vee}A\cup
B=B\mathrel{\vee}|\overline{A}\cap\overline{B}|\leq r)\mathrel{\wedge}$
$\displaystyle(|\overline{A}\cap\overline{B}|\geq
r\implies\overline{A}\cup\overline{B}=\overline{A}\mathrel{\vee}\overline{A}\cup\overline{B}=\overline{B}\mathrel{\vee}|A\cap
B|\leq r)\mathrel{\wedge}$ $\displaystyle(|\overline{A}\cap B|\geq
r\implies\overline{A}\cup B=\overline{A}\mathrel{\vee}\overline{A}\cup
B=B\mathrel{\vee}|A\cap\overline{B}|\leq r)\mathrel{\wedge}$
$\displaystyle(|A\cap\overline{B}|\geq r\implies
A\cup\overline{B}=A\mathrel{\vee}A\cup\overline{B}=\overline{B}\mathrel{\vee}|\overline{A}\cap
B|\leq r).$

###### Proof.

$(\implies)$ We have $A\mathrel{\bot_{r}}B$. This means that
${<\\!\\!\\{A,B\\}\\!\\!>^{\circ}_{r}}={<\\!\\!\\{A,B\\}\\!\\!>_{r}}$. Let
$H=\\{A,B\\}$. Thus,
${<\\!\\!H\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,B,\overline{A},\overline{B}\\}$
by Lemma 14. This equality is useful, as only the closure operator
${<\\!\\!\cdot\\!\\!>_{r}}$ appears in it. Now, we have to do the four cases
by hand. We will do the first one in detail and give a sketch for the other
three as it is exactly the same proof:

  * •

If $|A\cap B|\geq r$, by rule $\boldsymbol{R}_{{\,\cup}}$, $A\cup
B\in{<\\!\\!H\\!\\!>_{r}}$. Let us discuss the possible values of $A\cup B$
among hyperedges of
${<\\!\\!H\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,B,\overline{A},\overline{B}\\}$.
If $A\cup B\in{<\\!\\!\emptyset\\!\\!>_{r}}$, then $|A\cup B|\leq r$ or
$|\overline{A\cup B}|\leq r$ by Lemma 13. If $A\cup B=\overline{A}$, then
$A=\emptyset$ and $B=V$, meaning that $A\cup B=B$. If $A\cup B=\overline{B}$,
then $A=V$ and $B=\emptyset$, meaning that $A\cup B=A$. Otherwise, $A\cup B=A$
or $A\cup B=B$. Hence we have that:

$\displaystyle|A\cap B|\geq r$ $\displaystyle\implies|A\cup B|\leq
r\mathrel{\vee}|\overline{A\cup B}|\leq r\mathrel{\vee}A\cup
B=A\mathrel{\vee}A\cup B=B$
$\displaystyle\implies|\overline{A}\cap\overline{B}|\leq r\mathrel{\vee}A\cup
B=A\mathrel{\vee}A\cup B=B$

In the last implication, we have replaced $|\overline{A\cup B}|\leq r$ by
$|\overline{A}\cap\overline{B}|\leq r$, and we have removed $|A\cup B|\leq r$
because if $|A\cap B|\geq r$ and $|A\cup B|\leq r$, then $A=B$, which implies
$A\cup B=A$.

  * •

If $|\overline{A}\cap\overline{B}|\geq r$, then we have $|\overline{A\cup
B}|\geq r$. By property $\boldsymbol{P}_{{{\cap}}}$, we have $A\cap
B\in{<\\!\\!H\\!\\!>_{r}}$, and by rule $\boldsymbol{R}_{{{\,\neg}}}$, we have
$\overline{A\cap B}=\overline{A}\cup\overline{B}\in{<\\!\\!H\\!\\!>_{r}}$.
With the exact same reasoning as the previous item, by replacing $A$ by
$\overline{A}$, $B$ by $\overline{B}$, and vice versa, we conclude that
$(|\overline{A}\cap\overline{B}|\geq
r\implies\overline{A}\cup\overline{B}=\overline{A}\mathrel{\vee}\overline{A}\cup\overline{B}=\overline{B}\mathrel{\vee}|A\cap
B|\leq r)$.

  * •

If $|\overline{A}\cap B|\geq r$, then we have $|B\setminus A|\geq r$. By
property $\boldsymbol{P}_{{\setminus}}$, we have $A\setminus
B\in{<\\!\\!H\\!\\!>_{r}}$, and by rule $\boldsymbol{R}_{{{\,\neg}}}$, we have
$\overline{A\setminus B}=\overline{A}\cup B\in{<\\!\\!H\\!\\!>_{r}}$. With the
exact same reasoning as the first item, by replacing $A$ by $\overline{A}$ and
vice versa, we conclude that $(|\overline{A}\cap B|\geq
r\implies\overline{A}\cup B=\overline{A}\mathrel{\vee}\overline{A}\cup
B=B\mathrel{\vee}|A\cap\overline{B}|\leq r)$.

  * •

If $|A\cap\overline{B}|\geq r$, then we have $|A\setminus B|\geq r$. By
property $\boldsymbol{P}_{{\setminus}}$, we have $B\setminus
A\in{<\\!\\!H\\!\\!>_{r}}$, and by rule $\boldsymbol{R}_{{{\,\neg}}}$, we have
$\overline{B\setminus A}=A\cup\overline{B}\in{<\\!\\!H\\!\\!>_{r}}$. With the
exact same reasoning as the first item, by replacing $B$ by $\overline{B}$ and
vice versa, we conclude that $(|A\cap\overline{B}|\geq r\implies
A\cup\overline{B}=A\mathrel{\vee}A\cup\overline{B}=\overline{B}\mathrel{\vee}|\overline{A}\cap
B|\leq r)$.

$(\ \Longleftarrow\ )$ We have to prove that $A\mathrel{\bot_{r}}B$. Recall
that $H=\\{A,B\\}$, and define
$H^{\prime}:={<\\!\\!H\\!\\!>^{\circ}_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,B,\overline{A},\overline{B}\\}$.
By Lemma 1, we know that
${<\\!\\!H\\!\\!>^{\circ}_{r}}\subseteq{<\\!\\!H\\!\\!>_{r}}$. It remains to
prove that ${<\\!\\!H\\!\\!>_{r}}\subseteq H^{\prime}$. In order to do so, it
suffices to prove that $H^{\prime}$ has $H$ as a sub-hypergraph, and that
$H^{\prime}$ satisfies rules $\boldsymbol{R}_{{{\,\leq}}}$,
$\boldsymbol{R}_{{{\,\neg}}}$ and $\boldsymbol{R}_{{\,\cup}}$. We know that
$H^{\prime}$ has $H$ as a sub-hypergraph by definition of $H$ and
$H^{\prime}$. We already know that $H^{\prime}$ satisfies rules
$\boldsymbol{R}_{{{\,\leq}}}$ and $\boldsymbol{R}_{{{\,\neg}}}$ because
$H^{\prime}={<\\!\\!H\\!\\!>^{\circ}_{r}}$. It remains to prove that
$H^{\prime}$ satisfies $\boldsymbol{R}_{{\,\cup}}$.

Let $C$ and $D$ be two distinct hyperedges of $H^{\prime}$ such that $|C\cap
D|\geq r$, and let us prove that $C\cup D$ is also a hyperedge of
$H^{\prime}$.

First, note that if $C$ is a hyperedge such that $|C|\leq r$, then $|C\cap
D|\leq|C|\leq r$, meaning that $|C\cap D|=r$ and $|C|=r$, and thus $C\subseteq
D$. Hence, $C\cup D=D$, which is a hyperedge of $H^{\prime}$. Secondly, if
$|C|\geq n-r$, then $|C\cup D|\geq n-r$, and $C\cup D$ is a hyperedge of
${<\\!\\!\emptyset\\!\\!>_{r}}$, and thus a hyperedge of $H^{\prime}$. Hence,
if $C\in{<\\!\\!\emptyset\\!\\!>_{r}}$, then $C\cup D\in H^{\prime}$. By
symmetry, if $D\in{<\\!\\!\emptyset\\!\\!>_{r}}$, then $C\cup D\in
H^{\prime}$. Now, it remains the cases where
$\\{C,D\\}\subseteq\\{A,B,\overline{A},\overline{B}\\}$. Taking into account
the symmetry between $C$ and $D$, we have six cases. If $C=\overline{D}$, it
means that $\\{C,D\\}=\\{A,\overline{A}\\}$ or
$\\{C,D\\}=\\{B,\overline{B}\\}$. In both cases, $C\cup D=V\in H^{\prime}$. We
are now left with four cases. Note that they are proved exactly the same way:

  * •

If $C=A$ and $D=B$, since $|C\cap D|\geq r$, then $|A\cap B|\geq r$. By
hypothesis, $(|A\cap B|\geq r\implies A\cup B=A\mathrel{\vee}A\cup
B=B\mathrel{\vee}|\overline{A}\cap\overline{B}|\leq r)$. If $A\cup B=A$, then
$C\cup D=A\cup B=A\in H^{\prime}$. If $A\cup B=B$, then $C\cup D=A\cup B=B\in
H^{\prime}$. If $|\overline{A}\cap\overline{B}|\leq r$, then $|\overline{A\cup
B}|\leq r$, and $\overline{A\cup B}\in H^{\prime}$ by rule
$\boldsymbol{R}_{{{\,\leq}}}$, and $A\cup B\in H^{\prime}$ by rule
$\boldsymbol{R}_{{{\,\neg}}}$, i.e.$C\cup D\in H^{\prime}$.

  * •

If $C=\overline{A}$ and $D=\overline{B}$, since $|C\cap D|\geq r$, then
$|\overline{A}\cap\overline{B}|\geq r$. By hypothesis,
$(|\overline{A}\cap\overline{B}|\geq
r\implies\overline{A}\cup\overline{B}=\overline{A}\mathrel{\vee}\overline{A}\cup\overline{B}=\overline{B}\mathrel{\vee}|A\cap
B|\leq r)$. We do the same analysis by replacing $A$ by $\overline{A}$, $B$ by
$\overline{B}$, and vice versa, and we obtain that $C\cup D\in H^{\prime}$.

  * •

If $C=\overline{A}$ and $D=B$, since $|C\cap D|\geq r$, then
$|\overline{A}\cap B|\geq r$. By hypothesis, $(|\overline{A}\cap B|\geq
r\implies\overline{A}\cup B=\overline{A}\mathrel{\vee}\overline{A}\cup
B=B\mathrel{\vee}|A\cap\overline{B}|\leq r)$. We do the same analysis as the
first case by replacing $A$ by $\overline{A}$ and vice versa, and we obtain
that $C\cup D\in H^{\prime}$.

  * •

If $C=A$ and $D=\overline{B}$, since $|C\cap D|\geq r$, then
$|A\cap\overline{B}|\geq r$. By hypothesis, $(|A\cap\overline{B}|\geq
r\implies
A\cup\overline{B}=A\mathrel{\vee}A\cup\overline{B}=\overline{B}\mathrel{\vee}|\overline{A}\cap
B|\leq r)$. We do the same analysis as the first case by replacing $B$ by
$\overline{B}$ and vice versa, and we obtain that $C\cup D\in H^{\prime}$.

This concludes the proof. ∎

From Lemma 15, we derive some other equivalences of the relation
$A\mathrel{\bot_{r}}B$.

######  Corollary 5.

Let $V=[n]$ and let $A\subseteq V$ and $B\subseteq V$. We have the following
equivalence.

$\displaystyle A\mathrel{\bot_{r}}B$ $\displaystyle\iff$ $\displaystyle(|A\cap
B|<r\mathrel{\vee}A\subseteq B\mathrel{\vee}B\subseteq
A\mathrel{\vee}|\overline{A\cup B}|<r\mathrel{\vee}|A\cap B|=|\overline{A\cup
B}|=r)\mathrel{\wedge}$ $\displaystyle(|A\setminus B|<r\mathrel{\vee}A\cap
B=\emptyset\mathrel{\vee}\overline{A\cup B}=\emptyset\mathrel{\vee}|B\setminus
A|<r\mathrel{\vee}|A\setminus B|=|B\setminus A|=r).$

###### Proof.

We start from the equivalence of Lemma 15 and we use De Morgan’s law as well
as basic set equivalences such as $A\cup B=A\iff B\subseteq A$ and
$\overline{A}\cup B=\overline{A}\iff A\cap B=\emptyset$. Then, let
$R_{1}\equiv(|A\cap B|<r\mathrel{\vee}A\subseteq B\mathrel{\vee}B\subseteq
A\mathrel{\vee}|\overline{A\cup B}|<r)$ and let $R_{2}\equiv(|A\setminus
B|<r\mathrel{\vee}A\cap B=\emptyset\mathrel{\vee}\overline{A\cup
B}=\emptyset\mathrel{\vee}|B\setminus A|<r)$. Recall that for all propositions
$X,Y$, we have $(X\implies Y)\iff(\neg X\mathrel{\vee}Y)$. Furthermore, for
all propositions $X,Y,Z$, we have
$(Z\mathrel{\vee}X)\mathrel{\wedge}(Z\mathrel{\vee}Y)\iff
Z\mathrel{\vee}(X\mathrel{\wedge}Y)$. Hence:

$\displaystyle A\mathrel{\bot_{r}}B$ $\displaystyle\iff$ $\displaystyle(|A\cap
B|<r\mathrel{\vee}A\subseteq B\mathrel{\vee}B\subseteq
A\mathrel{\vee}|\overline{A\cup B}|\leq r)\mathrel{\wedge}$
$\displaystyle(|\overline{A\cup B}|<r\mathrel{\vee}A\subseteq
B\mathrel{\vee}B\subseteq A\mathrel{\vee}|A\cap B|\leq r)\mathrel{\wedge}$
$\displaystyle(|A\setminus B|<r\mathrel{\vee}A\cap
B=\emptyset\mathrel{\vee}\overline{A\cup B}=\emptyset\mathrel{\vee}|B\setminus
A|\leq r)\mathrel{\wedge}$ $\displaystyle(|B\setminus A|<r\mathrel{\vee}A\cap
B=\emptyset\mathrel{\vee}\overline{A\cup B}=\emptyset\mathrel{\vee}|A\setminus
B|\leq r)$ $\displaystyle\iff$
$\displaystyle(R_{1}\mathrel{\vee}|\overline{A\cup
B}|=r)\mathrel{\wedge}(R_{1}\mathrel{\vee}|A\cap
B|=r)\mathrel{\wedge}(R_{2}\mathrel{\vee}|B\setminus
A|=r)\mathrel{\wedge}(R_{2}\mathrel{\vee}|A\setminus B|=r)$
$\displaystyle\iff$ $\displaystyle(R_{1}\mathrel{\vee}|A\cap
B|=|\overline{A\cup B}|=r)\mathrel{\wedge}(R_{2}\mathrel{\vee}|A\setminus
B|=|B\setminus A|=r),$

which concludes the proof. ∎

When $r=1$, Corollary 5 simplifies to $A\mathrel{\bot_{1}}B\iff(A\subseteq
B\mathrel{\vee}B\subseteq A\mathrel{\vee}A\cap
B=\emptyset\mathrel{\vee}\overline{A\cup B}=\emptyset)$, providing that $n>4$.
Indeed, in that case, relations $R_{1}$ and $R_{2}$ from the proof become
equal and we can factorize by it. We need $n>4$ to remove $|A\cap
B|=|\overline{A\cup B}|=|A\setminus B|=|B\setminus A|=r$ from the factorized
equivalence. Hence, this generalizes the notion of non-crossing hyperedges, as
introduced in [7].

The definition of $r$-cross-free hypergraph translates the idea that applying
$\boldsymbol{R}_{{\,\cup}}$ does not provide any new hyperedge. Let us go back
to Example 3 that shows some non-trivial orthogonal hyperedges. Using
Corollary 5, we can now prove easily what we said in that example :

######  Example 4.

Let $V=[n]$ with $n=12$, and let $r=3$. Let $A=\\{1,2,3\\}$ and
$B=\\{2,3,4,5,6\\}$. By using Corollary 5, since $|A\cap B|=|\\{2,3\\}|<r$ and
$|A\setminus B|=|\\{1\\}|<r$, we have that $A\mathrel{\bot_{r}}B$. Let
$C=\\{1,2,3,4,5,6\\}$ and $D=\\{4,5,6,7,8,9\\}$. By using Corollary 5, since
$|C\cap D|=|\overline{C\cup D}|=r$ and $|C\setminus D|=|D\setminus C|=r$, we
have $C\mathrel{\bot_{r}}D$.

Before moving on to the next section, we complete this section by listing some
properties regarding $r$-orthogonal hyperedges.

######  Lemma 16.

We have the following properties for all hyperedges $A$ and $B$ and $r\geq 0$:

  1. 1.

If $|A|\leq r$, then $A\mathrel{\bot_{r}}B$.

  2. 2.

$A\mathrel{\bot_{r}}A$.

  3. 3.

$A\mathrel{\bot_{r}}\overline{A}$.

  4. 4.

If $A\mathrel{\bot_{r}}B$, then $B\mathrel{\bot_{r}}A$.

  5. 5.

If $A\mathrel{\bot_{r}}B$, then $A\mathrel{\bot_{r}}\overline{B}$.

  6. 6.

If $A\mathrel{\bot_{r}}B$, then $A^{\prime}\mathrel{\bot_{r}}B^{\prime}$ for
$A^{\prime}\in\\{A,\overline{A}\\}$ and $B^{\prime}\in\\{B,\overline{B}\\}$.

  7. 7.

If $A\mathrel{\bot_{r}}B$, then $A\mathrel{\bot_{r+1}}B$.

###### Proof.

Let us prove each point using Corollary 5, which states
$A\mathrel{\bot_{r}}B\iff(|A\cap B|<r\mathrel{\vee}A\subseteq
B\mathrel{\vee}B\subseteq A\mathrel{\vee}|\overline{A\cup
B}|<r\mathrel{\vee}|A\cap B|=|\overline{A\cup
B}|=r)\mathrel{\wedge}(|A\setminus B|<r\mathrel{\vee}A\cap
B=\emptyset\mathrel{\vee}\overline{A\cup B}=\emptyset\mathrel{\vee}|B\setminus
A|<r\mathrel{\vee}|A\setminus B|=|B\setminus A|=r).$

  1. 1.

There are three cases. If $|A\cap B|=r$, then $A\setminus B=\emptyset$, which
means that $A\mathrel{\bot_{r}}B$. If $|A\setminus B|=r$, then $A\cap
B=\emptyset$, which means that $A\mathrel{\bot_{r}}B$. Otherwise, $|A\cap
B|<r$ and $|A\setminus B|<r$, which means that $A\mathrel{\bot_{r}}B$.

  2. 2.

If $r>0$, then $A\subseteq A$ and $|A\setminus A|<r$. For the case $r=0$, we
have $A\subseteq A$ and $|A\setminus A|=|A\setminus A|=r$.

  3. 3.

$|A\cap\overline{A}|<r$ and $A\cap\overline{A}=\emptyset$.

  4. 4.

Definition 12 is symmetrical in $A$ and $B$.

  5. 5.

Corollary 5 is stable by replacing $B$ by $\overline{B}$.

  6. 6.

This is a consequence of points 4 and 5.

  7. 7.

If a set has size at most $r$, it has also size at most $r+1$.

Hence, every point is proven. ∎

##  4 Cross-free hypergraphs and lower bound

In this section, we introduce $r$-cross-free hypergraphs as a tool to prove a
lower bound on the number of hyperedges needed to represent a $r$-closed
hypergraph. We also prove that $r$-cross-free hypergraphs are, in a sense, not
compressible, as they have roughly the same number of hyperedges as any of
their representation.

######  Definition 13.

A hypergraph $H$ is said to be $r$-cross-free if for every pair of hyperedges
$(A,B)$, $A\mathrel{\bot_{r}}B$, i.e. $A$ and $B$ are $r$-orthogonal.

If an $r$-cross-free hypergraph $H$ is closed, we know it can be generated by
a hypergraph with $\mathcal{O}(n^{r+1})$ hyperedges. In this section, we show
that the number of hyperedges of $H$ is also $\mathcal{O}(n^{r+1})$.

The goal of the proof is to go deep inside the structure of a $r$-cross-free
closed hypergraph. By definition, when we take the closure of a $r$-cross-free
hypergraph, we do not need to apply $\boldsymbol{R}_{{\,\cup}}$ to do so.
Hence, since we apply only rules $\boldsymbol{R}_{{{\,\leq}}}$ and
$\boldsymbol{R}_{{{\,\neg}}}$, we will add $\mathcal{O}(n^{r})$ hyperedges and
then double the number of hyperedges. Thus, intuitively, a $r$-cross-free
hypergraph and its closure have roughly the same number of hyperedges.
However, we already know that a closed hypergraph $H$ can be generated by a
sub-hypergraph $H^{\prime}$ with $\mathcal{O}(n^{r+1})$ hyperedges. In the
case of $r$-cross-free closed hypergraph $H$, since $H$ and $H^{\prime}$ have
roughly the same number of hyperedges, $H$ should also have
$\mathcal{O}(n^{r+1})$ hyperedges, showing that $r$-cross-free closed
hypergraphs have a small number of hyperedges.

###  4.1 Tools

######  Lemma 17.

Let $H$ be a $r$-cross-free hypergraph with vertex set $V=[n]$, let $A$ be a
hyperedge of $H$. Let $\\{A\\}$ be the hypergraph with vertex set $V$ that has
only $A$ as hyperedge. Then:
${<\\!\\!\\{A\\}\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,\overline{A}\\}$.

###### Proof.

${<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,\overline{A}\\}$ is a hypergraph that
contains $\\{A\\}$ as a sub-hypergraph and that satisfies rules
$\boldsymbol{R}_{{{\,\leq}}}$, $\boldsymbol{R}_{{{\,\neg}}}$ and
$\boldsymbol{R}_{{\,\cup}}$. Since ${<\\!\\!\\{A\\}\\!\\!>_{r}}$ is the
smallest such hypergraph, we have
${<\\!\\!\\{A\\}\\!\\!>_{r}}\subseteq{<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,\overline{A}\\}$.

Since $\emptyset\subseteq\\{A\\}$, then
${<\\!\\!\emptyset\\!\\!>_{r}}\subseteq{<\\!\\!\\{A\\}\\!\\!>_{r}}$ by
monotony. Furthermore, $A$ is a hyperedge of ${<\\!\\!\\{A\\}\\!\\!>_{r}}$
since ${<\\!\\!\\{A\\}\\!\\!>_{r}}$ must contains $\\{A\\}$ as a sub-
hypergraph. Then, since ${<\\!\\!\\{A\\}\\!\\!>_{r}}$ must satisfy rule
$\boldsymbol{R}_{{{\,\neg}}}$, then $\overline{A}$ must be a hyperedge of
${<\\!\\!\\{A\\}\\!\\!>_{r}}$, meaning that
${<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,\overline{A}\\}\subseteq{<\\!\\!\\{A\\}\\!\\!>_{r}}$,
which concludes the proof. ∎

######  Lemma 18.

Let $H$ be a hypergraph with vertex set $V=[n]$, let $A$ and $B$ be two
hyperedges of $H$. Then:
$A\mathrel{\bot_{r}}B\iff{<\\!\\!\\{A,B\\}\\!\\!>_{r}}={<\\!\\!\\{A\\}\\!\\!>_{r}}\cup{<\\!\\!\\{B\\}\\!\\!>_{r}}$.

###### Proof.

By Definition 7,
$A\mathrel{\bot_{r}}B\iff{<\\!\\!\\{A,B\\}\\!\\!>_{r}}={<\\!\\!\\{A,B\\}\\!\\!>^{\circ}_{r}}$.
By Lemmas 14 and 17, we have the following equalities:

$\displaystyle{<\\!\\!\\{A,B\\}\\!\\!>^{\circ}_{r}}$
$\displaystyle={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,B,\overline{A},\overline{B}\\}$
$\displaystyle=({<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,\overline{A}\\})\cup({<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{B,\overline{B}\\})$
$\displaystyle={<\\!\\!\\{A\\}\\!\\!>_{r}}\cup{<\\!\\!\\{B\\}\\!\\!>_{r}}.$

Hence the result. ∎

######  Lemma 19.

Let $H$ be a $r$-cross-free hypergraph with vertex set $V=[n]$ and at least
one hyperedge. For every hyperedge $A$ of $H$, let $\\{A\\}$ be the hypergraph
with vertex set $V$ that has only $A$ as hyperedge. Then:

$\displaystyle{<\\!\\!H\\!\\!>_{r}}=\bigcup_{A\in
H}{<\\!\\!\\{A\\}\\!\\!>_{r}}$

###### Proof.

One inclusion is easy: for any hyperedge $A$, we have $\\{A\\}\subseteq H$.
Hence ${<\\!\\!\\{A\\}\\!\\!>_{r}}\subseteq{<\\!\\!H\\!\\!>_{r}}$, meaning
that $\bigcup_{A\in
H}{<\\!\\!\\{A\\}\\!\\!>_{r}}\subseteq{<\\!\\!H\\!\\!>_{r}}$.

Now, let us prove that ${<\\!\\!H\\!\\!>_{r}}$ is included in the union
$U:=\bigcup_{A\in H}{<\\!\\!\\{A\\}\\!\\!>_{r}}$. To do so, let us prove that
$U$ satisfies rules $\boldsymbol{R}_{{{\,\leq}}}$,
$\boldsymbol{R}_{{{\,\neg}}}$ and $\boldsymbol{R}_{{\,\cup}}$. The first two
rules trivially hold. For rule $\boldsymbol{R}_{{\,\cup}}$, let $A,B$ be two
hyperedges of $U$ such that $|A\cap B|\geq r$. Hence, there exists
$A^{\prime}\in H$ and $B^{\prime}\in H$ such that
$A\in{<\\!\\!\\{A^{\prime}\\}\\!\\!>_{r}}$ and
$B\in{<\\!\\!\\{B^{\prime}\\}\\!\\!>_{r}}$. By Lemma 17,
${<\\!\\!\\{A^{\prime}\\}\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A^{\prime},\overline{A^{\prime}}\\}$.
If $A\in{<\\!\\!\emptyset\\!\\!>_{r}}$, by Lemma 13, either $|A|\leq r$ or
$|A|\geq n-r$. If $|A|\leq r$, since $|A\cap B|\geq r$, we have $|A|=|A\cap
B|=r$, and $A\subseteq B$, meaning that $A\cup B=B\in U$. If $|A|\geq n-r$,
$|A\cup B|\geq n-r$ and $A\cup B\in{<\\!\\!\emptyset\\!\\!>_{r}}\subseteq U$.
It remains to consider the case where
$A\subseteq\\{A^{\prime},\overline{A^{\prime}}\\}$. With the same analysis, we
can consider that $B\subseteq\\{B^{\prime},\overline{B^{\prime}}\\}$

Since $H$ is $r$-cross-free, $A\mathrel{\bot_{r}}B$. By Lemma 16,
$A^{\prime}\mathrel{\bot_{r}}B^{\prime}$. Then, by Lemma 18,
${<\\!\\!\\{A^{\prime}\\}\\!\\!>_{r}}\cup{<\\!\\!\\{B^{\prime}\\}\\!\\!>_{r}}={<\\!\\!\\{A^{\prime},B^{\prime}\\}\\!\\!>_{r}}$.
Hence, $A,B\in{<\\!\\!\\{A^{\prime},B^{\prime}\\}\\!\\!>_{r}}$, and since
$|A\cap B|\geq r$, by rule $\boldsymbol{R}_{{\,\cup}}$, we have $A\cup
B\in{<\\!\\!\\{A^{\prime},B^{\prime}\\}\\!\\!>_{r}}$. Then, since
${<\\!\\!\\{A^{\prime},B^{\prime}\\}\\!\\!>_{r}}={<\\!\\!\\{A^{\prime}\\}\\!\\!>_{r}}\cup{<\\!\\!\\{B^{\prime}\\}\\!\\!>_{r}}$,
$A\cup
B\in{<\\!\\!\\{A^{\prime}\\}\\!\\!>_{r}}\cup{<\\!\\!\\{B^{\prime}\\}\\!\\!>_{r}}\subseteq
U$. Since $U$ contains $H$, and since ${<\\!\\!H\\!\\!>_{r}}$ is the smallest
such hypergraph, we have ${<\\!\\!H\\!\\!>_{r}}\subseteq U$. ∎

With the three previous lemmas, we can understand the structure of an
$r$-cross-free hypergraph.

######  Lemma 20.

Let $H$ be an $r$-cross-free hypergraph with $n$ vertices. Then we have that:

$\displaystyle{<\\!\\!H\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\bigcup_{A\in
H}\\{A,\overline{A}\\}.$

As a consequence, $|{<\\!\\!H\\!\\!>_{r}}|\leq 2(r+1)n^{r}+2|H|$.

###### Proof.

By applying Lemmas 19 and 17 to $H$ which is $r$-cross-free, we have:

$\displaystyle{<\\!\\!H\\!\\!>_{r}}=\bigcup_{A\in
H}{<\\!\\!H_{A}\\!\\!>_{r}}=\bigcup_{A\in
H}({<\\!\\!\emptyset\\!\\!>_{r}}\cup\\{A,\overline{A}\\})={<\\!\\!\emptyset\\!\\!>_{r}}\cup\bigcup_{A\in
H}\\{A,\overline{A}\\}.$

Then, since ${<\\!\\!\emptyset\\!\\!>_{r}}=\\{A\subseteq V\;|\;|A|\leq r\text{
or }|\overline{A}|\leq r\\}$, we have that:

$\displaystyle|{<\\!\\!H\\!\\!>_{r}}|$
$\displaystyle\leq\sum_{i=0}^{r}\binom{n}{i}+\sum_{i=0}^{r}\binom{n}{n-i}+2|H|\leq
2(r+1)n^{r}+2|H|$

which concludes the proof. ∎

As a consequence, when $H$ is $r$-cross-free, $H$ and ${<\\!\\!H\\!\\!>_{r}}$
have roughly the same number of hyperedges. We know that
$H\subseteq{<\\!\\!H\\!\\!>_{r}}$, meaning that
$|H|\leq|{<\\!\\!H\\!\\!>_{r}}|$. With Lemma 20, we have the following bounds:
$|H|\leq|{<\\!\\!H\\!\\!>_{r}}|\leq 2(r+1)n^{r}+2|H|$. These bounds can be
improved by removing ${<\\!\\!\emptyset\\!\\!>_{r}}$ from $H$.

######  Lemma 21.

Let $H$ be a $r$-cross-free hypergraph with $n$ vertices. Then:

$|H\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|\leq|{<\\!\\!H\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|\leq
2|H\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|.$

###### Proof.

Let $H^{\prime}=H\setminus{<\\!\\!\emptyset\\!\\!>_{r}}$, Let
$J=H\cap{<\\!\\!\emptyset\\!\\!>_{r}}$, let $U=\bigcup_{A\in
H}\\{A,\overline{A}\\}$ and let $U^{\prime}=\bigcup_{A\in
H^{\prime}}\\{A,\overline{A}\\}$. We have:

$\displaystyle U=\bigcup_{A\in H}\\{A,\overline{A}\\}=\bigcup_{A\in
J}\\{A,\overline{A}\\}\cup\bigcup_{A\in
H^{\prime}}\\{A,\overline{A}\\}=\bigcup_{A\in J}\\{A,\overline{A}\\}\cup
U^{\prime}\subseteq{<\\!\\!\emptyset\\!\\!>_{r}}\cup U^{\prime}.$

By Lemma 20, ${<\\!\\!H\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup U$.
Hence, ${<\\!\\!H\\!\\!>_{r}}\subseteq{<\\!\\!\emptyset\\!\\!>_{r}}\cup
U^{\prime}$. Since $U^{\prime}\subseteq U$, we also have
${<\\!\\!\emptyset\\!\\!>_{r}}\cup
U^{\prime}\subseteq{<\\!\\!\emptyset\\!\\!>_{r}}\cup U={<\\!\\!H\\!\\!>_{r}}$.
All in all, ${<\\!\\!H\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup
U^{\prime}$.

According to Lemma 13, we know that
${<\\!\\!\emptyset\\!\\!>_{r}}=\\{A\subseteq V\;|\;|A|\leq r\text{ or }|A|\geq
n-r\\}$. Since $H^{\prime}=H\setminus{<\\!\\!\emptyset\\!\\!>_{r}}$, every
hyperedge of $H^{\prime}$ satisfies $r<|A|<n-r$. Since $U^{\prime}$ is made
only of hyperedges $A$ such that $A\in H^{\prime}$ or $\overline{A}\in
H^{\prime}$, every hyperedges $A$ of $U^{\prime}$ satisfies $r<|A|<n-r$.
Hence, $U^{\prime}$ and ${<\\!\\!\emptyset\\!\\!>_{r}}$ are disjoint.
Therefore, the equality
${<\\!\\!H\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup U^{\prime}$ can be
rewritten as
${<\\!\\!H\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}=U^{\prime}$. From
the definition of $U^{\prime}$, we have $|H^{\prime}|\leq|U^{\prime}|\leq
2|H^{\prime}|$, which we rewrite as
$|H\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|\leq|{<\\!\\!H\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|\leq
2|H\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|$, hence the result. ∎

Now, let us see that the property of being $r$-cross-free is inherited when
going back and forth through the closure operator ${<\\!\\!\cdot\\!\\!>_{r}}$.

######  Lemma 22.

Let $H$ be a hypergraph with $n$ vertices. $H$ is $r$-cross-free if and only
if ${<\\!\\!H\\!\\!>_{r}}$ is $r$-cross-free.

###### Proof.

If $H$ is a $r$-cross-free hypergraph, by Lemma 20, it satisfies:

$\displaystyle{<\\!\\!H\\!\\!>_{r}}={<\\!\\!\emptyset\\!\\!>_{r}}\cup\bigcup_{A\in
H}\\{A,\overline{A}\\}.$ ($*$)

We have to show that every pair of hyperedges $A,B$ of ${<\\!\\!H\\!\\!>_{r}}$
is orthogonal. Let $A,B$ be two hyperedges of ${<\\!\\!H\\!\\!>_{r}}$. If
$A\in{<\\!\\!\emptyset\\!\\!>_{r}}$, then by Lemma 13, we have $|A|\leq r$ or
$|\overline{A}|\leq r$. Hence, with the first point of Lemma 16,
$A\mathrel{\bot_{r}}B$. The same is true if
$B\in{<\\!\\!\emptyset\\!\\!>_{r}}$. Thus, we can consider that
$A\notin{<\\!\\!\emptyset\\!\\!>_{r}}$ and
$B\notin{<\\!\\!\emptyset\\!\\!>_{r}}$. Hence, using relation $(*)$, it means
that there exists $A^{\prime}\in H$ such that $A=A^{\prime}$ or
$\overline{A^{\prime}}$ and there exists $B^{\prime}\in H$ such that
$B=B^{\prime}$ or $\overline{B^{\prime}}$. Since $H$ is $r$-cross-free,
$A^{\prime}\mathrel{\bot_{r}}B^{\prime}$. Using the sixth point of Lemma 16,
$A\mathrel{\bot_{r}}B$.

If ${<\\!\\!H\\!\\!>_{r}}$ is $r$-cross-free, then every pair of hyperedge of
${<\\!\\!H\\!\\!>_{r}}$ is $r$-orthogonal. Since
$H\subseteq{<\\!\\!H\\!\\!>_{r}}$, every pair of hyperedge of $H$ is also
$r$-orthogonal, and $H$ is $r$-cross-free. ∎

###  4.2 Bounds

Using the lemmas stated in the previous section, we can easily prove the
following theorem:

######  Theorem 2.

Let $H$ be a hypergraph in $\mathds{K}_{r}(n)$ that is also $r$-cross-free,
and let $f$ be a bound on the number of hyperedges needed to represent a
hypergraph of order $n$. If $f(n)=\Omega(n^{r})$, then
$|H|=\mathcal{O}(f(n))$.

###### Proof.

By Theorem 1, there exists $H^{\prime}$ with $\mathcal{O}(n^{r+1})$ hyperedges
such that $H={<\\!\\!H^{\prime}\\!\\!>_{r}}$. By Lemma 22, $H^{\prime}$ is
$r$-cross-free. Hence, by Lemma 20, $|H|=|{<\\!\\!H^{\prime}\\!\\!>_{r}}|\leq
2(r+1)n^{r}+2|H^{\prime}|=\mathcal{O}(n^{r})+\mathcal{O}(f(n))=\mathcal{O}(f(n))$.
∎

By Theorem 1, there exists such a function $f$ with $f(n)=\Theta(n^{r+1})$.
This means that the number of hyperedges of a $r$-cross-free hypergraph is
$\mathcal{O}(n^{r+1})$.

The remainder of this section is dedicated to proving a lower bound on the
number of hyperedges needed to represent a closed hypergraph.

######  Lemma 23.

For all $r>0$, there exists an infinite family of $r$-cross-free hypergraphs
$\\{H_{n}\\}$, each with $n$ vertices and a number of hyperedges equal to
$\Omega(n^{r})$ as $n$ goes to infinity.

###### Proof.

Let $r>0$. Let $n$ be a multiple of $r+1$, i.e. $n=k(r+1)$ for some
$k\in\mathds{Z}$. We will construct a hypergraph with $n$ vertices such that
every pair of hyperedge is $r$-orthogonal. To do so, let us consider the
vertex set $V:=\mathds{Z}/k\mathds{Z}\mathrel{\times}[r+1]$, where
$\mathds{Z}/k\mathds{Z}$ denotes the set of integers modulo $k$. One can
interpret this set as follows: every vertex is assigned a value between 0 and
$k-1$ and a color from the set $[r+1]$. The value is used modulo $k$ through
computation, which is why it is taken from $\mathds{Z}/k\mathds{Z}$ rather
than from $\\{0,\ldots,k-1\\}$. The edge set is defined as follows:

$\displaystyle\mathcal{E}:=\Bigg{\\{}A=\\{(v_{i},c_{i})\\}_{i=1}^{r+1}\in\binom{V}{r+1}\;\Bigg{|}\;\\{c_{i}\\}_{i=1}^{r+1}=[r+1]\text{
and }\sum_{i=1}^{r+1}v_{i}\equiv 0\mod k\Bigg{\\}}$

In other words, $\mathcal{E}$ is the family of all sets made of $r+1$ vertices
from $V$ such that:

  * •

vertices have pairwise distinct colors, and

  * •

the sum of the value of each vertex equals 0 modulo $k$.

As there are $r+1$ colors and $r+1$ vertices in a hyperedge, each hyperedge
contains exactly one vertex of each color. We consider the hypergraph
$H_{n}=(V,\mathcal{E})$.

First, remark that if one picks $r$ vertices with pairwise distinct colors,
then there is only one hyperedge that contains these $r$ vertices. Indeed, let
$(v_{i},c_{i})$ with $1\leq i\leq r$ be these $r$ vertices. Let
$(v_{r+1},c_{r+1})$ be a vertex. For $\\{(v_{i},c_{i})\\}_{i=1}^{r+1}$ to be a
hyperedge, $c_{r+1}$ must be the missing color from
$\\{(v_{i},c_{i})\\}_{i=1}^{r}$, and $v_{r+1}$ must be equal to
$-\sum_{i=1}^{r}v_{i}\mod k$. Hence, if $A,B\in\mathcal{E}$ are two hyperedges
of $H$ such that $|A\cap B|=r$, then $A=B$. As a consequence, for every pair
$(A,B)$ of distinct hyperedges, $A\mathrel{\bot_{r}}B$. Indeed, we know that
$|A\cap B|<r$ since $A\neq B$. Then, either $|A\setminus B|<r$, which mean
that $A\mathrel{\bot_{r}}B$, or $|A\setminus B|=r$, which implies that $|A\cap
B|=1$ and that $|B\setminus A|=r$, meaning that $A\mathrel{\bot_{r}}B$. As a
consequence, $H_{n}$ is $r$-cross-free.

Now, let us compute the cardinality of $\mathcal{E}$. Without loss of
generality, we can set $c_{i}=i$. Hence, there is no choice to take regarding
colors. For $1\leq i\leq r$, $v_{k}$ can be picked freely among $k$ different
vertices. For $v_{r+1}$, there is only one choice available. Hence,
$|\mathcal{E}|=k^{r}$. As $n=k(r+1)$, we have:
$|\mathcal{E}|=k^{r}=(r+1)^{-r}\;n^{r}=\Omega(n^{r})$, as $r$ is fixed and $n$
goes to infinity. ∎

######  Theorem 3.

For a fixed $r>0$, there exists an infinite family of $r$-cross-free
hypergraphs $\\{H_{n}\\}$, each with $n$ vertices, such that for any
hypergraph $H_{n}$ and for any hypergraph $H^{\prime}$, if
${<\\!\\!H^{\prime}\\!\\!>_{r}}={<\\!\\!H_{n}\\!\\!>_{r}}$, then $H^{\prime}$
has at least $\Omega(n^{r})$ hyperedges, with respect to $n$ going to
infinity.

###### Proof.

Let $\\{H_{n}\\}$ be the family defined in Lemma 23. Let $H^{\prime}$ be such
that ${<\\!\\!H^{\prime}\\!\\!>_{r}}={<\\!\\!H_{n}\\!\\!>_{r}}$. Hypergraph
$H_{n}$ is $r$-cross-free, so ${<\\!\\!H_{n}\\!\\!>_{r}}$ and $H^{\prime}$ are
also $r$-cross-free by Lemma 22. Therefore, we can apply Lemma 21:
$2|H^{\prime}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|\geq|{<\\!\\!H^{\prime}\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|$,
meaning in particular that
$2|H^{\prime}|\geq|{<\\!\\!H^{\prime}\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|$.
Thus,
$2|H^{\prime}|\geq|{<\\!\\!H_{n}\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|$.
Furthermore,
$H_{n}\subseteq{<\\!\\!H_{n}\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}$
because $H_{n}\subset{<\\!\\!H_{n}\\!\\!>_{r}}$ and because every hyperedge
$A$ of $H_{n}$ have a size satisfying $r<|A|<n-r$, meaning that
$H_{n}\cap{<\\!\\!\emptyset\\!\\!>_{r}}=\emptyset$. Hence,
$|{<\\!\\!H_{n}\\!\\!>_{r}}\setminus{<\\!\\!\emptyset\\!\\!>_{r}}|\geq|H_{n}|$.
Recall that the number of hyperedges of $|H_{n}|$ satisfies $\Omega(n^{r})$.
Hence, since $2|H^{\prime}|\geq|H_{n}|$, the number of hyperedges of
$H^{\prime}$ is $\Omega(n^{r})$. ∎

In summary, some $r$-closed hypergraphs need at least $\Omega(n^{r})$
hyperedges to be represented, and our method guarantees at most
$\mathcal{O}(n^{r+1})$ hyperedges.

##  5 Concluding remarks

In this paper, we prove that $r$-closed hypergraphs need at least
$\Omega(n^{r})$ hyperedges to be represented, and we give a method that
guarantees at most $\mathcal{O}(n^{r+1})$ hyperedges to represent such a
hypergraph. The natural question is to reduce the gap between the lower and
upper bound: Does there exists a better method that gives at most
$\mathcal{O}(n^{r})$ hyperedges, or are there some $r$-closed hypergraphs that
need at least $\Omega(n^{r+1})$ hyperedges to be represented? Or maybe the
correct space complexity stands between $n^{r}$ and $n^{r+1}$?

## References

  * [1] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  Journal of the ACM (JACM), 69(1):1–46, 2021.
  * [2] Binh-Minh Bui-Xuan, Michel Habib, and Michaël Rao.  Tree-representation of set families and applications to combinatorial decompositions.  European Journal of Combinatorics, 33(5):688–711, 2012.
  * [3] Nathalie Caspard and Bernard Monjardet.  The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey.  Discrete Applied Mathematics, 127(2):241–269, 2003.
  * [4] Pierre Charbit, Fabien De Montgolfier, and Mathieu Raffinot.  Linear time split decomposition revisited.  SIAM Journal on Discrete Mathematics, 26(2):499–514, 2012.
  * [5] Bruno Courcelle, Joost Engelfriet, and Grzegorz Rozenberg.  Handle-rewriting hypergraph grammars.  Journal of computer and system sciences, 46(2):218–270, 1993.
  * [6] William H Cunningham.  Decomposition of directed graphs.  SIAM Journal on Algebraic Discrete Methods, 3(2):214–228, 1982\.
  * [7] William H Cunningham and Jack Edmonds.  A combinatorial decomposition theory.  Canadian Journal of Mathematics, 32(3):734–765, 1980.
  * [8] Jack Edmonds and Rick Giles.  A min-max relation for submodular functions on graphs.  In Annals of Discrete Mathematics, volume 1, pages 185–204. Elsevier, 1977.
  * [9] Emeric Gioan and Christophe Paul.  Dynamic distance hereditary graphs using split decomposition.  In International symposium on algorithms and computation, pages 41–51. Springer, 2007.
  * [10] Emeric Gioan and Christophe Paul.  Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs.  Discrete Applied Mathematics, 160(6):708–733, 2012.
  * [11] Michel Habib and Christophe Paul.  A survey of the algorithmic aspects of modular decomposition.  Computer Science Review, 4(1):41–59, 2010.
  * [12] Petr Hliněnỳ, Sang-il Oum, Detlef Seese, and Georg Gottlob.  Width parameters beyond tree-width and their applications.  The computer journal, 51(3):326–362, 2008.
  * [13] Sang-il Oum.  Rank-width and vertex-minors.  Journal of Combinatorial Theory, Series B, 95(1):79–100, 2005.
  * [14] Sang-il Oum.  Rank connectivity and pivot-minors of graphs.  arXiv preprint arXiv:2011.03205, 2020.
  * [15] Sang-il Oum and Paul Seymour.  Approximating clique-width and branch-width.  Journal of Combinatorial Theory, Series B, 96(4):514–528, 2006\.
  * [16] Neil Robertson and Paul D. Seymour.  Graph minors. ii. algorithmic aspects of tree-width.  Journal of algorithms, 7(3):309–322, 1986.