has to occur

Linear equations for unordered data vectors in →^.

Piotr Hofman
Faculty of Mathematics, Informatics, and Mechanics

University of Warsaw

Warszawa, Polska
This work is supported by Polish NCN grant nr. UMO-2016/21/D/ST6/01368.

Jakub Różycki
Faculty of Mathematics, Informatics, and Mechanics

University of Warsaw

Warszawa, Polska

This work is supported by Polish NCN grant nr. UMO-2016/21/D/ST6/01368.

Following a recently considered generalisation of linear equations to unordered-data vectors
and to ordered-data vectors,
we perform a further generalisation to k-element-sets-of-unordered-data vectorsdata vectors that are functions from k-element subsets of the
unordered-data set to vectors of integer numbers11.
These generalised equations naturally appear in the analysis of vector addition systems
(or Petri nets) extended so that each token carries a set of unordered data.
We show that nonnegative-integer solvability of linear equations is in nondeterministic-exponential-timenondeterministic exponential time11
while integer solvability is in polynomial-timepolynomial time11.

§ INTRODUCTION.

Diophantine linear equations
The solvability problem for systems of linear Diophantine equations is defined as follows:
given a finite input set of $\dimension$-dimensional integer vectors $\setInput = \{\vec v_1\ldots \vec v_m\} \subseteq \ktuple{\dimension}{\Z}$, and
a target vector $\vec v \in \ktuple{\dimension}{\Z}$, we ask if there is a solution $(n_1\ldots n_m)$
such that

\begin{align}\label{eq:Dio}
n_1 \cdot \vec v_1 + \ldots + n_m \cdot \vec v_m = \vec v.
\end{align}

Restricting solutions $n_1\ldots n_m$ to integers $\Z$ or nonnegative integers $\N$to the set $\Z$ of integers or the set $\N$ of nonnegative
integers18, we may speak of
$\Z$-solvability orand19 $\N$-solvability, respectively.
The former problem is in $\PTIME,$
while the latter is equivalent to integer linear programming, a well-known
$\NPTIME-complete$$\NPTIME$-completeNULL problem <cit.>.

This paper is a continuation of a line of research that investigates generalisations
of the solvability problem to data vectors <cit.>, i.e., i.e.22
on a high level of abstraction, to vectors indexed by orbit-finite sets instead of finite ones
(for an introduction to orbit-finite sets, also known as sets with atoms,
see <cit.>).

In the simplest setting, given a fixed countable infinite set $\setD$ of data values,
a data vector is a function $\vec{a}\colon \setD \to \ktuple{\dimension}{\Z}$. Addition and scalar multiplication are defined pointwise i.e.
$\vec{a}{\bf +}\vec{a'}(\da)=\vec{a}(\da)+\vec{a'}(\da)$
$(\vec{a}{\bf +}\vec{a'})(\da)=\vec{a}(\da)+\vec{a'}(\da)$26 for every $\da\in \setD$.
In the presence of data, the solvability problems are defined analogouslyThe solvability problems over input sets $\setInput$ of data vectors are
defined analogously27, with the important difference
that the input set $\setInput$ of data vectors is orbit-finite, i.e., i.e.2227
is the closure, under data permutations/data renaming35, of a finite set of data vectors.
Given such an orbit-finiteinfinite, but finite up to data permutation27 set $\setInput$, and a target data vector $\vec v$, we ask if there are
data vectors $\vec v_1\ldots \vec v_m\in \setInput$ and numbers $n_1\ldots n_m$, such that
the equality (<ref>) is satisfied.

We consider data vectors $\setD \xrightarrow{} \Z$. For every two different data values $\dd, \de\in \setD$, let
$\vec v_{\dd \de}(x) = 1$ if $x=\dd$ or $x=\de$, and $\vec v_{\dd \de}(x) = 0$ otherwise.
Let $\setInput = \setof{\vec v_{\dd \de}\colon \setD \to \Z}{\dd,\de\in\setD,\dd\neq \de}$. The set $\setInput$ is closed under data permutation. Indeed, for
any data permutation
$\pi\colon\setD\xrightarrow{} \setD$ and any $\vec{v_{\dd \de}}\in \setInput$ we have $\vec{v_{\dd \de}}\circ \pi = \vec{v_{\pi^{-1}(\dd) \pi^{-1}(\de)}}$
which is
also an element of

Finally, let $\vec v(\db) = 2$$\vec{v_{\db}}(\db) = 2$70 and $\vec v(x) = 0$$\vec{v_{\db}}(x) = 0$70 for $x\neq \db$, where
$\db\in\setD$ is some fixed data
On the one hand side44, this instance admits a $\Z$-solution, since $\vec a$since $\vec{v_{\db}}$44 is presentable as

\begin{align*}
\vec v = \vec v_{\db \dd} + \vec v_{\db \de} - \vec v_{\dd \de},
\end{align*}

\begin{align*}
\vec{v_{\db}} = \vec v_{\db \dd} + \vec v_{\db \de} - \vec v_{\dd \de},
\end{align*}

for any two different data values $\dd,\de$ different than $\db$.
On the other hand side44, there is no $\N$-solution, as there is no similar presentation
of $\vec v$$\vec{v_{\db}}$70 in terms of data vectors $\vec v_{\dd \de}$ that useuses47 nonnegative coefficients. Simply, every
vector that is a sum of of data vectors from the
family $\setInput$ must be strictly positive for at least two data values.
Furthermore, if $\vec v(\db) = 3$$\vec{v_{\db}}(\db) = 3$70 instead of $2$, then there is no $\Z$-solution, too. Indeed, notice that $\sum_{\da
\in \setD} \vec{w}(\da)$ is always
an even number if $\vec{w}$ is a sum of data vectors from the family $\setInput.$

The above simple example is covered by the theory developed in <cit.>. HereHere,169,170 we extend the previous
resultresults from <cit.>53 to
data vectors in $\kset{\setSizeK}{\setD}\xrightarrow{} \ktuple{\dimension}{\Z}$, where $\kset{\setSizeK}{\setD}$ stands for the ${\setSizeK}$
elements${\setSizeK}$-element54 subsets of
$\setD$. The complexity of
analysis of data vectors in $\kset{\setSizeK}{\setD}\xrightarrow{} \ktuple{\dimension}{\Z}$ can already be observed
for $\setSizeK=2$ and $\dimension=1.$

Consider data vectors of a formin56 $\kset{2}{\setD} \to{} \Z$ where $\kset{2}{\setD} =\{ \{\dd,\de\}\colon \dd,\de\in \setD,\ \dd\neq \de\}$.
You can think of them as weighted graphs with vertices labelled with elements of $\setD$.
Suppose the set $\setInput$ is a set of triangles with weights of all edges equal $1$equal to $1$58, i.e. i.e.22

\begin{equation*}
\vec{v_{\dc \dd \de}}(x)=\begin{cases}
1 \quad &\text{if} \, x \in\{\{\dc,\dd\},\{\dd,\de\},\{\de,\dc\}\} \\
0 \quad &\text{otherwise}\\
\end{cases}
\end{equation*}

and $\setInput=\setof{\vec v_{\dc \dd \de}\colon \kset{2}{\setD} \to \Z}{\dc, \dd, \de\in\setD, \dd\neq \de \neq \dc \neq \dd}$ (see Figure <ref>).

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]
[place] (DA) at (0, 0) $\da$;
[place] (DB) at (2, 2) $\db$;
[place] (DC) at (4, 0) $\dc$;
[-, color=black] (DA) to node [left] $1$ (DB);
[-, color=black] (DA) to node [below ] $1$ (DC);
[-, color=black] (DB) to node [right ] $1$ (DC);

Graph representing the data vector $\vec{v_{\da\db\dc}}$.

The set $\setInput$ is closed under
data permutations, indeed for any
permutation $\pi$ and any $\vec v_{\dc \dd \de}\in \setInput$ the data vector
$\changed{}{\vec{v_{\dc\dd\de}}\circ \pi =}{NULL}\vec v_{\pi^{-1}(\dc) \pi^{-1}(\dd) \pi^{-1}(\de)}\in \setInput$.
Finally, we want to know if $\setInput$ and the following target data vector $\vec{v_{\dc \dd}}$ admitsadmits70 a $\Z$-solution

\begin{equation*}
\vec{v_{\dc \dd}}(x)=\begin{cases}
6 \quad &\text{if} \, x = \{\dc,\dd\} \\
0 \quad &\text{otherwise}\\
\end{cases}
\end{equation*}

($v_{\dc \dd}$$\vec{v}_{\dc \dd}$NULL is a single edge with weight 6).
The answer is yes, but it is not trivial,

\[
\vec{v_{\dc\dd}}= (\vec{v_{\db\dd\dc}} - \vec{v_{\db\dd\da}} + \vec{v_{\dd\dc\de}} - \vec{v_{\dd\de\da}} + \vec{v_{\db\da\de}} - \vec{v_{\db\dc\de}} )+
(\vec{v_{\dd\db\dc}}  - \vec{v_{\dc\db\da}} + \vec{v_{\dd\de\dc}} - \vec{v_{\dc\de\da}} + \vec{v_{\de\db\da}}  - \vec{v_{\de\db\dd}}) + 2\vec{V_{\da\dd\dc}}
\]

where $\da,\db,$ and $\de$ are any data values different than $\dc,\dd$.75

The idea behind the above sum is presented in Figure <ref>.

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]

[place] (DA) at (9.95, 10) $\da$;
[place] (DB) at (12.3, 10) $\db$;
[place] (DC) at (7.7, 10) $\dc$;
[place] (DD) at (9.95, 12.1) $\dd$;
[place] (DE) at (9.95, 7.8) $\de$;

[-, color=] (7.9, 10.23) to node [above right]  (9.72,11.98);
[-, color=] (10.20, 11.98) to node [above right]  (12.10,10.20);
[-, color=] (8, 10.03) to node [above right]  (12.02,10.03);

[-, color=] (7.9, 9.78) to node [above right]  (9.72,7.96);
[-, color=] (10.20, 7.96) to node [above right]  (12.10,9.78);
[-, color=] (8, 9.97) to node [above right]  (12.02,9.97);

(R) at (13,10) $=$;

[place] (DA1) at (13.95, 10) $\da$;
[place] (DD1) at (13.95, 12.1) $\dd$;
[place] (DE1) at (13.95, 7.8) $\de$;

[-, color=black] (DA1) to node [right] $2$ (DD1);
[-, color=black] (DA1) to node [right] $-2$ (DE1);

(TEXT) at (18,10)
First we construct a gadget $\vec{g_{\dd\da\de}}$ as presented on the left. Blue color denotes addition and orange subtraction of an edge.
$\vec{g_{\da\dd\de}}= \vec{v_{\da\db\dd}} - \vec{v_{\da\db\de}} + \vec{v_{\da\dc\dd}} - \vec{v_{\da\dc\de}} + \vec{v_{\dc\db\de}} - \vec{v_{\dc\db\dd}}$

Next, we use such gadgets combined with triangles in the following way $g_{\dc\dd\da}+g_{\dd\dc\da} + 2\vec{v_{\da\dc\dd}}=\vec{v_{\dc\dd}}.$
$\vec{g}_{\dc\dd\da}+\vec{g}_{\dd\dc\da} + 2\vec{v_{\da\dc\dd}}=\vec{v_{\dc\dd}}.$

IdaIdea88 behind construction in Example <ref>.

If we ask about $\N$-solvability then the answer is no. If we add triangles then the number of nonzero edges will be greater than $2$, so there
is no way of reaching $\vec{v}_{\dc\dd}$.89
WhatBut, what89 if we change $6$ to $3$? The answer is postponed to Section <ref>.

§.§ Related work and our contribution.

The above-discussed, simplest extension of the $\Z$-solvability problem to data vectors of the form $\setD\xrightarrow{} \ktuple{\dimension}{\Z}$
is in $\PTIME,$ and the $\N$-solvability is $\NPTIME-complete$$\NPTIME$-complete20,92 <cit.>.
Further known results concern the more general case of ordered data domain $\setD$ <cit.>: while. For ordered data
we assume that the set of data forms a dens linear order and the set of data permutations is restricted to the set of order preserving bijections
$\setD\to{}\setD$. In the ordered data case93 the $\Z$-solvability problem remains in $\PTIME,$ while93 the complexity of the
$\N$-solvability is
equivalent to the reachability problem of vector addition systems with states (VASS),
or Petri nets, and hence $\AckermanCOMPLETE$20 <cit.>.
The increase of complexity caused by the order in data is thus remarkable.
An example of a result that builds on top of the97 <cit.> is
where the continuous reachability problem for unordered data nets is shown to be in $\PTIME.$ The question if the continuous reachability problem is
solvable for the ordered data
domain remains open.
It is particularly interesting due to <cit.>,
where the coverability problem in timed data nets <cit.> is
to be
interreducible with the coverability problem in ordered data nets.

In this paper, we perform a further generalisation to ${\setSizeK}$-element subsets of unordered data, i.e., i.e. we22
consider data vectors of the form $\kset{\setSizeK}{\setD} \xrightarrow{} \ktuple{\dimension}{\Z}$, where $\kset{\setSizeK}{\setD}$ stands for
the ${\setSizeK}$-element subsets of $\setD$.
We prove two main results: first, for every fixed $\setSizeK\geq 1$
the complexity of the $\Z$-solvability problem again remains polynomial.
Second, we prove decidability and provide an upper $\NETIME$ complexity bound for
the $\N$-solvability problem.
Second, we present a $\NETIME$ algorithm for the $\N$-solvability problem.106
This is done by an improvement of techniques developed in <cit.>. Namely, we non-triviallynontrivially107 extend
theoremsTheorems107,119 11 and 15
from <cit.>.

* To address $\N$-solvability, we reprove the theoremTheorem109 11 from <cit.> in a more general setting (the proof
slightly modified). Next,110
combined it
with new idea to obtain a reduction to the (easier) $\Z$-solvability,
witnessing a nondeterministic exponential blowup.

* Our approach to $\Z$-solvability is an extension the theoremof Theorem112 15 from <cit.>.
Precisely, if we reformulate the $\Z$-solvability question in terms of
(weighted) hypergraphs, then there is a natural way to lift the
characterisation of $\Z$-solvability proposed in Theorem 15 <cit.>.
The main contribution of this paper is a new tool-box developed to prove the lifted theorem 15 from <cit.>.
The new characterisation is easily checkable in polynomial
time, what gives usresulting in117 the algorithm.

The analogous of theoremsTheorems107,119 11 and 15 from <cit.> are not present in

No analogous of theoremsTheorems107,119 11 and 15 from <cit.> appear in
<cit.> or are otherwise known,
thus we are pessimistic about
applicability of the studied here approach in case of the ordered data domain.

As we comment in the conclusionsConclusions122,
we believe that elaboration of the techniques of this paper allows also tackling the case
of tuples of unordered data.

Our motivation for this research is two-fold.
FromOn the one hand, from124 a foundational research perspective, our results are a part of a wider research program
aiming at lifting computability results in finite-dimensional linear algebra to
its orbit-finite-dimensional counterpart.
Up to now, research is focusedhas been focused127 on understanding
expressibilitysolvability124 <cit.>127, but there are other natural questions
definitions of bases, dimension, linear transformations, etc.
We are focused on expressibility, as it gives us a tool for the analysis of systems with
data.On the other hand, we are interested in the analysis of systems with data and solvability may be a useful tool.124
We highlight three areas where understanding of $\N/\Z$-expressibilitysolvability124 may be crucial for further development.

Unordered Data nets reachability/coverability <cit.>. The model can be seen as a special type of Coloured Petri
nets <cit.>.
Data nets are an extension of Petri nets where every token caries a tuple of data values. In additionIn addition,134 each
transition is equipped with a Boolean formula that connects data of tokens that are consumed and data of tokens that are produced (for unordered data the
formula may use $=$ and $\neq$). To fire a transition we take a valuation satisfying the formula and according to it we remove and produce tokens.

Consider the following simple net with $3$ places and one transition. The initial marking has $3$ tokens each with two data values.

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=17mm,
token/.style=circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=4mm]
transition=[rectangle,thick,draw=!75, fill=!20,minimum size=10mm]
[place]      (A1)         $ $;
[token]      (TOK1)    at (0,0.35)     $\da,\db$;
[token]      (TOK2)    at (0,-0.35)     $\da,\dc$;
[place]      (B1)      at (0,-2)  $ $;

[token]      (TOK3)    at (0,-1.8)     $\db,\dd$;

[transition]      (T1)     at (4.5,-1) $y = z \land x=x' \land u=u' $;
[place]      (C1)     at (9,-1) ;
[->] (A1) to node [above right] $(x,y)$ (T1);
[->] (B1) to node [below right] $(z,u)$ (T1);
[->] (T1) to node [below ] $(x',u')$ (C1);

If we valuate $x=\da, y=\db, z=\db, u=\dd, x'=\da, u'=\dd$ then we may fire the transition and get the new marking.

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=17mm,
token/.style=circle,draw=black!100,fill=black!100,thick,inner sep=0pt,minimum size=4mm]
transition=[rectangle,thick,draw=!75, fill=!20,minimum size=10mm]
[place]      (A1)         $ $;

[token]      (TOK2)    at (0,-0.2)     $\da,\dc$;
[place]      (B1)      at (0,-2)  $ $;

[transition]      (T1)     at (4.5,-1) $y = z \land x=x' \land u=u' $;
[place]      (C1)     at (9,-1) ;
[token]      (TOK4)    at (9,-0.8)     $\da,\dd$;
[->] (A1) to node [above right] $(x,y)$ (T1);
[->] (B1) to node [below right] $(z,u)$ (T1);
[->] (T1) to node [below ] $(x',u')$ (C1);

If we choseIf we had chosen152 another valuation $x=\da, y=\db, z=\db, u=\dc, x'=\da, u'=\dc$ then the formula would hold,
but we would lack tokens that can be consumed so we
could not fire the transition with this valuation.

The reachability and coverability questions can be formulated as usual for Petri nets.
It is not hard to imagine that some workflow or a flow of data through a program can be modelled with data nets.
Unfortunately, in this richer model the reachability and coverability problems are undecidable <cit.> already for $k=2$.
For $k=1$, i.e. i.e.22 data vectors in $\setD\xrightarrow{} \ktuple{\dimension}{\Z}$$\setD\xrightarrow{}
\ktuple{\dimension}{\Z}$,160 the status of reachability is unknown and coverability is decidable but known to
be Ackermann-hard  <cit.>.
This is not a satisfying answer for engineers and in this case we should look for over and under approximations of the reachability relation, or for some
techniques that will help in the analysis of industrial cases. One of the classic over-approximations of the Petri nets reachability relation is so-called
integer reachability(165 or Marking Equation Lemma165 in <cit.> lemma 2.12)Lemma 2.12,165 where the
number of tokens in some places may go negative during the run. It can be
encoded as integer programming and solved in $\NPTIME.$ Its analogue for data nets can be stated as $\N$-solvability of an orbit finite linear
equations.over an input set of data vectors, where the set is closed under data permutations.167

HereHere,169,170 we should mention that the integer reachability is a member of a wider family of algebraic techniques for Petri nets. We refer
to <cit.> for
an exhaustive overview of linear-algebraic and integer-linear-programming techniques
in the analysis of Petri nets. The usefulness of these techniques is confirmed by multiple applications including, for instance, recently proposed
efficient tools for the coverability problem of Petri
nets <cit.>.

Another formalism close to unordered data nets are $\nu$-nets (unordered data nets equipped with a global freshens test.additionaly equipped with
an operation of creating a new datum that is not present in the current configuration of the net; in other words, a transition may force creation of data that
are globally fresh/unique175). In <cit.>In <cit.>,175
observes that they are equivalent to so-called multiset rewriting with name binding systems which, as he showed, are a formalism equivalent to
ThusThus,177 one may try to transfer algebraic techniques for data nets to $\pi$-calculus. This is a long way,
but there is no possibility to start it without a good understanding of integer solutions of linear equations with data.

HereHere,169,170 it is worth to mention thatworth mentioning that180
in $\pi$ calculus-calculus186 we use constructs like $\bar{c}\langle y\rangle.P$ which send a datum $y$ trough the channel $c$, thus the sending
operation is
parameterized with
a pair of data values i.e. the name of the channel and the data value. ThusThus,177 one can notcannot357 expect that already
existing results for data vectors
$\setD\xrightarrow{} \Z^\dimension$ <cit.> will be sufficient and we will need at least theory for $\setD^2\xrightarrow{}
\Z^\dimension$, for
example, to count messages that are sent and received.

But even pairs of data may not be enough. Rosa-Velardo encodes $\pi$-calculus in $\nu$-nets using derivatives, which essentially are terms of bounded depth.
The bound depends on the process definition. The number of data values that parametrize each derivative is bounded.
In the encoding, each derivative corresponds to a place while particular instantiations of derivatives we represent with tokens.
Thus, if use this encoding, then we should expect arbitrary tuples of data and not only pairs.

In fact even $\setD^2\xrightarrow{}\Z^\dimension$ may be not enough. In <cit.>, the fundamental concept for the encoding are derivatives, which
essentially are terms of bounded depth labelled with data values. In his encoding, Rosa-Velardo represent each derivative with a token, so each token has to
carry all data that are needed to identify the derivative. For a given process definition, he produces a $\nu$-net with tokens with bounded but
arbitrary high number of data values. Thus, if one wants to use linear algebra with data to describe some properties of the produced $\nu$-net, he will have to
work with data vectors in $\ktuple{\setSizeK}{\setD}\to{}\ktuple{\dimension}{\Z}$, for $\setSizeK$ grater than $2$.

Parikh'Parikh'190s theorem. Finally, we may try to lift Parikh'Parikh'190s theorem from
context-free grammars
and finite automata to context-free grammars with data <cit.> and
register automata <cit.>. It is not
clear to what extent it is possible but there are some
promising results <cit.>.
If we want to use this lifted Parikh'Parikh'190s theorem then we have to work with semilinear sets with data and be able to check
things like membership or
non-emptinessnonemptiness107 of the intersection. HereHere,169,170 one more time techniques to solve systems of linear equations
with data will be inevitable.

In Section <ref> we introduce the setting and define the problems.
Next, in Section <ref> we provide the polynomial-time procedure for the $\Z$-solvability
problem: the hypergraph reformulation and an effective characterisation
of hypergraph solvability.
In Section <ref> due tofor200 pedagogical reasons we present
the proof of the characterisation if data vectors are restricted
to $\kset{2}{\setD}\xrightarrow{} \ktuple{\dimension}{\Z}$.
After this, in Sections
<ref>, <ref>, <ref>, <ref>, <ref>, <ref> we provide the full proof of the characterisation.
The proof follows the same steps,202
as the proof of the case $\kset{2}{\setD}\xrightarrow{} \ktuple{\dimension}{\Z}$, but is much more involving oninvolved at204 the technical level.
Next, in Section <ref> we present a reduction from $\N$- to $\Z$-solvability.
Finally, Section <ref> concludes this work.

§ LINEAR EQUATIONS WITH DATA.

In this section, we introduce the setting of linear equations with data and formulate our results.
For a gentle introduction of the setting, we start by recalling classical linear equations.

Let $\Z$ and $\N$ denote integers and nonnegative integers, respectively.

Classical linear equations are of the form

\[
a_1 x_1 + \ldots + a_m x_m = a,
\]

where $x_1 \ldots x_m$ are variables (unknowns), and $a_1 \ldots a_m\in \Z$ are integer coefficients.
For a finite system $\systemOfEquationsU$ of such equations over the same variables
$x_1\ldots x_m$, a solution of ${\systemOfEquationsU}$
is a vector $(n_1\ldots n_m) \in \Z^m$ such that the valuation
$x_1 \mapsto n_1\ldots$, $x_m \mapsto n_m$ satisfies all equations in $\systemOfEquationsU$.
It is well known that integer solvability problem
($\Z$-solvability problem), i.e., i.e.22 the question whether $\systemOfEquationsU$ has a solution $(n_1\ldots n_m) \in \Z^m$,
is decidable in $\PTIME.$

In the sequel we are often interested in nonnegative integer solutions $(n_1\ldots n_m) \in \N^m$,
but one may consider also other solution domains than $\N$.
It is well known that the nonnegative-integer solvability problem ($\N$-solvability problem)
of linear equations, i.e. i.e.22 the question whether
${\systemOfEquationsU}$ has a nonnegative-integer solution, is NP-complete (for hardness see <cit.>; NP-membership is a consequence
The complexity remains the same for other natural variants of this problem, for instance, for inequalities
instead of equations (a.k.a. integer linear programming).

The $\Numbers$-solvability problem (where $\Numbers \in\{\Z, \N\}$)
is equivalently formulated as follows: for a given finite set of coefficient vectors
$\setInput = \{\vec v_1\ldots \vec v_m\} \subseteq \ktuple{\dimension}{\Z}$ and a target vector $\vec v \in \ktuple{\dimension}{\Z}$
(we use bold font to distinguish vectors from other elements), check whether
$\vec v$ is an $\sumsBez{\Numbers}$ of $\setInput$,
i.e., i.e. 22

\begin{align}\label{eq:lineq}
\vec{v} \in \sums{\Numbers}{\setInput} = \setof{n_1 \cdot \vec v_1 + \ldots + n_m \cdot \vec v_m}{n_1\ldots n_m \in \Numbers}.
\end{align}

The dimension $\dimension$ corresponds to the number of equations in $\systemOfEquationsU$.

Data vectors
Linear equations can be naturally extended with data.

In this paper, we assume that the data domain $\setD$ is a countable infinite set,
whose elements are called data values.
The bijections $\rho\colon \setD\to\setD$ are called data permutations.

For a set $\setX$ and $\setSizeK\in\N$, by $\kset{\setSizeK} \setX$ we denote the set of all ${\setSizeK}$-elements${\setSizeK}$-element54
subsets of $\setX$
(called ${\setSizeK}$-sets in short).
Data permutations lift naturally to ${\setSizeK}$-sets of data values:
$\rho(\{\da_1\ldots \da_{\setSizeK}\}) = \{\rho(\da_1)\ldots \rho(\da_{\setSizeK})\}$.

Fix a positive integer $\setSizeK\geq 1$.
A data vector is a function $\vec{v}\colon \kset{\setSizeK}{\setD} \rightarrow \ktuple{\dimension}{\Z}$
such that $\vec v(x) = \vec{0}\in \ktuple{\dimension}{\Z}$ for all but finitely many $x \in \kset{\setSizeK}{\setD}$.
(Again, we use bold font to distinguish data vectors from other elements.)
The numbers ${\setSizeK}$ and $\dimension$ we callWe call the numbers ${\setSizeK}$ and $\dimension$237 the arity and the dimension of $\vec v$, respectively.

The vector addition and scalar multiplication are lifted to data vectors pointwise:
$(\vec{v}+\vec{w})(x) \eqdef \vec{v}(x)+\vec{w}(x)$, and
$(c\cdot \vec v)(x)\eqdef c\vec{v}(x)$.

Further,241 for a data permutation $\pi\colon\setD\xrightarrow{} \setD$ by $\vec{v}\circ \pi$ we mean the data vector defined as follows
$(\vec{v}\circ \pi) (\changed{\da_1, \da_2\ldots \da_{\setSizeK}}{\{\da_1, \da_2\ldots \da_{\setSizeK}\}}{242}) \eqdef \vec{v}(\changed{\pi(\da_1),\pi(\da_2)\ldots \pi(\da_{\setSizeK})}{\{\pi(\da_1),\pi(\da_2)\ldots \pi(\da_{\setSizeK})\}}{242})$ for all $\da_1, \da_2\ldots
\da_{\setSizeK}\in \setD$. It is the natural lift
of normal function composition.
For a set $\setInput$ of data vectors we define

\[
\perm{\setInput} = \setof{\vec v \circ \pi}{\vec v \in \setInput, \pi \changed{\in \text{data permutations}}{\text{ is a data permutation}}{245} }.
\]

A data vector $\target$
is said to be an $\Numbers$-permutation sum of a finite set of data vectors $\setInput$ if
(we deliberately overload the symbol $\sums{\Numbers}{\placeHolder}$ and use it for data vectors,
while in (<ref>) it is used for (plain) vectors)

\begin{equation}
\target \in \sums{\Numbers}{\perm{\setInput}} =
\setof{n_1 \cdot \vec{v_1} + \ldots + n_m \cdot \vec{v_m}}
{\\ \vec{v_1}\ldots\vec{v_m} \in \perm{\setInput}, n_1\ldots n_m \in \Numbers}.
\end{equation}

We investigate the following decision problems (for $\Numbers \in\{\Z,\N\}$):

A finite set $\setInput$ of data vectors and a target data vector $\vec v$, all of the same arity and dimension
Is $\vec v$ an $\Numbers$-permutation sum of $\setInput$?

The insightful reader may notice that, in the motivating examples we consider $\Numbers$-sums of an input set of data vectors that is closed under
data permutations. Here, we switch to the $\Numbers$-solvability problem, which is defined by $\Numbers$-permutation sum. But observe that, to formalise
expressibility by $\Numbers$-sums as a problem we have to provide a finite representation of the input set. That is why as an input to the problem we take a
finite set of data vectors $\setInput$, and we consider $\Numbers$-sums of its closure under data permutations i.e. of the set $\perm{\setInput}$. This is why
we consider $\Numbers$-permutation sums instead of pure $\Numbers$-sums.253

For complexity estimations we assume binary encoding of numbers appearing in the input to all decision problems discussed in this paper.

Our main results are the following complexity bounds:

For every fixed arity ${\setSizeK}\in \N$, the $\Z$-solvability problem is in $\PTIME.$
(The dependency formon261 ${\setSizeK}$ is exponential).

For every fixed arity ${\setSizeK}\in \N$, the $\N$-solvability problem is in $\NETIME.$

For athe263 special case of the solvability problems when the arity ${\setSizeK} = 1$,
the $\PTIME$ and $\NPTIME$ complexity bounds, respectively, have been shown in <cit.>.
Thus, according to Theorem <ref>,
in the case of $\Z$-solvability the complexity remains polynomial for every ${\setSizeK} > 1$.
In the case of $\N$-solvability the $\NPTIME-hardness$$\NPTIME$-hardness20 carries over to every ${\setSizeK}>1$, and
hence a complexity gap remains open between $\NPTIME$ and $\NETIME.$

§ PROOF OF THEOREM <REF>.

We start by reformulating the problem in terms of (undirected) weighted uniform hypergraphs
(Lemma <ref> below).

Fix a positive integer ${\setSizeK} \geq 1$.
By a ${\setSizeK}$-hypergraph we mean a pair $\hypergraphH = (\setVertices, \mu)$ where $\setVertices\subset \setD$
is a finite set called vertices
and $\mu\colon \kset{\setSizeK}{\setVertices} \to \ktuple{\dimension}{\Z}$ is a weight function (when ${\setSizeK}$
is not relevant we skip it and write a hypergraph).
As before, the numbers ${\setSizeK}$ and $\dimension$ we callwe call the numbers ${\setSizeK}$ and $\dimension$237  the arity and the dimension of $\hypergraphH$, respectively.
In the case of arity $\setSizeK=2$When $\setSizeK=2$,274 we speak of graphs instead of hypergraphs.
(Note however that the (hyper)graphs we consider are always weighted, with weights from $\ktuple{\dimension}{\Z}$.)

Because vertices are essentially277 data then instead of usual $u,v$ for vertices we will use Greek letters $\da,\db,\dc,\dd,\de\ldots$.

The set of hyperedges is then defined as

\[
\he \hypergraphH = \setof{{\edge} \in \kset{\setSizeK} \setVertices}{\mu({\edge}) \neq {\vec{0}}}.
\]

When $\da\in {\edge}$ for $\da\in \setVertices$ and ${\edge} \in \he \hypergraphH$, we say that the vertex $\da$
is incidentadjacentNULL with the
hyperedge ${\edge}$.
The degree of $\da$ is the  number of hyperedges incidentadjacentNULL with $\da$.
Vertices of degree 0 we callWe call vertices of degree $0$237 isolated.

Two hypergraphs are isomorphic if there is a bijection between their sets of
vertices that preserves the value of the weight function.
Two hypergraphs are equivalent if they are isomorphic after
removing their isolated vertices.
For a set ${\setHypergraphsH}$ of hypergraphs, by $\eqs {\setHypergraphsH}$ we denote the set of all hypergraphs equivalent
to ones from ${\setHypergraphsH}$. If ${\setHypergraphsH}=\{\hypergraphH\}$ then instead of $\eqs{\{\hypergraphH\}}$ we write $\eqs{\hypergraphH}$.

Scalar multiplication and addition are defined naturally for hypergraphs.
First, for $c \in \Z$ and a hypergraph $\hypergraphH = (\setVertices, \mu)$,
let $c \cdot \hypergraphH \eqdef (\setVertices, c\cdot \mu)$.
Second, given two hypergraphs $\hypergraphG = (\setVerticesW, \widetilde{\mu})$ and $\hypergraphH = (\setVertices, \mu)$
of the same arity ${\setSizeK}$ and dimension $\dimension$,
we first add isolated vertices to both hypergraphs to make their
vertex sets equal to the union $\setVertices \cup \setVerticesW$$\setVerticesW \cup \setVertices$292,
thus obtaining $\hypergraphG' = (\setVerticesW\cup \setVertices, \widetilde{\mu}')$ and $\hypergraphH' =
(\setVerticesW\cup \setVertices, \mu')$ with the
accordingly extended
weight functions $\widetilde{\mu}', \mu'\colon \kset{\setSizeK}{{(\setVerticesW \cup \setVertices)}} \to \ktuple{\dimension}{\Z}$,
and then define $\hypergraphG + \hypergraphH \eqdef (\setVerticesW\cup \setVertices, \widetilde{\mu}' + \mu')$.

Using these operations we define $\Numbers$-sums
of a family ${\setHypergraphsH}$ of hypergraphs of the same arity and dimension
(again, we overload the symbol $\sums \Numbers {\placeHolder}$ further and use it for hypergraphs):

\[
\sums \Numbers {{\setHypergraphsH}} =
\setof{c_1 \cdot \hypergraphH_1 + \ldots + c_l \cdot \hypergraphH_l}
{c_1\ldots c_l \in \Numbers, \hypergraphH_1\ldots \hypergraphH_l \in {\setHypergraphsH}}.
\]

We say that a hypergraph $\hypergraphH$ is a $\Numbers$-sum of ${\setHypergraphsH}$ up to equivalence if
$\hypergraphH$ is a $\Numbers$-sum of hypergraphs equivalent to elements of ${\setHypergraphsH}$:
\hypergraphH \in \sums \Numbers {\eqs {\setHypergraphsH}}.

We illustrate the $\Z$-sums in arity $\setSizeK=2$, i.e., i.e.22 using graphs.
Consider the following graph $\hypergraphG$ consisting of 3 vertices and 2 edges:

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]
[place]      (A1)         $\da$;
[place]      (B1)       [left=of A1]  $\db$;
[place]      (C1)      [right=of A1] $\dc$;
(B1) to node [above] $\vec{x}$ (A1) to node [above] $\vec{y}$ (C1) ;

Let $\vec x, \vec y \in \ktuple{\dimension}{\Z}$ be arbitrary vectors.
HereHere, there169,170 are two examples of graphs which can be presented
as a $\Z$-sum of $\{\hypergraphG\}$ up to equivalence, using a sum
of two graphs equivalent to $\hypergraphG$:

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]
[node distance=7mm and 7mm]
[place]      (B1i)      at (0,-1) $\db$;
[place]      (A1i)      [above right =of B1i]   $\da$;
[place]      (C1i)      [below right=of A1i] $\dc$;
(B1i) to node [above, sloped] $2\vec x$ (A1i) to node [above, sloped] $\vec y$ (C1i)
to node [below] $\vec y$ (B1i);

(R) at (3,-0.5) =;

[place]      (Ai)    at (5,-0.5)                     $\db$;
[place]      (Bi)       [left=of Ai]  $\da$;
[place]      (Ci)      [right=of Ai] $\dc$;
(Bi) to node [above] $\vec x$ (Ai) to node [above] $\vec y$ (Ci);

(R1) at (7,-0.5) +;

[place]      (Aii)    at (9,-0.5)                     $\da$;
[place]      (Bii)       [left=of Aii]  $\db$;
[place]      (Cii)      [right=of Aii] $\dc$;
(Bii) to node [above] $\vec x$ (Aii) to node [above] $\vec y$ (Cii);

and a difference of two such graphs:

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]
[node distance=7mm and 7mm]
[place]      (A2ii)  at (-1,-2.5)     $\da$;
[place]      (B2ii)       [right=of A2ii]  $\db$;
[place]      (C2ii)      [right =of B2ii] $\dc$;
[place]      (D2ii)      [right=of C2ii] $\dd$;

(A2ii) to node [above] $\vec x$ (B2ii);
(C2ii) to node [above] $-\vec x$ (D2ii);

(Rii) at (3,-2.5) =;

[place]      (Aii)    at (5,-2.5)                     $\db$;
[place]      (Bii)       [ left=of Aii]  $\da$;
[place]      (Cii)      [right=of Aii] $\dc$;
(Bii) to node [above] $\vec x$ (Aii) to node [above] $\vec y$ (Cii);

(R1ii) at (7,-2.5) -;

[place]      (Cii)    at (9,-2.5)   $\dc$;
[place]      (Aii)   [left =of Cii]  $\db$;
[place]      (Bii)       [right=of Cii]  $\dd$;
(Aii) to node [above] $\vec y$ (Cii) to node [above] $\vec x$ (Bii);

We are now ready to formulate the hypergraph $\Z$-sum problem,
to which the312 $\Z$-solvability is going to be reduced:

hypergraph $\Z$-sum
A finite set ${\setHypergraphsH}$ of hypergraphs and a target hypergraph $\hypergraphH$, all of the same arity and dimension
Is $\hypergraphH$ a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence?

The $\Z$-solvability problem reduces in logarithmic space to the hypergraph $\Z$-sum problem.
The reduction preserves the arity and dimension.

The reduction encodes each data vector $\vec v$ by a hypergraph $\hypergraphH = (\setVertices, \mu)$, where

\[
\setVertices \quad = \quad \bigcup \{x\in \kset{\setSizeK}{\setD} \mid \vec{v}(x)\not={\vec{0}}\}
\]

and $\mu$ is the restriction of $\vec v$ to $\kset{\setSizeK}{\setVertices}$.
In this way,323 a set $\setInput$ of data vectors and a target data vector $\vec v$ are transformed into
a set of ${\setHypergraphsH}$ hypergraphs and a target hypergraph $\hypergraphH$ such that
$\vec v$ is a $\Z$-permutation sum of $\setInput$ if, and only if,325 $\hypergraphH$ is a $\Z$-sum of ${\setHypergraphsH}$
up to equivalence.

Thus, from now on, we concentrate on solving the hypergraph $\Z$-sum problem. One may ask why we perform such a reduction.
The reasons are of pedagogical nature, namely graphs are more convenient for examples and proofs by pictures.

As the next step, we formulate our core technical result (Theorem <ref>). The theorem
provides a local characterisation of the hypergraph $\Z$-sum problem
and in consequence it enables solving the problem in polynomial time.In the theorem we state that the hypergraph $\Z$-sum problem
is equivalent to a local $\Z$-sum problem, defined in the following paragraph. It is easy to design a polynomial time algorithm for the local $\Z$-sum problem.
This gives us the proof of Theorem <ref>.331
Let $\hypergraphH = (\setVertices, \mu)$ be a hypergraph. For a set $\setX \subset \setD$ we consider
$\setof{\edge\in \he \hypergraphH}{\setX \subseteq \edge}$ —
the set of all hyperedges that include $\setX$ —
and define the weight of $\setX$ as the sum of weights of all these edges:

\[
\weight{setX}(\hypergraphH) \eqdef \sum_{\edge\in \he \hypergraphH, \setX\subseteq \edge} \mu(\edge).
\]

In particular when $\setX\not\subseteq \setVertices$ then $\weight{setX}(\hypergraphH) =\vec{0}$.
Further, $\weight{emptyset}(\hypergraphH)$ is the sum of weights of all
hyperedges of $\hypergraphH$.
When $\setX = \{\da\}$, then $\weight{setX}(\hypergraphH)$ is the sum of weights of all hyperedges incidentadjacentNULL with $\da$
(we write $\weight{da}$
instead of
). Finally,
when the cardinality of $\setX$ equals ${\setSizeK}$ i.e. $\size{\setX} = {\setSizeK}$, $\weight{setX}(\hypergraphH)= \mu(\setX)$
is the weight of a hyperedge $\setX$, given as a
defining component of $\hypergraphH$341.

Let $\vec x, \vec y, \vec z \in \ktuple{\dimension}{\Z}$ be arbitrary vectors.
As an illustration, consider the graph $\hypergraphG$ on the left below, with the weights of chosen subsets of its vertices
listed on the right:

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm]
[place]      (A)                       $\da$;
[place]      (B)       [below left=of A]  $\db$;
[place]      (C)      [below right=of A] $\dc$;
(A) to node [above] $\vec x$ (B) to node [above] $\vec y$ (C) to node [above] $\vec z$ (A);

(D) at (4,-0.5)

\begin{align*}
&\weight{{da,db}}(\hypergraphG)=\vec x\\
&\weight{db}(\hypergraphG)=\vec x+\vec y\\
&\weight{dc}(\hypergraphG)=\vec z+ \vec y\\
&\weight{emptyset}(\hypergraphG)=\vec x+\vec y+\vec z.
\end{align*}

Weights of sets 351are important as they form a family
of homomorphisms from hypergraphs to $\ktuple{\dimension}{\Z}$. Namely,
for any subset of vertices $\setX$ we have that

\[\weight{setX}(\hypergraphH + \hypergraphH') = \weight{setX}(\hypergraphH) + \weight{setX}(\hypergraphH')\]

\[c \weight{setX}(\hypergraphH)= \weight{setX}(c\hypergraphH)\text{, for any }c\in \Z.\]

This allowallows356 us to design a partial test for the hypergraph
$\Z$-sum problem. If there is a set of vertices $\setX$ such that
$\weight{setX}(\hypergraphH)$ can notcannot357 be expressed as a $\Z$-sum of vectors in $\weight{setX}(\eqs {\setHypergraphsH})$ then
$\hypergraphH\not\in \sums \Z {\eqs {\setHypergraphsH}}$. This motivates the next definition.

We say that a ${\setSizeK}$-hypergraph $\hypergraphH = (\setVertices, \mu)$ is
locally a $\Z$-sum of a family $\setHypergraphsH$ of hypergraphs if
for every $\setX\subseteq \setVertices$ of the 360cardinality $\size{\setX}\leq \setSizeK$, its weight $\weight{setX}(\hypergraphH)$
is a $\Z$-sum
of weights of $\size{\setX}$-element subsets of vertex sets of hypergraphs from $\setHypergraphsH$

\begin{equation}
\label{eq:loc}
\weight{setX}(\hypergraphH) \in \sums \Z {\setof{\weight{setX'}(\hypergraphH ')}{\hypergraphH' = (\setVertices', \mu') \in {\setHypergraphsH},
\setX'\subseteq \setVertices', \size{\setX'} = \size{\setX}}}.
\end{equation}

Note that we only consider hypergraphs $\hypergraphH'\in {\setHypergraphsH}$, and we do not need to consider hypergraphs
$\hypergraphH' \in \eqs {\setHypergraphsH}$ equivalent to ones from ${\setHypergraphsH}$ as

\[\setof{\weight{setX'}(\hypergraphH')}{\hypergraphH' = (\setVertices', \mu') \in {\setHypergraphsH},
\setX'\subseteq \setVertices', \size{\setX'} = \size{\setX}} = \setof{\weight{setX}(\hypergraphH')}{\hypergraphH' \in \eqs {\setHypergraphsH}}.\]

The following conditions are equivalent,
for a finite set ${\setHypergraphsH}$ of hypergraphs and a hypergraph $\hypergraphH$, all of the same arity and dimension:

* $\hypergraphH$ is a $\Z$-sum of $\eqs{{\setHypergraphsH}}$;

* $\hypergraphH$ is locally a $\Z$-sum of ${\setHypergraphsH}$.

Before we embark on proving the result (in the next section) we first discuss how it
implies Theorem <ref>.
Recall that the arity ${\setSizeK}$ is fixed.
Instead of checking if $\hypergraphH = (\setVertices, \mu)$ is a $\Z$-sum of $\eqs{{\setHypergraphsH}}$, the
algorithm checks if
$\hypergraphH$ is locally a $\Z$-sum of ${\setHypergraphsH}$.
Observe that the condition (<ref>) amounts to solvability of a
(classical) system of linear equations, as in (<ref>)374.
Therefore, the algorithm tests $\Z$-solvability of a
system of the corresponding
$\dimension\cdot (1+\size{\setVertices}+\size{\kset{2}{\setVertices}}+\ldots \size{\kset{\setSizeK}{\setVertices}})$
linear equations,
$\dimension$ for every subset $\setX \subseteq \setVertices$ of the cardinality at most ${\setSizeK}$.
The number of equations is exponential in ${\setSizeK}$, but due to fixing ${\setSizeK}$
it is polynomial in the input hypergraphs $\hypergraphH$ and ${\setHypergraphsH}$.
Thus, Theorem <ref> is proved once we prove Theorem <ref>.

Let us recallcontinue379 Example <ref>. For the target we have that
$\weight{emptyset}(\changed{a}{\vec{v}}{379-381}_{\dc \dd})= \weight{dc} (\changed{a}{\vec{v}}{379-381}_{\dc \dd})= $
${\weight{dd}}(\changed{a}{\vec{v}}{379-381}_{\dc \dd})=$
${\weight{dc dd}}(\changed{a}{\vec{v}}{379-381}_{\dc \dd})= 6$,
and for the triangle we have
$\weight{emptyset}(\changed{a}{\vec{v}}{379-381}_{\dd \dc \de})=3$, $\weight{x}(\changed{a}{\vec{v}}{379-381}_{\dd \dc \de}) =2 $ for any $x\in \{\dd, \dc, \de\}$,
and $\weight{{ x, y}}(\changed{a}{\vec{v}}{379-381}_{\dd \dc \de})=1$ for any $\{x, y\}\subset \{\dd,\dc,\de\}$.

As $6 = 3 + 3$ and $6= 2+ 2+ 2$ and $6 = 1+ 1+ 1+1 +1 +1$ we see that
the target is locally a $\Z$-sum of the triangle. Hence the 383target is a
$\Z-$sum$\Z$-sum383 of the triangle up to equivalence. Moreover, if we change
$6$ to a smaller positive number then the target graph will not be
a $\Z$-sum of the triangle up to equivalence. For example if, we change $6$ toNULL $3$ can not be
expressed as a sum of twos., then $\vec{v}_{\dc \dd}$ is not a $\Z$-sum of the triangletrianglesNULL as ${\weight{dd}}(\vec{v}_{\dc \dd})=3$
is not divisible by $2$
i.e. the weight of any single vertex of the triangle.

§ PROOF OF THEOREM <REF> (THE CASE FOR K=2).

The implication $1 \implies 2$ is immediate.
Indeed, suppose $\hypergraphH = (\setVertices, \mu) = c_1 \cdot \hypergraphH_1 + \ldots + c_l \cdot \hypergraphH_l$,
where $c_i \in \Z$ and
$\hypergraphH_i \changed{= (\setVertices_i, \mu_i)}{}{NULL} \in \eqs {\setHypergraphsH}$.
Let $\setX\subseteq \setVertices$ be a subset of cardinality $\size{\setX} \leq \setSizeK$.
We  have

\[
\weight{setX}(\hypergraphH) = c_1 \cdot \weight{setX}(\hypergraphH_1) + \ldots + c_l \cdot \weight{setX}(\hypergraphH_l),
\]

which implies,
for some hypergraphs $\hypergraphH'_i = (\changed{\setVertices'_i}{\setVertices_i}{NULL}, \changed{\mu'_i}{\mu_i}{NULL}) \in {\setHypergraphsH}$ equivalent to
$\hypergraphH_i$, and subsets
$\setY_i \subseteq \changed{\setVertices'_i}{\setVertices_i}{NULL}$ of cardinality $\size{\setY_i} = \size{\setX}$,
the following equality holds

\[
\weight{setX}(\hypergraphH) = c_1 \cdot \weight{setY_1}(\hypergraphH_1') + \ldots + c_l \cdot \weight{setY_l}(\hypergraphH_l').
\]

As $\setX$ was chosen arbitrarily, this shows that $\hypergraphH$ is locally a $\Z$-sum of ${\setHypergraphsH}$.

The proof of the converse implication $2 \implies 1$ is much more involved. The case for arity $\setSizeK =1$ is considered in
Here, for pedagogical reasons, we provide a simplified version of the proof for arity $\setSizeK =2$, i.e., i.e.22 for (undirected) graphs.
The case for arity $\setSizeK =1$ is considered in
Consequently, we speak of edges instead of hyperedges.
We recall that the graphs we consider are actually $\ktuple{\dimension}{\Z}$-weighted graphs.

Let $\hypergraphH = (\setVertices , \mu)$ be a graph

and assume that $\hypergraphH$ is locally a $\Z$-sum of ${\setHypergraphsH}$.
We are going to demonstrate that $\hypergraphH$ is equivalent to a $\Z$-sum of $\eqs{{\setHypergraphsH}}$.
Since we work with arity $\setSizeK=2$,
the assumption amounts to the following conditions,
for every vertex $\da \in \setVertices$ and every edge $\edge \in \he \hypergraphH$:

\begin{equation}
\label{eq:ass0}
\weight{emptyset}(\hypergraphH) \in \sums \Z {\setof{\weight{emptyset}(\hypergraphH')\;}{\hypergraphH' = (\setVertices', \mu') \in {\setHypergraphsH}}}
\end{equation}

\begin{equation}\label{eq:ass1}
\weight{da}(\hypergraphH) \in \sums \Z {\setof{\weight{da'}(\hypergraphH')}{ \hypergraphH' = (\setVertices', \mu') \in {\setHypergraphsH},
\da' \in \setVertices'}}
\end{equation}

\begin{equation}\label{eq:ass2}
\weight{edge}(\hypergraphH) \in \sums \Z {\setof{\weight{edge'}(\hypergraphH')\,}{ \hypergraphH' = (\setVertices', \mu') \in {\setHypergraphsH},
\edge' \in \he {\hypergraphH'}}}.
\end{equation}

W.l.o.g. we may assume that $\hypergraphH = (\setVertices, \mu)$ satisfies $\weight{emptyset}(\hypergraphH) = {\vec{0}}$.

Indeed, due to the assumption (<ref>) and due the following equality
(note that the symbol $\sums \Z {\placeHolder}$ applies to vectors on the left,
and to graphs on the right)

\begin{equation}
\sums \Z {\setof{\weight{emptyset}(\hypergraphH')\;}{\hypergraphH' \in {\setHypergraphsH}}} =
{\setof{\weight{emptyset}(\hypergraphH')\;}{\hypergraphH' \in \sums \Z {\setHypergraphsH}}},
\end{equation}

there is a graph $\hypergraphH' = ({\setVertices}', \mu') \in \sums \Z {{\setHypergraphsH}}$
with $\weight{emptyset}(\hypergraphH') = \weight{emptyset}(\hypergraphH)$.
$\hypergraphH \in \sums \Z {\eqs{{\setHypergraphsH}}}$ if, and only if,325 $\hypergraphH-\hypergraphH' \in \sums \Z {\eqs{{\setHypergraphsH}}}$, and hence
we can replace $\hypergraphH$ by $\hypergraphH-\hypergraphH'$.
Note that, if $\hypergraphH$ is locally a ${\Z}$-sum of ${\setHypergraphsH}$ then $\hypergraphH-\hypergraphH'$ is also locally a ${\Z}$-sum of

We proceed in two steps.
We start by defining a class of particularly simple graphs, called $\hypergraphH$- graphs,
and argue that $\hypergraphH$ is a $\Z$-sum of these graphs (Lemma <ref> below).
Then we prove that every $\hypergraphH$- graph is representable as a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence
(Lemma <ref> below).
Composing the two claims we get that $\hypergraphH$ is a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence.
We may compose these two lemmas because of Lemma <ref>. By this we get that
$\hypergraphH$ is a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence.

This structure of the proof is correct due to the following simple lemma:421

For a family of ${\setSizeK}$-hypergraphs ${\setHypergraphsH}$$\setG$442 and ${\setSizeK}$-hypergraphs $\hypergraphH, \hypergraphH_1\ldots \hypergraphH_l$$\hypergraphG, \hypergraphG_1\ldots \hypergraphG_l$442, all of the
same dimension,
If $\hypergraphH_1\ldots \hypergraphH_l \in \sums \Z { \eqs {\setHypergraphsH}}$$\hypergraphG_1\ldots \hypergraphG_l \in \sums \Z { \eqs {\setG}}$422
and $\hypergraphH \in \sums \Z {\eqs{\{\hypergraphH_1\ldots
\hypergraphH_l\}}}$$\hypergraphG \in \sums \Z {\eqs{\{\hypergraphG_1\ldots
\hypergraphG_l\}}}$422 then
$\hypergraphH \in \sums \Z { \eqs {\setHypergraphsH}}$.$\hypergraphG \in \sums \Z { \eqs {\setG}}$.422

(Lemma <ref> is expressible, more succinctly, as

\[
\sums \Z {\eqs{\sums \Z { \eqs {\changed{\setHypergraphsH}{\setG}{422}}}}} = \sums \Z { \eqs {\changed{\setHypergraphsH}{\setG}{422}}}.)
\]

This is simply because of three trivial facts:

* $\eqs{{\hypergraphG}_i+{\hypergraphG}_j}\subseteq \eqs{{\hypergraphG}_i} + \eqs{{\hypergraphG}_j}$ where ${\hypergraphG}_i, {\hypergraphG}_j$ are any
${\setSizeK}$-hypergraphs of the same dimension, and the 429second plus
is the 429Minkowski sum.

* $\sums \Z \familyF= \sums \Z {\sums \Z \familyF}$, for any $\familyF$ a family of ${\setSizeK}$-hypergraphs of the same

* $\eqs \familyF= \eqs {\eqs \familyF}$, for any $\familyF$ a family of ${\setSizeK}$-hypergraphs of the same dimension.

\begin{align*}
\sums \Z {\eqs{\sums \Z { \eqs {\setHypergraphsH}}}} \subseteq  &&\text{ \changed{due to}{because of}{200} 1 }\\
\sums \Z {\sums \Z {\eqs {\eqs {\setHypergraphsH}}}}= &&\text{ \changed{due to}{because of}{200} 2 and 3}\\
\sums \Z {\eqs {\setHypergraphsH}}.&&
\end{align*}

The inclusion in the opposite direction is trivial.

For every vector $\vec a \in \ktuple{\dimension}{\Z}$ we define an $\vec a$-edge simple graph $\simpleGraph{2}{\vec a}$
(shown on the left) and an $\vec a$-vertex simple graph $\simpleGraph{1}{\vec a}$ (shown on the right):

We do not specify names of vertices, as anyway 443we will consider these graphs up to equivalence.
Both types of graphs we callWe call both types of graphs237  graphs.

\begin{align}\label{eq:defsetWeight2}
\setWeight{2}{\hypergraphH} = \sums \Z {\setof{\weight{edge}(\hypergraphH)}{\edge \in \he{\hypergraphH}}} \subseteq \ktuple{\dimension}{\Z}
\end{align}

\begin{align}\label{eq:defsetWeight1}
\setWeight{1}{\hypergraphH} = \sums \Z {\setof{\weight{da}(\hypergraphH)}{\da \in {\setVertices}}} \subseteq \ktuple{\dimension}{\Z}.
\end{align}

Now, let $\setSimpleGraph{1} \hypergraphH \eqdef \setof{\simpleGraph{1}{\vec a}}{\vec a \in \setWeight{1}{\hypergraphH}}$ and
$\setSimpleGraph{2}{\hypergraphH} \eqdef \setof{\simpleGraph{2}{\vec a}}{\vec a \in \setWeight{2}{\hypergraphH}}.$

$\hypergraphH \in \sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH} \cup \setSimpleGraph{2}{\hypergraphH}}}$.

Suppose $\hypergraphH= ({\setVertices}, \mu)$.
The proof of the lemma is done in steps.

There is a ${\hypergraphG}\in \sums{\Z}{\eqs{\setSimpleGraph{1}{\hypergraphH}}}$ such that for any vertex $\da\in \setD$ holdsit holds that451 $\weight{da}({\hypergraphG} +
\hypergraphH)
= {\vec{0}}$.

We will use it to further simplify our problem, as $\hypergraphH \in \sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH} \cup \setSimpleGraph{2}{\hypergraphH}}}$
if,325 and only if,325 ${\hypergraphG} + \hypergraphH \in \sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH} \cup
\setSimpleGraph{2}{\hypergraphH}}}$.

Let $\da, \da'$ arebe456 two vertices not in ${\setVertices}$ and let $\familyF\subseteq \setSimpleGraph{1}{\hypergraphH}$ be the family of all
$\simpleGraph{1}{\vec{a}}$  graphs (depicted below)

where $\vec{a}= \weight{db}(\hypergraphH)$ for $\db \in {\setVertices}$.

We define ${\hypergraphG}= \sum_{\hypergraphF\in \familyF} \hypergraphF$. As $\familyF\subset
\eqs{\setSimpleGraph{1}{\hypergraphH}}$,461 the
graph ${\hypergraphG}\in \sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH}}}$${\hypergraphG}$ is in $\sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH}}}$461. Moreover,

* for every $\db \in {\setVertices}$ holdsit holds that451 $-\weight{db}(\hypergraphH)=\weight{db}({\hypergraphG})$;

* $\weight{da}({\hypergraphG})={\vec{0}}$ as for each $\hypergraphF\in \familyF$,463 $\weight{da}(\hypergraphF) ={\vec{0}}$;

* $\weight{da'}({\hypergraphG})={\vec{0}}$ as $\weight{da'}({\hypergraphG})=\sum_{\db \in {\setVertices}} \weight{db}(\hypergraphH) =
where the second equality reflects the fact that every edge has two ends and the last equality is due to Claim <ref>.

As $\weight{x}$ is a homomorphism we get that $\weight{x}(\hypergraphH+{\hypergraphG}) ={\vec{0}}$ for every $x\in {\setVertices}\cup \{\da,\da'\}$. The same
holds for other vertices as they are isolated.

Due toBecause of200 the previous claim w.l.gw.l.o.g468 we may restrict our self to the following case.468-478
We assume that $\hypergraphH$ has following
propertiesthe following property468 $\weight{db}(\hypergraphH)=\vec{0}$
for every $\db\in \setVertices$for every $\db\in \setVertices$, it holds that $\weight{db}(\hypergraphH)=\vec{0}$468-469.

HereHere,169,170 there is one issue that should be discussed. Suppose $\hypergraphH'= \hypergraphH + \hypergraphG$ as in the471
Claim <ref>. The issue is that471
$\setSimpleGraph{1}{\hypergraphH} \cup \setSimpleGraph{2}{\hypergraphH} = \setSimpleGraph{1}{\hypergraphH'} \cup \setSimpleGraph{2}{\hypergraphH'}$ may not
So if we prove the lemma for $\hypergraphH'$ and $\setSimpleGraph{1}{\hypergraphH'} \cup \setSimpleGraph{2}{\hypergraphH'}$ it does not necessarily carry on 472
to $\hypergraphH$ and $\setSimpleGraph{1}{\hypergraphH} \cup \setSimpleGraph{2}{\hypergraphH}$.
Fortunately, it is sufficient for us if $\sums{\Z}{\setSimpleGraph{1}{\hypergraphH'} \cup \setSimpleGraph{2}{\hypergraphH'}} \subseteq
\sums{\Z}{\setSimpleGraph{1}{\hypergraphH} \cup
\setSimpleGraph{2}{\hypergraphH}}$. The last inclusion holds.
Indeed, for every $\db\in \setVertices'$ holdsit holds that451 $\weight{db}(\hypergraphH')$ is a sum of weights of vertices in $\hypergraphH$ thus
$\sums{\Z}{\setSimpleGraph{1}{\hypergraphH'}} \subseteq
\sums{\Z}{\setSimpleGraph{1}{\hypergraphH}}$ and similarly $\sums{\Z}{\setSimpleGraph{2}{{\hypergraphH'}}} \subseteq
\sums{\Z}{\setSimpleGraph{2}{\hypergraphH}}$.
Thus, we do not loose generality due tobecause of200 the proposed restriction.

There is a hypergraphgraph480 ${\hypergraphG\changed{}{'}{NULL}}\in \sums \Z {\eqs{\setSimpleGraph{2}{\hypergraphH}}}$
such that ${\hypergraphG\changed{}{'}{NULL}}=(\setVertices' ,\mu')$, $\hypergraphH + \hypergraphG\changed{}{'}{NULL}$ has at most $3$
non-isolatednonisolated107 vertices, and
$\weight{db}({\hypergraphH} + {\hypergraphG\changed{}{'}{NULL}})={\vec{0}}$ for everfor every481 $\db\in {\setVertices}\cup \setVertices'$.

We will use it to further simplify our problem, as $\hypergraphH \in \sums {\Z}  {\eqs{\setSimpleGraph{1}{\hypergraphH} \cup
\setSimpleGraph{2}{\hypergraphH}}}$ if,325 and only if,325
${\hypergraphH} + {\hypergraphG} \in \sums {\Z}  {\eqs{\setSimpleGraph{1}{\hypergraphH} \cup
\setSimpleGraph{2}{\hypergraphH}}}$.

We construct ${\hypergraphG}'$ gradually as a sum ${\hypergraphG}'=\sum_{i=1}^{last} {\hypergraphG}_i'$ in parallel with a sequence ${\hypergraphH_i}$
where $ {\hypergraphH_0}=  {\hypergraphH}$ and
$ {\hypergraphH_{i+1}}= {\hypergraphH_i} + {\hypergraphG}_{i+1}'$.
We construct ${\hypergraphG}'$ gradually as a sum of a sequence of graphs ${\hypergraphG}_1',{\hypergraphG}_2'\ldots{\hypergraphG}_{last}'$.
The sequence ${\hypergraphG}_i'$ is constructed in parallel with a sequence ${\hypergraphH_i}$
where $ {\hypergraphH_0}=  {\hypergraphH}$ and
$ {\hypergraphH_{i+1}}= {\hypergraphH_i} + {\hypergraphG}_{i+1}'$.486

The main property of the sequence $ {\hypergraphH_i}$ is that
$ {\hypergraphH_i}>  {\hypergraphH_{i+1}}$ in some well foundedwell-founded488
quasi orderquasi-order488 on graphs. Let $\ALG$ be an algorithmSuppose that, there is $\ALG$ an algorithm486-494, that takes as an
input $ {\hypergraphH_{i-1}}$ and produces the next ${\hypergraphG}_i'\in
\eqs{\setSimpleGraph{2}{\hypergraphH}}$. The
precondition of the algorithm $\ALG$ is that
$ {\hypergraphH_{i-1}}$ has more than $3$ non-isolatednonisolated107 vertices.
ThusNow486-494, due to the well-foundedness of the quasi order, the sequence ${\hypergraphG}_i'$ is finite.
Further, the graph $ {\hypergraphH_{last}}$ has at most $3$
non-isolatednonisolated107 vertices due tobecause of200 the precondition of $\ALG$.
To this end, we need to define the order on graphs and provide the algorithm $\ALG$.

Order on graphs We assume an arbitrary total order $<$ on vertices ${\setVertices}$495.
We lift the order to an order on edges $\{\da, \db\}$. We define it as the lexicographic order on
pairs $(\da, \db)$ satisfying $\da > \db$.
Finally, the order is extended to a quasi-order on graphs: ${\hypergraphG} < {\hypergraphG}'$ iff
$\edge < \edge'$, where $\edge$ and $\edge'$ are the largest edges in ${\hypergraphG}$ and ${\hypergraphG}'$, respectively.

The algorithm $\ALG$
Suppose,Suppose499 $(\da,\db)$$\{\da,\db\}$499 is the biggestlargest499 edge in the graph $ {\hypergraphH_i}$
and that $ {\hypergraphH_i}$ has at least $4$ non-isolatednonisolated107
Observe that
$\weight{da}( {\hypergraphH_i})={\vec{0}}$. Indeed, $\weight{da}( {\hypergraphH_i})=
\weight{da}(\hypergraphH+\sum_{j=1}^{i}{\hypergraphG}_j')=\weight{da}(\hypergraphH)+\sum_{j=1}^{i}\weight{da}({\hypergraphG}_j')=
{\vec{0}} + \sum_{j=1}^{i}\weight{da}({\hypergraphG}_j')$ but each ${\hypergraphG}_j'\in\eqs{\setSimpleGraph{2}{\hypergraphH}}$${\hypergraphG}_j'$ belongs to $\eqs{\setSimpleGraph{2}{\hypergraphH}}$503 and
by the definition of edge simple graphs $\weight{de}(\setSimpleGraph{2}{\hypergraphH})={\vec{0}}$ for every vertex $\de$.
As a consequence there must be at least one vertex $\dc\not\in \{\da,\db\}$ such
that $(\da,\dc)$ is an edge in $ {\hypergraphH_i}$. As $ {\hypergraphH_i}$ has at least $4$ non-isolatednonisolated107 vertices,
there is $\dd\not\in \{\dc,\da,\db\}$ a non-isolatednonisolated107 vertex in
$ {\hypergraphH_i}$. We define ${\hypergraphG}_{i+1}$${\hypergraphG}_{i+1}'$509 as follows

for $\vec{a} = \weight{{da,db}}( {\hypergraphH_i}).$

Observe that edges $(\da,\dc), (\db,\dd), (\dc,\dd)$ are smaller than the edge $(\da,\db)$ and $({\hypergraphH_i} +
{\hypergraphG}_{i+1})(\{\da,\db\})=\vec{0}$$({\hypergraphH_i} +
{\hypergraphG'}_{i+1})(\{\da,\db\})=\vec{0}$512 so
$ {\hypergraphH_i} + \changed{{\hypergraphG}_{i+1}}{{\hypergraphG'}_{i+1}}{512} <  {\hypergraphH_i}$.

After usage of the claim we get a graph $\hypergraphH'\eqdef \hypergraphH + \changed{\sum_{i=0}^{last} {\hypergraphG}_i'}{{\hypergraphG}'}{514}$. We know that
$\hypergraphH\in \sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH}\cup \setSimpleGraph{2}{\hypergraphH}}}$ if,325
only if,325
$ \hypergraphH'\in \sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH}\cup \setSimpleGraph{2}{\hypergraphH}}}$.
The graph $\hypergraphH'$ has at most $3$ non-isolatednonisolated107 nodesverticesNULL, $\weight{emptyset}(\hypergraphH')
={\vec{0}},$ and
$\weight{da}(\hypergraphH')={\vec{0}}$ for any vertex $\da$.

Suppose that the set of non-isolatednonisolated107 vertices of $\hypergraphH'$ is a subset of $\{\da,\db,\dc\}$. We may write the following system
of equations:

\begin{align}
\begin{split}
\weight{da}(\hypergraphH') = \weight{{da,db}}(\hypergraphH') + \weight{{da,dc}}(\hypergraphH') = {\vec{0}}\\
\weight{db}(\hypergraphH') = \weight{{da,db}}(\hypergraphH') + \weight{{db,dc}}(\hypergraphH') = {\vec{0}}\\
\weight{dc}(\hypergraphH') = \weight{{da,dc}}(\hypergraphH') + \weight{{db,dc}}(\hypergraphH') = {\vec{0}}
\end{split}
\label{eq:unique_solutions}
\end{align}

The only solution is $\weight{{da,db}}(\hypergraphH') = \weight{{db,dc}}(\hypergraphH') = \weight{{da,dc}}(\hypergraphH') = {\vec{0}}$. So $\hypergraphH'$
is the empty graph.
In consequence, $\hypergraphH = - \sum_{i=1}^{last}{\hypergraphG}_i \in \sums \Z {\eqs{\setSimpleGraph{1}{\hypergraphH}\cup
\setSimpleGraph{2}{\hypergraphH}}}$, which completes
the proof of Lemma <ref>.

§ REPRESENTATION OF $\HYPERGRAPHH$- GRAPHS

As the second step,527 we prove that every $\hypergraphH$- graphsgraph528 is
representable as a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence (Lemma <ref>). We start fromwith529 two preparatory lemmas.

Let $\edge\in \he{{\hypergraphG}}$ for a graph ${\hypergraphG} = ({\setVertices\changed{}{'}{NULL}}, \mu\changed{}{'}{NULL})$, and let
$\weight{edge}({\hypergraphG}) = \vec a$.
Then $\simpleGraph{2}{\vec a} \in \sums \Z {\eqs{\{\hypergraphG\}}}$.

Let $\edge = \{\da, \db\} \subseteq {\setVertices\changed{}{'}{NULL}}$, $\weight{edge}({\hypergraphG}) = \vec a$, and let $\dc, \dd \notin
{\setVertices\changed{}{'}{NULL}}$ arebe532 two additional
vertices outside of ${\setVertices\changed{}{'}{NULL}}$. We consider three graphs ${\hypergraphG}_1, {\hypergraphG}_2, {\hypergraphG}_{12}$ which differ from
only by:

* replacing $\da$ with $\dc$ (in case of ${\hypergraphG}_1$),

* replacing $\db$ with $\dd$ (in case of ${\hypergraphG}_2$),

* replacing both $\da$ and $\db$ with $\dc$ and $\dd$, respectively (in case of ${\hypergraphG}_{12}$).

Clearly all the three graphs are equivalent to ${\hypergraphG}$.
We claim that ${\hypergraphG} - {\hypergraphG}_1 - {\hypergraphG}_2 + {\hypergraphG}_{12}$ yields:

that is a graph equivalent to $\simpleGraph{2}{\vec a}$.
Indeed, the above graph operations cancel out
all edges non-incidentnonadjacent107 to the four vertices $\da, \db, \dc, \dd$,
as well as all edges incidentadjacentNULL to only one of them.
The two horizontal $\vec a$-weighted edges originate from ${\hypergraphG}$ and ${\hypergraphG}_{12}$,
while the two remaining vertical ones originate from $-{\hypergraphG}_1$ and $-{\hypergraphG}_2$.

Let $\da\in {\setVertices\changed{}{'}{NULL}}$ be a vertex of a graph ${\hypergraphG} = ({\setVertices\changed{}{'}{NULL}}, \mu\changed{}{'}{NULL})$, and let
$\weight{da}({\hypergraphG}) = \vec a$.
Then $\simpleGraph{1}{\vec a} \in \sums \Z {\eqs{\{\hypergraphG\}}}$.

Let a graph ${\hypergraphG}'$ differ from ${\hypergraphG}$ only by
replacing $\da$ with a fresh vertex $\db \notin {\setVertices\changed{}{'}{NULL}}$.
The graph ${\hypergraphG} - {\hypergraphG}'$ has the following shape (with blue square vertices representing
the set ${\setVertices\changed{}{'}{NULL}} \setminus \{\da\} = \{\dc_1, \dc_2\ldots \dc_n\}$):

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm,
stplace/.style=rectangle,draw=!20,fill=!20,thick,inner sep=0pt,minimum size=4mm
[place]    (V)     at ( 0,0.3)    $\da$;
[place]      (V1)       at (0,-1.3)  $\db$;
[stplace]      (A1)      at ( -1.5,-0.5)   $\dc_1$;
[stplace]      (A11)     at ( 0,-0.5)  $\dc_2$;
[]      (A111d2)    at ( 1.5,-0.5)  $\ldots$;
[stplace]      (A1111)    at ( 4,-0.5)  $\dc_n$;

(V) to node [above, sloped] $\vec v_1$ (A1) to node [below, sloped] $-\vec v_1$ (V1) ;
(V) to node [right] $\vec v_2$ (A11) to node [right] $-\vec v_2$ (V1) ;
[bend left=15] (V) to node [ above, sloped] $\vec v_n$ (A1111);
[bend left=15] (A1111) to node [below, sloped] $-\vec v_n$ (V1) ;

Relying on Lemma <ref>, we add to the graph ${\hypergraphG} - {\hypergraphG}'$ the following graphs equivalent to
$\simpleGraph{2}{\vec v_i}$, for $i = 1, 2\ldots n-1$:

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm,
stplace/.style=rectangle,draw=!20,fill=!20,thick,inner sep=0pt,minimum size=4mm
[place]    (Vd)         [below= of A11] $\da$;
[place]      (V1d)       [below=of Vd]  $\db$;
[stplace]      (A1d)      at (-1.5,-2.5)   $\dc_i$;
[stplace]      (A1111d)    at (4,-2.5)  $\dc_n$;

(Vd) to node [above, sloped] $-\vec v_i$ (A1d) to node [below, sloped] $\vec v_i$ (V1d) ;
[bend left=15] (Vd) to node [above, sloped] $\vec v_i$ (A1111d);
[bend left=15] (A1111d) to node [below, sloped] $-\vec v_i$ (V1d) ;

This results in collapsing all blue vertices into one:

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=4mm,
stplace/.style=rectangle,draw=!20,fill=!20,thick,inner sep=0pt,minimum size=4mm
[place]    (V)         $\da$;
[place]    (V1)   at (7,0)    $\db$;
[stplace]      (A1)      at ( 3.5,0)   $\dc_n$;
(V) to node [above] $\vec v_1+\ldots+\vec v_n$ (A1) to node [above] $-(\vec v_1+\ldots+\vec v_n)$ (V1) ;

Since $\vec a = \vec v_1 + \ldots + \vec v_n$, the resulting graph is equivalent to $\simpleGraph{1}{\vec a}$, as required.

Every $\hypergraphH$- graph is a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence:
$\setSimpleGraph{1} \hypergraphH \subseteq \sums \Z {\eqs{{\setHypergraphsH}\}}}$ and $\setSimpleGraph{2} \hypergraphH \subseteq \sums \Z

Let $\hypergraphH = ({\setVertices}, \mu)$. We have to prove that for any $\vec{a}\in \changed{\setWeight{2}{\hypergraphH}}{\setWeight{1}{\hypergraphH}}{NULL}$
($\setWeight{1}{\hypergraphH}$ is defined in Equation <ref>)571 holdsit holds that451 $\simpleGraph{1}{\vec{a}}\in
\sums{\Z}{\eqs{\setHypergraphsH}}$ and that for any $\vec{b}\in \changed{\setWeight{1}{\hypergraphH}}{\setWeight{2}{\hypergraphH}}{NULL}$
($\setWeight{2}{\hypergraphH}$ is
defined in Equation <ref>)571 holdsit holds that451 $\simpleGraph{2}{\vec{b}}\in
\sums{\Z}{\eqs{\setHypergraphsH}}$. We prove only $\simpleGraph{1}{\vec{a}}\in
\sums{\Z}{\eqs{\setHypergraphsH}}$ as the second proof is the almost same.
Due toBecause of200 Lemma <ref> we know that

\[
\sums{\Z}{\eqs{\sums{\Z}{\eqs{\setHypergraphsH}}}}=\sums{\Z}{\eqs{\setHypergraphsH}}.
\]

Thus, due tobecause of200 Lemma <ref> it is sufficient to prove that there is a graph $\hypergraphG_{\vec{a}}\in \sums{\Z}{\eqs{\setHypergraphsH}}$ such
that $\weight{da}({\hypergraphG}_{\vec{a}})=\vec{a}$.

As $\vec a\in \changed{\setWeight{2}{\hypergraphH}}{\setWeight{1}{\hypergraphH}}{NULL}$ we know that581

\begin{align}\label{eq:a}
\vec a = z_1 \cdot \vec a_1 + \ldots + z_l \cdot \vec a_l,
\end{align}

where $z_i\in \Z$ and $\vec{a_i}$ is $\weight{db_i}(\hypergraphH)$ for some $\db_i\in {\setVertices}$.
By the assumption (<ref>), for every $i$ we know

\[
\vec a_i \in \sums \Z {\setof{\weight{dc_i}(\hypergraphH')}{\hypergraphH' = ({\setVertices}', \mu') \in {\setHypergraphsH}, \dc_i \in {\setVertices}'}}.
\]

we may use the equivalence relation and rewrite it as follows

\[
\vec a_i \in \sums \Z {\setof{\weight{da}(\hypergraphH')}{\hypergraphH' = ({\setVertices}', \mu') \in \eqs{{\setHypergraphsH}}}}.\\
\]

We concretize itThus585

\[
\vec a_i = z_{i,1} \weight{da}(\hypergraphH'_{i,1}) + z_{i,2} \weight{da}(\hypergraphH'_{i,2}) +\ldots + z_{i,h(i)} \weight{da}(\hypergraphH'_{i,\changed{h}{h(i)}{586}}) \text{ and
further }
\]

\[
\vec{a} = \sum_{i=1}^{l} z_i \left( z_{i,1} \weight{da}(\hypergraphH'_{i,1}) + z_{i,2} \weight{da}(\hypergraphH'_{i,2}) +\ldots + z_{i, h(i)}
\weight{da}(\hypergraphH'_{i,h(i)}) \right)
\]

$\weight{da}$ is a homomorphism, so

\[
\vec{a} = \weight{da}\left(\sum_{i=1}^{l} z_i \left( z_{i,1} \hypergraphH'_{i,1} + z_{i,2} \hypergraphH'_{i,2} +\ldots + z_{i, h(i)} \hypergraphH'_{i,h(i)}
\right)\right)
\]

so we  define

\[
{\hypergraphG}_{\vec{a}} \eqdef \sum_{i=1}^{l} z_i \left( z_{i,1} \hypergraphH'_{i,1} + z_{i,2} \hypergraphH'_{i,2} +\ldots + z_{i, h(i)}
\hypergraphH'_{i,h(i)}\right).
\]

The construction of elements of $\setSimpleGraph{2}{\hypergraphH}$ relays on Lemma <ref> instead of Lemma <ref>.

Combining Lemmas <ref> and <ref> we know that $\hypergraphH$ is
a $\Z$-sum of $\hypergraphH$- graphs, each of which in turn is a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence.
By Lemma <ref>, $\hypergraphH$ is a $\Z$-sum of ${\setHypergraphsH}$ up to equivalence, as required.
The proof of Theorem <ref>, for graphs, is thus completed.

§ PROOF OF THEOREM <REF> (THE OUTLINE).

Now,NULL we are ready to prove the implication $2 \implies 1$ from Theorem <ref> in full generality.
The proof is split into five parts. We want to mimic the approach presented in Section <ref>, thus we need to generalise a 608few things:

* In Section <ref> we build an algebraic background to be able to solve systems of equations that in the general case correspond to
Equations <ref>.

* In Section <ref> we introduce simple hypergraphs that generalise graphs defined in Definition <ref>.

* In Section <ref> we show that our target hypergraph is a $\Z$-sum of simple
hypergraphs. This generalises Lemma <ref>.NULL

* In Section <ref> we prove that simple hypergraphs are $\Z$-sums of
$\eqs{{\setHypergraphsH}}$. This generalises Subsection Representation of $\hypergraphH$- graphs i.e.
Lemmas <ref>, <ref>, and <ref>.NULL

* Finally, in Section <ref> we complete the proof of Theorem <ref>.

§ REDUCTION MATRICES.

In this section we introduce a notion of reduction matrices and
prove a key
lemma about their rank, Lemma <ref>. They are
$0,1$ matrices related to adjacency matrices of Kneser graphs. We recall that by $x-$set$x$-set619 we mean a set with $x$ elements.

Let $a\in \N$ and $\setA$ be an $a$-set.
Matrix is a reduction matrix for $a \geq b \geq c$, $a,b,c \in \mathbb{N}$, denoted by $\reductionMatrix{a}{b}{c}$, if
For $a \geq b \geq c$, $a,b,c \in \mathbb{N}$, we define a matrix $\reductionMatrix{a}{b}{c}$ as follows:

* it has $\binom{a}{b}$ columns and $\binom{a}{c}$ rows, 622

* columns and rows are indexed with $b$-element subsets of $\setA$ and $c$-element subsets of $\setA$, respectively,

* $\reductionMatrix{a}{b}{c}[\setC,\setB]=1$ if $\setC\subseteq \setB$ and $0$ otherwise,
where $\setC$ is an index of a row and $\setB$ is an index of a column.

The definition is up to reordering of rows and columns.622

Suppose $\setA=\{\da,\db,\dc,\dd\}$.626

* $\begin{bmatrix}
\reductionMatrix{4}{3}{1}
\end{bmatrix}
\begin{bmatrix}
&\{\dc,\db,\da\} &\{\dd,\db,\da\} &\{\dd,\dc,\da\} & \{\dd,\dc,\db\} \\
\{\da\} & 1 & 1 & 1 & 0 \\
\{\db\} & 1 & 1 & 0 & 1 \\
\{\dc\} & 1 & 0 & 1 & 1 \\
\{\dd\} & 0 & 1 & 1 & 1
\end{bmatrix}$ 4.5cm
up to a permutation of rows and columns.

* $\begin{bmatrix}
\reductionMatrix{4}{2}{1}
\end{bmatrix}
\begin{bmatrix}
& \{\db,\da\} &\{\dc,\da\}&\{\dc,\db\}&\{\dd,\da\}&\{\dd,\db\}&\{\dd,\dc\}\\
\{\da\}& 1 & 1 & 1 & 0 & 0 & 0 \\
\{\db\}& 1 & 0 & 0 & 1 & 1 & 0 \\
\{\dc\}& 0 & 1 & 0 & 1 & 0 & 1 \\
\{\dd\}& 0 & 0 & 1 & 0 & 1 & 1
\end{bmatrix}$3.5cm
up to a permutation of rows and columns.

The below lemma expresses the important property of reduction matrices.

Any $\reductionMatrix{2{\setSizeK}+1}{{\setSizeK}+1}{{\setSizeK}}$ reduction matrix has maximal rank.

The proof relies on thea640 result from the spectral theory of Kneser graphs.

Kneser graph.NULL
Let $\setA$ be an $a$-set.
The Kneser graph Kneser graph641 $K_{a,c}$ is the graph whose vertices are $c$-element subsets of $\setA$,
and where two vertices $x,y$ are adjacent if,325 and only if,325 $x\cap y=\emptyset$.

The incidenceadjacencyNULL matrix of 644a graph $({\setX},E)$ is a ${\setX}\times {\setX}$-matrix $M$ such that
$M[x,y]=1$ if $x,y$ are adjacentthere is an edge between $x$ and $y$645 and $0$ otherwise.

All eigenvalues of the incidenceadjacencyNULL matrix for a Kneser graph are non-zerononzero107.

The rank of the incidenceadjacencyNULL matrix for a Kneser graph is maximal.

We relabel columns of $\reductionMatrix{2{\setSizeK}+1}{{\setSizeK}+1}{{\setSizeK}}$ in the following way. If a column is labelled with
the set $\setB\subset \setA$ we relabel it to $\setA\setminus \setB$. Now,NULL both rows and columns are labelled with
${\setSizeK}$-subsets of $\setA$.  We denoteNULL the relabelled matrix byNULL $M'$.
On the one hand, observe that if a ${\setSizeK}$-set $\setC$ is a subset of a $\setSizeK+1$-$(\setSizeK+1)$-779set $\setB$ then
$\setC\cap (\setA\setminus \setB)=\emptyset$, in which case $M'[\setC, \setA\setminus \setB]=1$.
On the other hand if a ${\setSizeK}$-set $\setC$ is not a subset of a $\setSizeK+1$-$(\setSizeK+1)$-779set $\setB$ then
$\setC\cap (\setA\setminus \setB)\neq \emptyset$, and $M'[ \setC, \setA\setminus \setB]=0$.
So we see that $M'$ is the incidenceadjacencyNULL matrix of
the Kneser graph $K_{2{\setSizeK}+1,{\setSizeK}}$. But due to, because of200 Corollary <ref>,655 it has maximal rank, and the same holds for $M$
as relabelling of columns does not change the rank of the matrix.

§ SIMPLE HYPERGRAPHS.

Let ${\hypergraphH}=(\setVertices,\mu)$ be a ${\setSizeK}$-hypergraph. We say that it is $m$-isolated
if for any subset $\setX \subseteq {\setVertices}$ such that $\size{\setX}\leq m$ holdsit holds that451

Let $0\leq m \leq \setSizeK$ and $\vec{a}\in \ktuple{\dimension}{\Z}$658. We call a ${\setSizeK}$-hypergraph
${\hypergraphG}=({\setVertices\changed{}{'}{NULL}},\mu\changed{}{'}{NULL})$ $(m, \vec{a})$-
if there exist pairwise disjoint sets $\setA, \setB, \setC$ such that

* ${\setVertices\changed{}{'}{NULL}} = \setA \cup \setB \cup \setC$.

* $\setA = \{\da_1, \da_2 \ldots \da_m\}$ and $\setB = \{\db_1, \db_2 \ldots \db_m\}$ are $m$-sets.

* $\size{\setC} = 2({\setSizeK}-m)-1$ or $\setC=\emptyset$ if $m=\setSizeK$.

* $\forall \setX\subseteq \setA\cup \setB$, such that $\setX = \{x_1, x_2 \ldots x_m\}$,
where $x_i \in \{\da_i,\db_i\}$, the equality $\weight{setX}({\hypergraphG})= (-1)^{\size{\setB \cap \setX}}\cdot \vec{a}\ $ holds.

* For any other $\setX \subseteq {\setVertices\changed{}{'}{NULL}}$ such that $\size{\setX} = m$ the equality $\weight{setX}({\hypergraphG}) = \vec{0}$

* $\forall{\setX\subseteq {\setVertices}}$, such that $\size{\setX}<m$ the equality $\weight{setX}({\hypergraphG})=\vec{0}$ holds.

* $\hypergraphG$ is $(m-1)$-isolated.666

This definition looks horribleis hard667 so we analyse it using examples, and explain the required properties.
Also, observe that contrary to $\simpleGraph{1}{\vec a}$ and $\simpleGraph{2}{\vec a}$ $(m, \vec{a})$- hypergraphs
are not fully specified up to isomorphism. Further, it is not clear that they exist for all $(m, \vec{a})$. In the example below we comment on this as well667

From the left to the right: a $(0,\vec{a})-\simple$$(0,\vec{a})$-20 $2$-hypergraph ${\hypergraphG}_0$, where
a $(1,\vec{a})-\simple$$(1,\vec{a})$-20 $2$-hypergraph ${\hypergraphG}_1$;
a $(2,\vec{a})-\simple$$(2,\vec{a})$-20 $2$-hypergraph ${\hypergraphG}_2.$ The sets $\red{\setA},\blue{\setB},\green{\setC}$ are marked
with colours.

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=3mm]
[place, color=] (A) ;
[place, color=] (B) [below left=of A] ;
[place, color=] (C) [below right=of A] ;
(A) to node [above, sloped] $\vec{x}$ (B) to node [above] $\vec{y}$ (C) to node [above, sloped] $\vec{z}$ (A);

[place, color=] (A1) [right =of C] ;
[place, color=] (B1) [above left=of A1] ;
[place, color=] (C1) [above right=of A1] ;
(B1) to node [above, sloped] a (A1) to node [above, sloped] -a (C1) ;

[place, color=] (A2) [right =of C1] ;
[place, color=] (B2) [below =of A2] ;
[place, color=] (C2) [right =of A2] ;
[place, color=] (D2) [below =of C2] ;

(A2) to node [left] a (B2) to node [above] -a (D2) to node [right] a (C2) to node [above] -a (A2);

* If $m=0$ then $\setA, \setB$ are empty, conditionProperty685-688 2 states that $\setC$ has $3$ vertices,
conditionProperty685-688 $4$ that
conditionsProperties685-688 $5$ and

* If $m=1$ then $\size{\setA}=\size{\setB}=\size{\setC}=1$, conditionsProperties685-688 $4$ and $5$ provide 3 equations

\begin{align}
\vec{a}=\weight{red{bullet}}({\hypergraphG}_1)=\weight{{red{bullet},green{bullet}}}({\hypergraphG}_1)+\weight{{red{bullet},blue{bullet}}}({
\hypergraphG}_1) \\
({\hypergraphG}_1) \\
\vec{0}=\weight{green{bullet}}({\hypergraphG}_1)=\weight{{blue{\bullet},green{bullet}}}({\hypergraphG}_1)+\weight{{red{bullet},green{bullet}}}
\end{align}

It is not hard to derive from them that $\vec{a}=\weight{{red{bullet},green{bullet}}}({\hypergraphG}_1)$, $-\vec{a} =
\weight{{blue{\bullet},green{bullet}}}({\hypergraphG}_1)$,
and $\vec{0}=
\weight{{red{bullet},blue{bullet}}}({\hypergraphG}_1)$.
The conditionProperty685-688 $6$ states that $\weight{emptyset}({\hypergraphG}_1)=\vec{0}$.

* If $m=2$ then $\size{\setA}=\size{\setB}=2$ and $\setC=\emptyset$. Conditions $4$ and $5$ define weights of all edges, the conditionProperty685-688 $4$ is responsible
edges with non-zerononzero107 weights and $5$ for the edges with the weight $\vec{0}$. The conditionProperty685-688 $6$ says that
the weight of $\emptyset$ and weights of single
are $\vec{0}$.

Note that $(m,\vec{a})$- hypergraphs are not defined uniquely. For example, the711 $(0,\vec{a})$- hypergraph from the example above is not fully
defined, as for any $\vec{x}$ and $\vec{y}$ we may choose appropriate $\vec{z}=\vec{a}-\vec{x}-\vec{y}$712.
The existence of all  hypergraphs is proven later (we show how to construct them).

Now, why we characterise   hypergraphs using such complicated conditionsProperties685-688?
In the following we justify our design.703
The most important property of   hypergraph is the last one. It implies the following lemma:

Let $\hypergraphG=(\setVertices', \mu')$ be a ${\setSizeK}$-hypergraph and $\simpleGraph{m}{\vec{a}}$ be an
$(m,\vec{a})-\simple$$(m,\vec{a})$-20 ${\setSizeK}$-hypergraph.
Then for any $\setX \subseteq {\setVertices'}, \size{\setX} < m$ we have $\weight{setX}(\hypergraphG) = \weight{setX}(\hypergraphG+
\simpleGraph{m}{\vec{a}})$.

Indeed, $\weight{setX}$ is a homomorphism and
$\weight{setX}(\simpleGraph{m}{\vec{a}})=\vec{0}$ due tobecause of200 propertyPropertyNULL
6 of694 Definition <ref>.

It justifiesProperty $6$, by this lemma, allows for703 the following
structure of the proof of the theoremTheorem
We gradually simplify yourthe696 target hypergraph by adding $(i,\vec{a})$- hypergraphs for
growing $i$. In the step $i$ we start from a hypergraph
with $\weight{setX}(\hypergraphH)=\vec{0}$ for every $\setX\subset \setVertices$ with at most $i-1$ vertices.an $(i-1)$-isolated hypergraph.666 Using
$(i,\vec{a})$- hypergraphs we
simplify it to a hypergraph with $\weight{setX}(\hypergraphH)=\vec{0}$ for all $\setX\subset \setVertices$ with exactly $i$ vertices.
The property $6$ guaranties that
while we perform the step $i$, we do not ruin our work from previous steps i.e. we reach a hypergraph suchsuch that700
$\weight{setX}(\hypergraphH)=\vec{0}$ for every
$\setX\subset \setVertices$ with at most $i$ vertices.an $i$-isolated hypergraph.666
Eventually, we reach a hypergraph with all the weights equal to702 $\vec{0}$ i.e. the empty hypergraph.

Now, let us justify the design of703 conditionsProperties685-688 $4$ and $5$. We already mentioned that using $(i,\vec{a})$- hypergraphs we want to reduce to $\vec{0}$ all weights of sets in
$\kset{i}{{\setVertices}}$; thus it is good to keep weights on the level $i$ as
simple as possible, i.e. i.e.22 $\vec{a},\vec{0},-\vec{a}$.

OtherThe designs of703 conditionsProperties $1$-$3$685-688 areis703 a trade-off between two things:

* we wantedwe want707 to have   hypergraphs as small as possible in terms of number of vertices and number of

* required   hypergraphs must be in $\sums{\Z}{\eqs{{\setHypergraphsH}}}$.
for the proof of Theorem <ref>, we need that  hypergraphs, from which we construct the target hypergraph $\hypergraphH$, may be constructed from
hypergraphs in the family $\setHypergraphsH$.

Note that $(m,\vec{a})$- hypergraph are not defined uniquely. For example $(0,\vec{a})$- hypergraph from the example above is not fully
It is also not clear if   hypergraphs exist, this is proven later (we show how to construct them).

Now, that Properties $1$-$6$ are commented, we may go back to the proof of the Theorem <ref>.703

We alsoNULL introduce $2$two714 other notions to work with families of   hypergraphs.

Let $\setG$ be a family of ${\setSizeK}$-hypergraphs. $\hypergraphG=({\setVertices}_{\hypergraphG}, \mu_{\hypergraphG})$ for every $\hypergraphG\in \setG$, for every $\hypergraphG\in \setG$ we denote the set of its vertices by $\setVertices_{\hypergraphG}$.715
For every $0\leq m\leq \setSizeK$,716 let ${\groupG}_m$ be athe716 group generated by
$\setof{\weight{setX}(\hypergraphG)}{ \changed{\text{ for every }}{}{716} \hypergraphG\in \setG, \setX\in
\kset{\changed{i}{m}{716}}{{\setVertices}_{\hypergraphG}}}$.
A family of ${\setSizeK}$-hypergraphs $\setS$ is a simplification of the family
$\setG$ if for every $0\leq m\leq\setSizeK$ and
every $\vec{g}\in
{\groupG}_m$ it contains an $(m,\vec{g})-\simple$$(m,\vec{g})$-20 ${\setSizeK}$-hypergraph.

A family of ${\setSizeK}$-hypergraphs $\setS$ is a simplification of the family $\setG$ if
for every $0\leq m\leq\setSizeK$ and
every $\vec{g}$ in
$\Z$-sums of $\setof{\weight{setX}(\hypergraphG)}{ \changed{\text{ for every }}{}{716} \hypergraphG\in \setG, \setX\in
\kset{\changed{i}{m}{716}}{{\setVertices}_{\hypergraphG}}}$ it contains an
$(m,\vec{g})-\simple$$(m,\vec{g})$-20 ${\setSizeK}$-hypergraph.
716 and (last) 716

The family $\setS$ is simple for itselfself-simplified720 if $\setS$ is a simplification of $\setS$.
A family $\setS$ is simple for a given ${\setSizeK}$-hypergraph
$\hypergraphH=({\setVertices},\weight{hypergraphH})$For a family of
${\setSizeK}$-hypergraphs $\setHypergraphsH$,
a family $\setS$ is simple for $\setHypergraphsH$
NULL if
is a family simple for itselfself-simplified720 and is
a simplification of $\setHypergraphsH$.

To produce a simpleself-simplified721 family,
it suffices to design an algorithm $alg(\setS)$ that produces a simplification of its input.
As a simpleself-simplified721 family we
takeThe following family is self-simplified724

\[
\bigcup_{i\in \N} alg^{i+1}(\setHypergraphsH) \text{ where }
alg^i \text{ is i-th iteration of the}\ alg.
\]

Note that the produced family is not necessarily finite.

FigureThe picture below729 presents an example of a simple family $\setG$ for the graph $\hypergraphH$.
$z \in \Z$ and the sets $\red{\setA},\blue{\setB},\green{\setC}$ are marked with colours.

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=3mm]
(G) at (-2,-0.5) ${\hypergraphH} =$;

[place] (A) ;
[place] (B) [below left=of A] ;
[place] (C) [below right=of A] ;
(A) to node [above, sloped] $\vec{x_1}$ (B) to node [above] $\vec{x_2}$ (C) to node [above, sloped] $\vec{x_3}$ (A);

[place, color=] (A1) at (-2, -3) ;
[place, color=] (B1) [below left=of A1] ;
[place, color=] (C1) [below right=of A1] ;
(A1) to node [above, sloped] $z\cdot \vec{x_1}$ (B1) to node [above] $z\cdot \vec{x_2}$ (C1) to node [above, sloped] $z\cdot \vec{x_3}$ (A1);

[place, color=] (A2) at (-2, -5) ;
[place, color=mycol3] (B2) [below left=of A2] ;
[place, color=] (C2) [below right=of A2] ;
(B2) to node [above, sloped] $\vec{a}$ (A2) to node [above, sloped] $-\vec{a}$ (C2) ;

(X0) at (2.2, -4) for anyallNULL $z\in \Z$.;

(X1) at (5.3, -6) where $\vec{a}$ isfor all $\vec{a}$NULL in $\sums{\Z}{\{ \vec{x_1}+ \vec{x_2},\ \vec{x_2}+\vec{x_3},\
\vec{x_3}+\vec{x_1}\}}$.;

[place, color=mycol3] (A21) at (-2.7, -8.5) ;
[place, color=mycol3] (B21) [above =of A21] ;
[place, color=] (C21) [right =of A21] ;
[place, color=] (D21) [above =of C21] ;

(A21) to node [left] $\vec{y}$ (B21) to node [above] $-\vec{y}$ (D21) to node [right] $\vec{y}$ (C21) to node [above] $-\vec{y}$ (A21);

(X1) at (4, -8) where $\vec{y}$ isfor all $\vec{y}$NULL in $\sums{\Z}{\{ \vec{x_1},\ \vec{x_2},\ \vec{x_3}\}}$.;

The family is infinite. Depicted graphs represent $(0,z(\vec{x_1}+\vec{x_2}+\vec{x_3}))$-simple hypergraphs, $(1,\vec{a})$-simple hypergraphs,
$(2,\vec{y})$-simple hypergraphs. To see that the family is self-simplified we observe the few following facts:

* $\setof{\weight{emptyset}(\hypergraphG)}{ \hypergraphG\in \setG} = \setof{z(\vec{x_1}+\vec{x_2}+\vec{x_3})}{z\in \Z}=
{\sums{\Z}{\setof{z(\vec{x_1}+\vec{x_2}+\vec{x_3})}{z\in \Z}}} $. Indeed,
$\weight{emptyset}(\hypergraphG) = \vec{0}$ for $\hypergraphG$ of the second or the third type of graphs. So the family contains all required
$(0,\placeHolder)$- graphs (triangles).

* $\setof{\weight{da}(\hypergraphG)}{ \hypergraphG=(\setVertices_{\hypergraphG}, \mu_{\hypergraphG})\in \setG, \da\in \setVertices_{\hypergraphG}} =
\setof{\vec{a}}{\vec{a}\in\sums{\Z}{\{ \vec{x_1}+ \vec{x_2},\ \vec{x_2}+\vec{x_3},\ \vec{x_3}+\vec{x_1}\}}}$.
This is because of,

* $\weight{da}(\hypergraphG) = \vec{0}$ for any $\hypergraphG=(\setVertices_{\hypergraphG}, \mu_{\hypergraphG})$ of the third type of graphs and any
$\da\in \setVertices_{\hypergraphG}$.

* $\weight{da}(\hypergraphG) = \vec{0}$ for $\hypergraphG$ of the second type of graphs and $\da$ being the middle vertex.

* it is easy to check that $\weight{da}(\hypergraphG) \in  \setof{\vec{a}}{\sums{\Z}{\{ \vec{x_1}+ \vec{x_2},\ \vec{x_2}+\vec{x_3},\
\vec{x_3}+\vec{x_1}\}}}$ also for other cases.

Thus, the family contains all required
$(1,\vec{a})$- graphs (the second type).

* $\setof{\weight{{da,db}}(\hypergraphG)}{ \hypergraphG=(\setVertices_{\hypergraphG}, \mu_{\hypergraphG})\in \setG,
\{\da,\db\}\in \kset{2}{\setVertices_{\hypergraphG}}} =
\setof{\vec{a}}{\sums{\Z}{\{ \vec{x_1},\ \vec{x_2},\ \vec{x_3}\}}}$. This is also easy to check.

Because of $\sums{\Z}{\sums{\Z}{\setX}}=\sums{\Z}{\setX}$ for any set $\setX$, we see that all needed  graphs are elements of the family $\setG$.
Thus, the family contains all required
$(2,\vec{y})$- graphs (the square type).

Let $\setS$ be a family simple for a $\setSizeK$-749hypergraph ${\hypergraphH}$. Suppose $\hypergraphG\in \sums{\Z}{\eqs{\setS}}$ then the family
$\setS$ is simple for

Let $\setX$ be a subset of vertices of ${\hypergraphH}+\hypergraphG$. By definition,747 if in $\setS$ there are $(i,\vec{a})$- and
hypergraphs then there is an
$(i,\vec{a}+\vec{b})$- hypergraph too. Thus, it is sufficient to prove that if $\size{\setX}\leq \setSizeK$ then in $\setS$ there is a
$(\size{\setX},\weight{setX}({\hypergraphH}+\hypergraphG))-$simple hypergraph.
Which is also trivial as $\weight{setX}({\hypergraphH}+\hypergraphG)=\weight{setX}({\hypergraphH}) + \weight{setX}(\hypergraphG)$ and in $\setS$ there are
$(\size{\setX},\weight{setX}({\hypergraphH}))-$simple and $(\size{\setX},\weight{setX}(\hypergraphG))-$
simple hypergraphs.

As $\setS$ is self-simplified, we only need prove that $\setS$ is a simplification of $\{\hypergraphH+\hypergraphG\}$.
Let $\hypergraphG=(\setVertices_{\hypergraphG}, \mu_{\hypergraphG})$, $\hypergraphH=(\setVertices_{\hypergraphH}, \mu_{\hypergraphH})$, and $m\leq
\setSizeK$.
Let $\vec{g}\in \sums{\Z}{{\setof{\weight{setX}(\hypergraphH + \hypergraphG)}{  \setX\in
\kset{{m}}{(\setVertices_{\hypergraphH}\cup \setVertices_{\hypergraphG})}}}}$.
We have to prove that $\setS$ contains an $(m,\vec{g})-\simple$$(m,\vec{g})$-20 graph.
Suppose that $\vec{g}=c_1\vec{a_1}+c_2\vec{a_2}\ldots +c_l\vec{a_l}$ where
$\vec{a_i}\in {\setof{\weight{setX}(\hypergraphH + \hypergraphG)}{  \setX\in
\kset{{m}}{(\setVertices_{\hypergraphH}\cup \setVertices_{\hypergraphG})}}}
$ and $c_i\in \Z$.
By definition,747 if in $\setS$ there are $(i,\vec{a})$- hypergraphs and $(i,\vec{b})$-
hypergraphs then in $\setS$ there is an
$(i,\vec{a}+\vec{b})$- hypergraph too.
Thus, it is sufficient to prove that in $\setS$ there are
$(m,\vec{a_i})$-simple hypergraphs for $\vec{a_i}\in {\setof{\weight{setX}(\hypergraphH + \hypergraphG)}{  \setX\in
\kset{{m}}{(\setVertices_{\hypergraphH}\cup \setVertices_{\hypergraphG})}}}$.
WhichThis750 is also trivial as
$\weight{setX}({\hypergraphH}+\hypergraphG)=\weight{setX}({\hypergraphH}) + \weight{setX}(\hypergraphG)$
and there are
$(\size{\setX},\weight{setX}({\hypergraphH}))$$-$-750,751simple and $(\size{\setX},\weight{setX}(\hypergraphG))$$-$-750,751simple
hypergraphs in $\setS$749,750. The first one is in $\setS$ because $\setS$ is a family simple for
$\{\hypergraphH\}$ and the second is in $\setS$ because $\setS$ is self-simplified.

§ EXPRESSING A HYPERGRAPH WITH SIMPLE HYPERGRAPHS

Our goal in this section is to prove Theorem <ref> which is a slightly stronger version of the the following claim.

If $\setS$ is a simple family for a ${\setSizeK}$-hypergraph ${\hypergraphH}$ then ${\hypergraphH}\in \sums{\Z}{\eqs{\setS}}$.

We need a stronger version to use in the proof of existence of   hypergraphs.
The stronger version requires the notion of a support of a sum..753-757

For a hypergraph ${\hypergraphH}=({\setVertices},\mu)$ its support is
${\setVertices}$. We denote it $\support{{\hypergraphH}}$.
Let ${\hypergraphH}\in \sums{\Z}{\eqs{\setHypergraphsH}}$. We say that
${\setVertices\changed{}{'}{759}}$ supports $\hypergraphH$ for the family
if there is a solution ofto760 the following equation

\[
{\hypergraphH}=\sum_{i>0} a_i {\hypergraphH}_i \text{ where } a_i\in \Z, {\hypergraphH}_i\in \eqs\setHypergraphsH, \text{ and }
\support{{\hypergraphH}_i}\subseteq
{\setVertices\changed{}{'}{759}} \text{ for all } i.
\]

For the second part of the definition, one should think that $\setVertices'$ may include all supports of the elements of the sum. This naming is
motivated by the literature where support is used for objects but also for sets of objects, expressions build from objects e.t.c. For the convenience of
the reader in the following text whenever we speak about support of the hypergraph we use $\support{}$ symbol and all occurrences of word support in the text
are used as ” …supports …for a family …”.759

Let $\hypergraphH=(\setVertices, \mu)$ be a ${\setSizeK}$-hypergraph. Further, let $\setS$ be a simple family for ${\hypergraphH}$. Then,765
\sums{\Z}{\eqs{\setS}}$.
Moreover, if $\size{{\setVertices}}>2k-1$ then ${\setVertices}$ supports ${\hypergraphH}$ for the family $\setS$.

ProofThe proof766 of this theorem requires a few definitions and lemmas stated below. We start with them
and then we prove the theorem while proofs of lemmas are postponed.

Let us recall (Definitiont <ref>) that, a ${\setSizeK}$-hypergraph ${\hypergraphH}=(\setVertices,\mu)$ is m-isolated
if for any subset $\setX \subseteq {\setVertices}$ such that $\size{\setX}\leq m$ it holds that

If ${\hypergraphH}$ is a ${\setSizeK}$-isolated ${\setSizeK}$-hypergraph, then ${\hypergraphH}$ is equivalent to the empty hypergraph i.e. it is a
union of isolated vertices770.

Let ${\hypergraphH}=(\setVertices,\mu)$ be a ${\setSizeK}$-hypergraph. We say that it is almostpre777 m-isolated if the following two
conditions are satisfied:

* ${\hypergraphH}$ is $(m-1)$-isolated,

* there is $\setX\subseteq {\setVertices}$ a set of vertices such that $\size{\setX}\leq 2m-1$ and
for any $\setY \in \kset{m}{{\setVertices}}$ such that $\setY\not\subseteq \setX$ holdsit holds that451 $\weight{setY}({\hypergraphH})=\vec{0}$.

If ${\hypergraphH}$ is a ${\setSizeK}$-hypergraph that is almostpre777 $m$-isolated then it is $m$-isolated.

Let ${\hypergraphH}=(\setVertices, \mu)$ be an $m$-isolated ${\setSizeK}$-hypergraph,778 and $\setS$ be a simple family for ${\hypergraphH}$.
Then there is a hypergraph $\hypergraphG\in \sums{\Z}{\eqs{\setS}}$, such that
${\hypergraphH}+\hypergraphG$ is almostpre777 $m+1$-$(m+1)$-779isolated. Moreover, if $\size{{\setVertices}}>2k-1$ then
${\setVertices}$ supports $\hypergraphG$ for the
family $\setS$.

Without loss of generality we mayWe781 assume that
$\size{{\setVertices}}>2k-1$, as otherwise we extend it$\hypergraphH$781 with a
few isolated vertices.

We constructSuppose we haveNULL a sequence of hypergraphs $\hypergraphG_i\in \sums{\Z}{\eqs{\setS}}$

such that for every $j\leq\setSizeK$ the hypergraph783
${\hypergraphH}-\sum_{i=0}^j \hypergraphG_i$ is $j$-isolated.
Also, for every $i\leq j$$i \leq\setSizeK$NULL the set
${\setVertices}$ supports $\hypergraphG_i$ for the family $\setS$.
We define ${\hypergraphG}$ as $\sum_{i=0}^{\setSizeK} \hypergraphG_i$. Observe that $\hypergraphH = \hypergraphG$ as $\hypergraphH-\sum_{i=0}^{\setSizeK}
\hypergraphG_i$
is a $\setSizeK$-isolated $\setSizeK$-hypergraph, so and every $\setSizeK$-isolated $\setSizeK$-hypergraphNULL is empty due tobecause
of200 Remark <ref>. Moreover, $\setVertices$ supports $\hypergraphG$ for the
family $\setS$ as for every $i\leq\setSizeK$ the set $\setVertices$ supports $\hypergraphG_i$ for the family $\setS$.

which satisfies following properties.

* For every $j\leq\setSizeK$ the hypergraph ${\hypergraphH}-\sum_{i=0}^j \hypergraphG_i$ is $j$-isolated.

* For every $i\leq j$$i \leq\setSizeK$NULL the set ${\setVertices}$ supports $\hypergraphG_i$ for the family $\setS$.

We define ${\hypergraphG}$ as $\sum_{i=0}^{\setSizeK} \hypergraphG_i$.
Now,NULL observe that

* $\hypergraphG\in \sums{\Z}{\eqs{\setS}}$ as each $\hypergraphG_i$ is in $\sums{\Z}{\eqs{\setS}}$.

* $\support{\hypergraphG}\subseteq \setVertices$ as $\support{\hypergraphG_i}\subseteq \setVertices$ for each $i\leq \setSizeK$.

* $\setVertices$ supports $\hypergraphG$ for the family $\setS$ as $\setVertices$ supports $\hypergraphG_i$ for the family $\setS$ for each $i\leq
\setSizeK$.

* $\hypergraphH = \hypergraphG$ up to equivalence. Because of the first property we know that $\hypergraphH - \hypergraphG$ is a $\setSizeK$-isolated
$\setSizeK$-hypergraph, so
and every $\setSizeK$-isolated
$\setSizeK$-hypergraphNULL is the empty hypergraph, due tobecause of200 Remark <ref>.

Thus, if we have the sequence $\hypergraphG_i$ then we are done. Now, we show how the sequence $\hypergraphG_i$ may be constructed.
The construction is via induction on $\changed{j}{i}{790}$.
As $\setS$ is a simple family for ${\hypergraphH}$ then there is
$\hypergraphG_0 \in{\eqs{\setS}}$ and $\support{\changed{\hypergraphG}{\hypergraphG_0}{NULL}}\subset {\setVertices}$ such that ${\hypergraphH}-\hypergraphG_0$
This creates the induction base.

For the inductive step we reason as follows. First we observe that due tobecause of200 Lemma <ref> the family $\setS$ is
simple for
Thus, we may use Lemma <ref> for athe795 hypergraph
${\hypergraphH}-\sum_{j=0}^i \hypergraphG_j$ and the family $\setS$.
As a consequence we get $\hypergraphG_{i+1}\in \sums{\Z}{\eqs{\setS}}$ such that
$({\hypergraphH}-\sum_{j=0}^i \hypergraphG_j)-\hypergraphG_{i+1}$ is almostpre777 $i+1$-$(i+1)$-779isolated.
Moreover, $\setVertices$ supports $\hypergraphG_{i+1}$ for the family $\setS$.
Further, Lemma <ref> implies
that $({\hypergraphH}-\sum_{j=0}^i \hypergraphG_j)-\hypergraphG_{i+1}$ is $i+1$-$(i+1)$-779isolated.

Note that $\setVertices$ supports $\hypergraphG_{i+1}$ for the family $\setS$ thus $\setVertices$ supports $({\hypergraphH}-\sum_{j=0}^{i+1} \hypergraphG_j)$
for the family $\setS$, too.
This ends the inductive step.

§  PROOF OF LEMMA <REF>.

Before we prove Lemma <ref> we prove a simple
lemma about the $\weight{setX}$ functions. The main tool in the proof of Lemma <ref>
are reduction matrices defined in Section <ref>.804

Suppose ${\hypergraphH}=(\setVertices, \mu)$ is a ${\setSizeK}$-hypergraph, $\setX \in \kset{m}{{\setVertices}}$,806 and $m\leq l \leq\setSizeK$.
Let $\familyF = \setof{\setY \in \kset{l}{{\setVertices}}}{ \setX \subseteq \setY}$, be athe807 family of $l-$$l$-807element
supersets of $\setX$.

\[
\sum\limits_{\setY \in \familyF}\weight{setY}({\hypergraphH}) = {k-m \choose l-m} \weight{setX}({\hypergraphH}).
\]

Let us recall definition of $\weight{setX}(\hypergraphH)$. It is the sum of all edges $\edge$
in $\hypergraphH$ such that $\setX\subseteq \edge$.NULL
Let $\edge$ be a hyperedge in ${\hypergraphH}$ such that $\setX \subseteq \edge$.
It suffices to prove that $\mu(\edge)$
appears the same number of times on the813 both sides of the equation.

\[
\sum\limits_{\setY \in \familyF} \left( \sum_{\edge\in \kset{\setSizeK}{{\setVertices}}, \setY\subseteq \edge} \mu(\edge) \right)=
{k-m \choose l-m} \sum_{\edge\in \kset{\setSizeK}{{\setVertices}}, \setX\subseteq \edge} \mu(\edge).
\]
On the right-hand44 side $\edge$ is added ${k-m \choose l-m}$ times, as $\mu(e)$ appears once in the expression
On the left-hand44 side the number of times when $\edge$$\mu(\edge)$NULL is added is equal to the number of
$l$-element supersets of $\setX$ that are included in $\edge$. This is because $\mu(e)$ appears once in the expression
$\weight{setY}({\hypergraphH})$ if $\setY\subseteq e$.NULL But this is equal to
${{\size{\edge}-\size{\setX}} \choose {l-\size{\setX}}}={k-m \choose l-m}$, as required.

The main tool in the proof of Lemma <ref>
areis804 reduction matrices defined in Section <ref>.804

Let $\setX$ be a set of vertices as in Definition <ref>.
We only823 need to prove that for any $\setX'\subseteq \setX$ such that $\size{\setX'}=m$ holdsit holds that451

Let $\setY_1, \setY_2 \ldots \setY_n$ be all the825 $(m-1)$-subsets of $\setX$ and let $\setX'_1, \setX'_2 \ldots \setX'_{n'}$ be all
the825 $m$-subsets of $\setX$.

Due toBecause of200 Lemma <ref>,827
we know that,827 for any $\setY_i$,827 the equation

\[
\sum\limits_{\setX'_j \supset \setY_i} \weight{setX'_j}({\hypergraphH}) =\changed{((2m-1)-(m-1))}{\binom{k-m}{m - (m-1)}}{829}\cdot
\weight{setY_j}({\hypergraphH})\changed{\text{ holds.}}{}{828}
\]

holds. 828But ${\hypergraphH}$ is $m-1$ isolated so $\weight{setY_j}({\hypergraphH})=\vec{0}$.

This system of equation may be rewritten in matrix form

\[
Cu = \vec{0} \text{ where }
\]

$C\eqdef \reductionMatrix{2m-1}{m}{m-1}$ ($\reductionMatrix{\bullet}{\bullet}{\bullet}$ are
defined in Definition <ref>).
$C$ is the matrix with $\binom{\size{\setX}}{m}=\binom{2m-1}{m}$ columns indexed with $m$-elements$m$-element54
subsets of the set $\setX$, $\binom{{\size{\setX}}}{m-1}=\binom{2m-1}{m-1}$
rows indexed with $(m-1)$-elements$(m-1)$-element54 subsets of the set $\setX$, such that each
individual entry represents inclusion between the index of the row and the index of the column. So up to permutation of rows and columns $C$
is the $\reductionMatrix{2m-1}{m}{m-1}$ matrix ($\reductionMatrix{\bullet}{\bullet}{\bullet}$ areis840
defined in Definition <ref>).

But according to Lemma <ref> the rank of the matrix $C$ is maximal,
which implies $u = \vec{0}$ is the only solution of the system of equations. Thus Thus, 177$\weight{setX'_j}({\hypergraphH}) = \vec{0}$
for any $j\leq n'$ and consequently ${\hypergraphH}$ is $m$-isolated.

§ PROOF OF LEMMA <REF>.

The proof of Lemma <ref> requires some preparation.

Suppose $\setX \subset {\setVertices}, \size{\setX} <\setSizeK$.
We define $\cut{{\hypergraphH}}{\setX} \eqdef ({\setVertices} \setminus \setX, {\cut{\mu}{\setX}})$, where
${\cut{\mu}{\setX}}(\edge)$ is a function from $\kset{k-\size{\setX}}{({\setVertices}-\setX)}$
to $\ktuple{\dimension}{\Z}$ and is defined as follows

\[
{\cut{\mu}{\setX}}(\edge)\eqdef \mu(\edge\cup{\setX})\text{ where }
\edge\in \kset{k-\size{\setX}}{({\setVertices}-\setX)}.
\]

The above operation is called $\setX$-cut of ${\hypergraphH}$.
The reverse operation called enrich ${\hypergraphH}$ with $\setX$ is denoted by $\revcut{{\hypergraphH}}{\setX}$
and its effect is a minimal in the sense of inclusion[Inclusion of the sets of hyperedges.]
$(k+\size{\setX})$-hypergraph ${\hypergraphG}$ such that $\cut{{\hypergraphG}}{\setX}={\hypergraphH}$.

Let $\hypergraphF=(\setVerticesW,\mu')$ is a $\setSizeK$-hypergraph.
Suppose $\setX \subset {\setVerticesW}, \size{\setX} < \setSizeK$.
We define $\cut{{\hypergraphF}}{\setX} \eqdef ({\setVerticesW} \setminus \setX, {\cut{\mu'}{\setX}})$, where
${\cut{\mu'}{\setX}}(\edge)$ is a function from $\kset{\setSizeK-\size{\setX}}{({\setVerticesW}-\setX)}$
to $\ktuple{\dimension}{\Z}$ and is defined as follows

\[
{\cut{\mu'}{\setX}}(\edge)\eqdef \mu'(\edge\cup{\setX})\text{ where }
\edge\in \kset{\setSizeK-\size{\setX}}{({\setVerticesW}-\setX)}.
\]

The above operation is called $\setX$ cut$\setX$-cut851 of ${\hypergraphF}$.

For $\setX\cap \setVerticesW=\emptyset$ we define the reverse operation called enrichenriching851
${\hypergraphF}$ with $\setX$. It is denoted by $\revcut{{\hypergraphF}}{\setX}$
and its effect is the minimal in the sense of inclusion[Inclusion of the sets of hyperedges.we say that a hypergraph includes a
hypergraph if the set of vertices of the
first hypergraph includes the set of vertices of the second one and every hyperedge of the second hypergraph is also a hyperedge of the first
$(\setSizeK+\size{\setX})$-hypergraph ${\hypergraphF'}$ such that $\cut{{\hypergraphF'}}{\setX}={\hypergraphF}$.

If $\setX = \{\da\}$ is a singleton, then we simplify the notation
$\cut{{\hypergraphG}}{\da} \eqdef \cut{{\hypergraphG}}{\{\da\}}$ and $\revcut{{\hypergraphG}}{\da} \eqdef \revcut{{\hypergraphG}}{\{\da\}}$.

If $\setX = \{\da\}$ is a singleton, then we simplify the notation
$\cut{{\hypergraphF}}{\da} \eqdef \cut{{\hypergraphF}}{\{\da\}}$ and $\revcut{{\hypergraphF}}{\da} \eqdef \revcut{{\hypergraphF}}{\{\da\}}$.

removed figure857

line cap=butt,line join=bevel]
[,thick] (-,-,0) – (,-,0) –  (-,,0) – cycle;
[font=] at (-,+0.3,0) $\da$;
(aux1) at (0,0,2/3*)̋ $\bullet$;
(aux2) at (0,-2/3*,2/3*)̋ $\bullet$;
(aux4) at (-2/3*,0,2/3*)̋ $\bullet$;

(aux3) at (-2/3*,2/5*,0);
[,thick,fill=,fill opacity=0.3] (-,,0) – (0,0,2*)̋ – (,-,0) – cycle;
[,thick,fill=,fill opacity=0.7] (-,-,0) – (,-,0) –  (0,0,2*)̋ – cycle – cycle;
[,thick,fill=,fill opacity=0.4] (-,-,0) – (0,0,2*)̋ – (-,,0) – cycle;
(aux1) – ++ (2,0.2) node[right,font=] a;
(aux4) – ++ (-1.5,0.3) node[left,font=] b;
(aux3) – ++ (1,1) node[above right,font=] c;
(aux2) – ++ (1,-1) node[below right,font=] d;

(A) at (5+-,-,0) ;
(B) at (5+,-,0) ;
(C) at (5,0,2*)̋ ;

[] (A) – (C) coordinate[midway](A1) ;
[ left = 0.1 cm and 0 cm of A1,font=] b;
[] (B) – (C)coordinate[midway](B1);
[ above = 0 cm and 0 cm of B1,font=] a;
[black] (B) – (A) coordinate[midway](C1);
[below= 0.1 cm and 0 cm of C1,font=] c;

On the left-hand44 side there is a $3$-hypergraph ${\hypergraphF}$ and
on the right hand44 side
there is a $2$-hypergraph
$\cut{{\hypergraphF}}{\da}$. We use letters $a,b,c,d$ to name corresponding hyperedges.863 The orange bottom hyperedge $d$863
disappears as it does not contain $\da$.
$\revcut{\cut{{\hypergraphF}}{\da}}{\da}$ would look like ${\hypergraphF}$ but without the orange hyperedge, as the enrichenriching851 operation
takes the minimal hypergraph among all such that cutting $\da$ returns $\cut{{\hypergraphF}}{\da}$.

Let ${\changed{\hypergraphH}{\hypergraphF}{847}}=(\changed{\setVertices}{\setVerticesW}{847}, \changed{\mu}{\mu'}{847})$ be a869
${\setSizeK}$-hypergraph,869 and $\setX\in \kset{m}{{\changed{\setVertices}{\setVerticesW}{847}}}$ for $m<\setSizeK$.
Then for any nonempty set 451$\setY\subseteq {\changed{\setVertices}{\setVerticesW}{847}}$ such that $\setY\cap \setX=\emptyset$
holdsit holds that451
In particular, if $\changed{\hypergraphH}{\hypergraphF}{847}$ is $l$-isolated and $m<l$ then $\cut{{\changed{\hypergraphH}{\hypergraphF}{847}}}{\setX}$ is

Note that $\edge$ and $\edge'$ are parameters of the sums below.In the equation below, $e$ and $e'$ are indexes, while $\setVerticesW, \setY$ and
$\setX$ are fixed.874, 880

\begin{align*}
\weight{YcupX}({\changed{\hypergraphH}{\hypergraphF}{847}})=\\
\sum_{\edge \in \kset{\setSizeK}{{\changed{\setVertices}{\setVerticesW}{847}}}, \setY\cup
\setX\subseteq \edge} \changed{\mu}{\mu'}{847}(\edge)=\\
\sum_{\edge\in \kset{\setSizeK}{{\changed{\setVertices}{\setVerticesW}{847}}}, \setY\cup \setX\subseteq \edge}
\weight{e-X}(\cut{{\changed{\hypergraphH}{\hypergraphF}{847}}}{\setX})=\\
\sum_{\changed{\edge\setminus \setX) \kset{\setSizeK-\size{\setX}}{\setVerticesW}}
{(\edge\setminus \setX) \kset{\setSizeK-\size{\setX}}{\setVerticesW\setminus \setX}}{875-883}
, \setY\subseteq (\edge\setminus \setX)}
\weight{e-X}(\cut{{\changed{\hypergraphH}{\hypergraphF}{847}}}{\setX})= \\
\changed{ \text{By $\edge'$ we denote hyperedges of the hypergraph $\cut{{\changed{\hypergraphH}{\hypergraphF}{847}}}{\setX}$.}}{}{875-883}\\
\sum_{\changed{}{\edge'\in \kset{\setSizeK-\size{\setX}}{\setVerticesW\setminus \setX},}{875-883} \setY\subseteq \edge'}
\weight{edge'}(\cut{{\changed{\hypergraphH}{\hypergraphF}{847}}}{\setX})=\\
\weight{setY}(\cut{{\changed{\hypergraphH}{\hypergraphF}{847}}}{\setX})
\end{align*}

Without loss of generality, we assume that $\size{{\setVertices}}>2\setSizeK-1$. Indeed, if
$\size{{\setVertices}}\leq 2\setSizeK-1$ then we extend ${\hypergraphH}$ with a few isolated vertices.

In the proof, instead of constructing $\hypergraphG$ directly, we build a finite sequence of hypergraphs
${\hypergraphH}_i$${\hypergraphH}_0\ldots{\hypergraphH}_{last}$888, such that:

* ${\hypergraphH}_0={\hypergraphH}$,

* ${\hypergraphH}_{last}$ is
almostpre777 ${\newl}+1$-$({\newl}+1)$-779isolated,

* there is a well-quasi order $>$ on hypergraphs such that $\hypergraphH_i >\hypergraphH_{i+1}$ for each $0\leq i < last$, and

* each
where $\simpleGraph{newl+1}{}_i$ is a $({\newl}+1, {\placeHolder})$- hypergraph such that $\simpleGraph{newl+1}{}_i\in \eqs{\setS}$ and

Intuitively, we build a sequence of improvements $\simpleGraph{newl+1}{}_i$885-890 and consequently
$\hypergraphG=-\sum_{i}\simpleGraph{newl+1}{}_i.$ we will set $\hypergraphG$, the hypergraph that we need to build, to be

First, we define athe885-890 well-founded quasi-order on hypergraphs,
nextthen892 we present a single improvement i.e. how to obtain ${\hypergraphH}_{i+1}$ from ${\hypergraphH}_i$,
finally we show that ${\hypergraphH}_{i+1}<{\hypergraphH}_i$ in the defined quasi-order and
that if the hypergraph can notcannot894 be improved anymore then it is
almostpre777 ${\newl}+1$-$({\newl}+1)$-779isolated.

Order. First,896 we impose aan arbitrary896 well foundedwell-founded896 linear order on the set of all vertices.
A set of vertices $\setX_1$
is smaller than a set $\setX_2$For two sets of vertices $\setX_1$ and $\setX_2$, we write $\setX_1<\setX_2$897 if there is a bijection $f\colon
\setX_1\rightarrow
\setX_2$ such that $\da \leq f(\da)$ for every $\da\in \setX_1$.
Finally, a hypergraph ${\hypergraphH}'=({\setVertices}',\mu') \leq_{{\newl}+1}{\hypergraphH}$for two hypergraphs $\hypergraphH=(\setVertices,\mu)$
and $\hypergraphH'=(\setVertices',\mu')$ we write $\hypergraphH'\leq_{{\newl}+1} \hypergraphH$898 if for every
$\setX'\in\kset{{\newl}+1}{{\setVertices}'}$ such that $\weight{setX'}({\hypergraphH}')\neq \vec{0}$ there is a set $\setX\in \kset{{\newl}+1}{{\setVertices}}$
such that
$\weight{setX}({\hypergraphH})\neq \vec{0}$ and $\setX$ is bigger than $\setX'$$\setX'\leq \setX$899.

The strict inequality $<_{{\newl}+1}$ holds if ${\hypergraphH}'\leq_{{\newl}+1} {\hypergraphH}$ but ${\hypergraphH}'\not\geq_{{\newl}+1} {\hypergraphH}$.

From now on until the end of this proof,901 whenever we enumerate vertices of some set $\da_1,\da_2\ldots \da_n$$\{\da_1,\da_2\ldots
\da_n\}$,902
we assume that $\da_i<\da_j$ for $i<j$.

Improvement. We define the improvement for ${\hypergraphH}_i$.
Let $\familyL\subset \kset{{\newl}+1}{\support{{\hypergraphH}_i}}$ $\setL\in \familyL \implies \weight{setL}({\hypergraphH}_i)\neq \vec{0}$be the
family of all sets such that for every set
$\setL\in \familyL$ it holds that $\weight{setL}({\hypergraphH}_i)\neq \vec{0}$903. Note that, if ${\newl}+1=\setSizeK$ then $\familyL$ is the set of
hyperedges of

Suppose $\setL\in \familyL$ is maximal in $\familyL$ and there is a set $\setL'\in\kset{{\newl}+1}{{\setVertices}}$ disjoint from $\setL$ such that
Let $\setL=\{\da_1, \da_2 \ldots \da_{{\newl}+1}\}$. Let $\simpleGraph{newl+1}{}_i\in\eqs{\setS}$ be an
$({\newl}+1,\weight{setL}({\hypergraphH}_i))$- hypergraph supported by ${\setVertices}$such that
{\setVertices}$, and759, 907
such that (according to Definition <ref>)(using the notation of Definition <ref>)907
$\setA=\setL$ and $\setB=\setL'=\{f^{-1}(\da_1),f^{-1}(\da_2)\ldots $ $f^{-1}(\da_{{\newl}+1})\}$, where $f$ witnesses $\setL'<\setL$. ItThe
hypergraph $\simpleGraph{newl+1}{}_i$908 exists due
tobecause of200
Lemma <ref>.

Let ${\hypergraphH}_{i+1}\eqdef {\hypergraphH}_i-\simpleGraph{newl+1}{}_i$.
We claim ${\hypergraphH}_{i+1}<_{{\newl}+1} {\hypergraphH}_i$.

Indeed, $\weight{setL}({\hypergraphH}_{i+1})=\vec{0}$ and $\setL$ wasis911 maximal in $\familyL$ so it is911 sufficient to
prove that for any
$\edgeK\in\kset{{\newl}+1}{\support{\simpleGraph{newl+1}{}_i}}$ such that $\edgeK\neq \setL$ and $\weight{edgeK}(\simpleGraph{newl+1}{}_i)\neq \vec{0}$
holdsit holds that451
$\edgeK< \setL$.
But $\weight{edgeK}(\simpleGraph{newl+1}{}_i)\neq \vec{0}$ if,325 and only if,325 $\edgeK$ is a subset
of $\setL'\cup \setL$ that contains exactly one element from each pair of vertices
$(\da_i,f^{-1}(\da_i))$ (Definition <ref>). As $\da_i>f^{-1}(\da_i)$ for every $i$ then trivially $\setL=\{\da_1,\da_2\ldots
\da_{{\newl}+1}\}>\edgeK$, as required.

First, we show inequality, next we show that it is strict. For the inequality we take any subset $\edgeK\in\kset{{\newl}+1}{{\setVertices}}$ such that
$\weight{edgeK}(\hypergraphH_{i+1})\neq \vec{0}$ and we find a subset $\edgeK'\in\kset{{\newl}+1}{{\setVertices}}$ such that
$\weight{edgeK}(\hypergraphH_{i  })\neq \vec{0}$ and         $\edgeK\leq \edgeK'$. We have to consider two cases:

* $\weight{edgeK}(\hypergraphH_{i+1})\neq \vec{0}$ because of $\weight{edgeK}(\hypergraphH_{i})\neq \vec{0}$ and

* $\weight{edgeK}(\hypergraphH_{i+1})\neq \vec{0}$ because of $\weight{edgeK}(\simpleGraph{newl+1}{}_i)\neq \vec{0}.$

In the first case $\edgeK'=\edgeK$. In the second case $\edgeK'=\setL$. We observe that $\edgeK\leq \setL$ as $\edgeK=\{x_1,x_2\ldots x_{\newl+1}\}$
where $x_i\in \{\da_i, f^{-1}(\da_i)\}$ and $\setL=\{\da_1,\da_2\ldots \da_{\newl+1}\}$ which is the greatest set (with respect to the order $<$) among such

Now,NULL to prove strictness of the inequality we observe that $\weight{setL}(\hypergraphH_{i+1})=\vec{0}$
and that there is no set $\edgeK$ such that $\setL\leq
\edgeK$ and $\weight{edgeK}{(\hypergraphH_{i+1})}\neq 0$, so $\hypergraphH_{i}\not\leq\hypergraphH_{i+1}.$
The formal proof requires the same case analysis as the proof of the non-strictnonstrict107 inequality. In the first case, we use maximality of
$\setL$ in the family
$\familyL$. In the second case, we use the fact that $\setL$ is is the greatest set (with respect to the order $<$) among possible sets.

Reduced form.
We call a hypergraph reduced if one can notcannot357 improve it any further.
If we consequently improve a given hypergraph then eventually we reach ${\hypergraphH}_{last}$ which is reduced.
Indeed, every improvement goes down in the quasi-order on hypergraphs and the quasi-order is trivially well-founded.
What remains to prove is the following claim.

A reduced hypergraph is almostpre777 ${\newl}+1$-$({\newl}+1)$-779isolated.

Proof of the claim.
First observe that ${\hypergraphH}_{last}$ is ${\newl}$-isolated as ${\hypergraphH}$ and each $\simpleGraph{newl+1}{}_i$ are ${\newl}$-isolated (by
Definition <ref>
every $({\newl}+1,{\placeHolder})$-
is ${\newl}$-isolated).

Observe  that929 $\support{{\hypergraphH}_{last}}\subseteq {\setVertices}$. Suppose ${\setVertices} =\{\da_1,\da_2\ldots
\da_{\size{{\setVertices}}}\}$.
Let $\familyL \subseteq \kset{{\newl}+1}{{\setVertices}}$ be atheNULL family of sets of vertices such that for any $\setL\in \familyL$ we have
$\weight{setL}({\hypergraphH}_{\changed{i}{last}{NULL}})\neq \vec{0}$ and $\setL$
contains a vertex
with index greater than $2{\newl}+1$. Our goal is to prove that $\familyL$ is empty; this implies the claim.

We prove it viaby933 contradiction. Suppose $\familyL\neq \emptyset.$
For aany922 set $\setL\in \familyL$, $\setL=\{\da_{i_1},\da_{i_2}\ldots \da_{i_{{\newl}+1}}\}$ we introduce $\setY_{\setL}\subseteq \setL$
the maximal (in the sense of inclusion) set of vertices
such that $i_j\geq 2j,$ $i_{j+1}\geq 2(j+1),$ $\ldots i_{{\newl}+1}\geq 2({\newl}+1)$. By definition of the family $\familyF$,935 for every
$\setL\in \familyF$ the set $\setY_{\setL}\neq
\emptyset.$$\setY_{\setL}$ is nonempty.936

Let $\setL\in \familyL$ be a set such that $\setY_{\setL}$ is maximal
in the terms of size, i.e. i.e.22 for every $\edgeK\in \familyL$ holdsit holds that451 $\size{\setY_{\setL}}\geq
\size{\setY_{\edgeK}}$.
We show the contradiction by proving $\weight{setL}({\hypergraphH}_{last})=\vec{0}$.

Observe that $\setL\neq \setY_{\setL}$ as in this case ${\hypergraphH}_{last}$ would not be reduced.

Take,Let940 ${\hypergraphG}'\eqdef
\changed{\cut{{\hypergraphH}_{last}}{{\setY_{\setL}}}}{\cut{{(\hypergraphH}_{last})}{{\setY_{\setL}}}}{940}$ (recall Definition <ref>). As
\setY_{\setL}$
we know that $\weight{setL}({\hypergraphH}_{last})=\weight{L-Y}({\hypergraphG}')$. So, if we prove that ${\hypergraphG}'$ is
$(\size{\setL}-\size{\setY_{\setL}})$-isolated then
$\vec{0}=\weight{L-Y}({\hypergraphG})=\weight{setL}({\hypergraphH}_{last})$ and we have the contradiction with the assumption
$\weight{setL}({\hypergraphH}_{last})\neq \vec{0}$.

So what remains, is to prove the following claim.

${\hypergraphG}'$ is  $(\size{\setL}-\size{\setY_{\setL}})$-isolated.

Track the proof on the Figure <ref>.946

Let ${\newl}'=(\size{\setL}-\size{\setY_{\setL}})$.
It suffices to prove that ${\hypergraphG}'$ is almostpre777 ${\newl}'$-isolated.
Indeed, thenThenNULL due tobecause of200 Lemma <ref>
the hypergraphNULL ${\hypergraphG}'$ is ${\newl}'$-isolated.

Note that ${\hypergraphG}'$ is ${\newl}'-1$-isolated which is inherited from ${\hypergraphH}_{last}$,
due tobecause of200 Lemma <ref>. So it remains to analyse weights
of ${\newl}'$-subsets of ${\setVertices}$.
We have to prove that everyOur goal is to show that, for every950 $\edgeK\in\kset{{\newl}'}{{\setVertices}}$ if
$\weight{edgeK}({\hypergraphG'})\neq \vec{0}$ then it is a subset of $\{\da_1\ldots
\da_{2{\newl}'-1}\}$.

Let us take $\edgeK=\{\da_{i'_1},\da_{i'_2}\ldots \da_{i'_{{\newl}'}}\}$, such that $ {i'_{{\newl}'}}\geq 2{\newl}'$.
We prove that $\weight{edgeK}({\hypergraphG'})=\vec{0}$.
Observe, that954 $\setY_{\setL}\subseteq \setY_{\setL} \cup \{\da_{i'_{{\newl}'}}\}\subseteq
\setY_{(\edgeK\cup \setY_{\setL})}$.
Indeed, $\setY_{\setL}$ guarantees that in $\edgeK\cup \setY_{\setL}$ there is at least one element not smaller than $2({\newl}+1)$, at least
two elements not smaller than $2{\newl}$…at least $\size{\setY_{\setL}}$
elements not smaller than $2({\newl}'+1)$. Moreover, because of ${i'_{{\newl}'}}\geq 2{\newl}'$, there are at least $\size{\setY_{\setL}}+1$ elements
not smaller than $2{\newl}'$.

Let us consider the set $\setLdwa=\edgeK\cup \setY_{\setL}$. We claim that $\size{\setY_{\setL}}< \size{\setY_{\setLdwa}}$.
To see this we observe that in the set $\setLdwa$, because of the definition of the set $\setY_{\setL}$,
there is at least one element not smaller than $\da_{2({\newl}+1)}$, at least
two elements not smaller than $\da_{2{\newl}}$…at least $\size{\setY_{\setL}}$
elements not smaller than $\da_{2({\newl}'+1)}$. Moreover, because of956 ${i'_{{\newl}'}}\geq 2{\newl}'$, there are at least
$\size{\setY_{\setL}}+1$ elements
not smaller than $\da_{2{\newl}'}$. This implies that $({\newl}+1)- ({\newl}'-1)\leq \size{\setY_{\setLdwa}}$ where $\size{\setY_{\setL}}=({\newl}+1)-

Due toBecause of200 maximality of $\setL$$\setY_{\setL}$NULL,958 we conclude that
$\weight{setLdwa}({\hypergraphH}_{last})=\vec{0}$, thus
Therefore every $\edgeK$ an ${\newl}'$-set
of vertices in ${\hypergraphG'}$, for which

Therefore for every
${\newl}'$-set of vertices $\edgeK$
in $\kset{{\newl}'}{\setVertices}$, such that959 $\weight{edgeK}\changed{}{(\hypergraphG')}{959}\neq \vec{0}$, it959 is a subset of $\{\da_1,
\da_2\ldots \da_{2{\newl}'-1}\}$.
This ends the proof that ${\hypergraphG}'$ is almostpre777 ${\newl}'$-isolated.

Finally, as it was written earlier, from Lemma <ref>
we derive that ${\hypergraphG}'$ is ${\newl}'$-isolated.

[place/.style=circle,draw=!50,fill=!20,thick,inner sep=0pt,minimum size=1mm]
[] (ZERO) at (0,1) ;
[place, color=black] (A0) at (0,0) ;
[place, color=black] (A1) at (1*,0) ;
[place, color=black] (A2) at (2*,0) ;
[place, color=black] (A3) at (3*,0) ;
[place, color=black] (A4) at (4*,0) ;
[place, color=black] (A5) at (5*,0) ;
[place, color=black] (A6) at (6*,0) ;
[place, color=black] (A7) at (7*,0) ;
[place, color=black] (A8) at (8*,0) ;
[place, color=black] (A9) at (9*,0) ;
[place, color=black] (A10) at (10*,0) ;
[place, color=black] (A11) at (11*,0) ;
[place, color=black] (A12) at (12*,0) ;
[place, color=black] (A13) at (13*,0) ;
[place, color=black] (A14) at (14*,0) ;
[place, color=black] (A15) at (15*,0) ;
[] (B0) at (0*,0.5) $v_{1}$;
[] (B1) at (1*,0.5) $v_{2}$;
[] (B2) at (2*,0.5) $v_{3}$;
[] (B3) at (3*,0.5) $v_{4}$;
[] (B4) at (4*,0.5) $v_{5}$;
[] (B5) at (5*,0.5) $v_{6}$;
[] (B6) at (6*,0.5) $v_{7}$;
[] (B7) at (7*,0.5) $v_{8}$;
[] (B8) at (8*,0.5) $v_{9}$;
[] (B9) at (9*,0.5) $v_{10}$;
[] (B10) at (10*,0.5) $v_{11}$;
[] (B11) at (11*,0.5) $v_{12}$;
[] (B12) at (12*,0.5) $v_{13}$;
[] (B13) at (13*,0.5) $v_{14}$;
[] (B14) at (14*,0.5) $v_{15}$;
[] (B15) at (15*,0.5) $v_{16}$;
[place, color=mycol2] (C0) at (0*,-1) ;
[place, color=mycol2] (C2) at (2*,-1) ;
[place, color=mycol2] (C3) at (3*,-1) ;
[place, color=mycol2] (C5) at (5*,-1) ;
[place, color=] (C9) at (9*,-1) ;
[place, color=] (C12) at (12*,-1) ;
[place, color=] (C14) at (14*,-1) ;
[place, color=] (D0) at (0*,-2) ;
[place, color=] (D1) at (1*,-2) ;
[place, color=] (D8) at (8*,-2) ;
[place, color=] (D15) at (15*,-2) ;
[, very thick, fill=mycol2, opacity=0.15] (-0.5*,-0.65) rectangle (17*,-1.35);

[, very thick, fill=, opacity=0.35] (7.5*,-0.75) rectangle (15*,-1.25);

[] (E1) at (16*,-1) $\setL$;

[] (E2) at (13*,-1) $\setY_{\setL}$;

[, very thick, fill=, opacity=0.15] (-0.5*,-1.65) rectangle (17*,-2.35);

[, very thick, , fill=, opacity=0.35] (6.5*,-1.75) rectangle (16*,-2.25);

[] (F1) at (16.5*,-2) $\setL'$;

[] (F2) at (13*,-2) $\setY_{\setL'}$;

§ THE CONSTRUCTION OF SIMPLE  HYPERGRAPHS.

The whole section is devoted to proving the following theorem:

Suppose ${\hypergraphG}$ is a ${\setSizeK}$-hypergraph.
Then there is $\setS'$ a simple family for $\{{\hypergraphG}\}$. Moreover $\setS'\subseteq \sums{\Z}{\eqs{{\hypergraphG}}}.$

We want to construct the family $\setS'$. To achieve this,975
Due tobecause of200 Remark <ref>,975 it is sufficient to propose an algorithm that for any
${\setSizeK}$-hypergraph ${\hypergraphG}$ produces $\setS$
a simplification of $\{{\hypergraphG}\}$ such that $\setS\subseteq \sums{\Z}{\eqs{{\hypergraphG}}}$. Existence of a such algorithmof such
an algorithm976 is
a consequence of the following lemmas.

Let ${\hypergraphG}=({\setVertices}',\mu')$ be a ${\setSizeK}$-hypergraph and
$\setX \in \kset{m}{{\setVertices}'}$ where $m\leq \setSizeK$. Let $\vec{a}=\weight{setX}(\hypergraphG)$.
there is a $(m,\vec{a})-\simple$$(m,\vec{a})$-979,980 ${\setSizeK}$-hypergraph
${\simpleGraph{m}{\vec{a}}}$ such that ${\simpleGraph{m}{\vec{a}}}\in \sums{\Z}{\eqs{{\hypergraphG}}}$.

Let ${\hypergraphG}$ be a ${\setSizeK}$-hypergraph.981 For any $0\leq m\leq \setSizeK$,980 if
$(m,\vec{a})-$simple$(m,\vec{a})$-979,980 and $(m,\vec{b})$-
hypergraphs are elements of $\sums{\Z}{\eqs{{\hypergraphG}}}$ then
$(m,\vec{a}+\vec{b})-$simple$(m,\vec{a}+\vec{b})$-979,980 hypergraph is also a member of $\sums{\Z}{\eqs{{\hypergraphG}}}$.

Let ${\hypergraphG}$ be a ${\setSizeK}$-hypergraph and $0\leq m\leq \setSizeK$. Suppose there are
$(m,\vec{a})$- and $(m,\vec{b})$-
hypergraphs that are elements of $\sums{\Z}{\eqs{{\hypergraphG}}}$. Then
$(m,\vec{a}+\vec{b})$- hypergraph is also a member of $\sums{\Z}{\eqs{{\hypergraphG}}}$.

Let ${\hypergraphG}=({\setVertices}',\mu')$ be a ${\setSizeK}$-hypergraph and
$\setX \in \kset{m}{{\setVertices}'}$ where $m\leq \setSizeK$. Let $\vec{a}=\weight{setX}(\hypergraphG)$.
there is a $(m,\vec{a})-\simple$$(m,\vec{a})$-979,980 ${\setSizeK}$-hypergraph
${\simpleGraph{m}{\vec{a}}}$ such that ${\simpleGraph{m}{\vec{a}}}\in \sums{\Z}{\eqs{{\hypergraphG}}}$.

Indeed, using this two lemmas we can produce all elements in the simplification.
Suppose, $m\leq \setSizeK$ and
$\vec{a}\in \sums{\Z}{{\setof{\weight{setX}(\hypergraphG)}{\setX\in \kset{m}{\setVertices'}}}}$.
We have to show that $(m,\vec{a})$- hypergraph is in $\sums{\Z}{\eqs{\hypergraphG}}$.
Suppose, $\vec{a}=c_1\vec{a_1}+c_2\vec{a_2}\ldots c_l\vec{a_l}$
where $\vec{a_i}\in$
$\setof{\weight{setX}(\hypergraphG)}{{\setX\in \kset{m}{\setVertices'}}}$ and $c_i\in \Z$.
Because of Lemma <ref> it suffices to prove that
$(m,\vec{a_i})$- hypergraphs are in $\sums{\Z}{\eqs{\hypergraphG}}$. But this is exactly
Lemma <ref>.NULL
So it remains to provide proofs of lemmas <ref> and <ref>.
The proof of Lemma <ref> is easy so we start from it and then we concentrate on the much more complicated proof of
Lemma <ref>.

We start fromwith964 an operator that is used in later proofs.

Suppose ${\hypergraphG}=({\setVertices}', \mu')$ is a ${\setSizeK}$-hypergraph and $\da \in {\setVertices}', \da'\notin
are two vertices.
Let $\sigma_{\da} \colon {\setVertices}' \cup \{\da'\} \rightarrow {\setVertices}' \cup \{\da'\}$ such that:

σ_(x) {
'     when $x = {\da}$

when $x = {\da}'$

x     otherwise

A swap of $\da$ and $\da'$ in ${\hypergraphG}$
is defined as
$\swap{\da}{\da'}{\hypergraphG} \eqdef {\hypergraphG} \circ \sigma_{\da}$.

Suppose ${\hypergraphG}$ is a ${\setSizeK}$-hypergraph.
Then there is $\setS'$ a simple family for $\{{\hypergraphG}\}$. Moreover $\setS'\subseteq \sums{\Z}{\eqs{{\hypergraphG}}}.$

Due toBecause of200 Remark <ref> it is sufficient to propose an algorithm that for any ${\setSizeK}$-hypergraph ${\hypergraphG}$
produces $\setS$
a simplification of $\{{\hypergraphG}\}$ such that $\setS\subseteq \sums{\Z}{\eqs{{\hypergraphG}}}$. Existence of a such algorithm is
a consequence of the following lemmas.

Let ${\hypergraphG}=({\setVertices}',\mu')$ be a ${\setSizeK}$-hypergraph and
$\setX \in \kset{m}{{\setVertices}'}$ where $m\leq \setSizeK$. Let $\vec{a}=\weight{setX}(\hypergraphG)$.
there is a $(m,\vec{a})-\simple$$(m,\vec{a})$-20 ${\setSizeK}$-hypergraph
${\simpleGraph{m}{\vec{a}}}$ such that ${\simpleGraph{m}{\vec{a}}}\in \sums{\Z}{\eqs{{\hypergraphG}}}$.

For any $0\leq m\leq \setSizeK$ if $(m,\vec{a})-$simple and $(m,\vec{b})$-
hypergraphs are elements of $\sums{\Z}{\eqs{{\hypergraphG}}}$ then
$(m,\vec{a}+\vec{b})-$simple hypergraph is also a member of $\sums{\Z}{\eqs{{\hypergraphG}}}$.

Indeed, using this two lemmas we can produce all elements in the simplification.
The proof of Lemma <ref> is easy so we start from it and then we concentrate on the much more complicated proof of
Lemma <ref>.

Let ${\simpleGraph{m}{\vec{a}}}\in \sums{\Z}{\eqs{{\hypergraphG}}}$ isbe985 & 986 the $(m,\vec{a})-$simple hypergraph and
$\simpleGraph{m}{\vec{b}}\in \sums{\Z}{\eqs{{\hypergraphG}}}$ isbe985 & 986 the $(m,\vec{b})-$simple hypergraph.
Thus weWe986 can write

\[
{\simpleGraph{m}{\vec{a}}}=\sum_i a_i {\hypergraphG}_i \text{ where } a_i \in \Z \text{ and } {\hypergraphG}_i\in \eqs{{\hypergraphG}}
\]

\[
\simpleGraph{m}{\vec{b}}=\sum_j b_{\vec{w}} {\hypergraphG}_j \text{ where } b_{\vec{w}} \in \Z \text{ and } {\hypergraphG}_j\in \eqs{{\hypergraphG}}
\]

We recall the definitionrecall the notation used in Definition <ref>992 of   hypergraphs; the vertices of
${\simpleGraph{m}{\vec{a}}}$ can be split into ${\setA}_{\simpleGraph{m}{\vec{a}}},
{\setB}_{\simpleGraph{m}{\vec{a}}}, {\setC}_{\simpleGraph{m}{\vec{a}}}$ and similarly
vertices of $\simpleGraph{m}{\vec{b}}$ are in ${\setA}_{\simpleGraph{m}{\vec{b}}}, {\setB}_{\simpleGraph{m}{\vec{b}}}, {\setC}_{\simpleGraph{m}{\vec{b}}}$.
We assume that sets ${\setA}_{{\placeHolder}}$ and ${\setB}_{{\placeHolder}}$ are ordered like in the definition of   hypergraphs.According
Definition <ref>, the elements of sets ${\setA}_{\simpleGraph{m}{\vec{a}}},
{\setB}_{\simpleGraph{m}{\vec{a}}}$ are paired, formally there is a bijection $f:{\setA}_{\simpleGraph{m}{\vec{a}}}\to{}
{\setB}_{\simpleGraph{m}{\vec{a}}}$, similarly elements of sets ${\setA}_{\simpleGraph{m}{\vec{b}}}$ and ${\setB}_{\simpleGraph{m}{\vec{b}}}$ are paired,
formally there is a bijection $f':{\setA}_{\simpleGraph{m}{\vec{b}}}\to{} {\setB}_{\simpleGraph{m}{\vec{b}}}$.993

Then there is a bijection $\pi$ between vertices that transfers $\setA_{\simpleGraph{m}{\vec{a}}}$ to ${\setA}_{\simpleGraph{m}{\vec{b}}}$,
$\setB_{\simpleGraph{m}{\vec{a}}}$ to ${\setB}_{\simpleGraph{m}{\vec{b}}}$, $C_{\simpleGraph{m}{\vec{a}}}$ to ${\setC}_{\simpleGraph{m}{\vec{b}}}$, and that
preserves the orders
on vertices in ${\setA}_{{\placeHolder}}$ and ${\setB}_{{\placeHolder}}$.it preserves the pairings i.e. $\pi(f(\da_i))=f'(\pi(\da_i))$ and
$\pi(f^{-1}(\db_i))=f'^{-1}(\pi(\db_i))$ for
every $\da_i\in \setA_{\simpleGraph{m}{\vec{a}}}$ and $\db_i\in \setB_{\simpleGraph{m}{\vec{a}}}$.993
Thus Thus, 177

\[
{{\simpleGraph{m}{\vec{a}}}} + {\simpleGraph{m}{\vec{b}}}\circ\pi = \sum_i a_i {\hypergraphG}_i + (\sum_j b_{\vec{w}} {\hypergraphG}_j)\circ \pi = \sum_i a_i
+ \sum_j b_{\vec{w}} ({\hypergraphG}_j)\circ \pi
\]

But this mean that ${{\simpleGraph{m}{\vec{a}}}}+{\simpleGraph{m}{\vec{a}}} \circ \pi\in \sums{\Z}{\eqs{{\hypergraphG}}}$

${{\simpleGraph{m}{\vec{a}}}}+{\simpleGraph{m}{\vec{b}}} \circ \pi\in \sums{\Z}{\eqs{{\hypergraphG}}}$1001. It is not hard to see
${{\simpleGraph{m}{\vec{a}}}}+{\simpleGraph{m}{\vec{a}}} \circ \pi$
${{\simpleGraph{m}{\vec{a}}}}+{\simpleGraph{m}{\vec{b}}} \circ \pi$
is an $(m,\vec{a}+\vec{b})$- hypergraph.

We may proceed to the proof of Lemma <ref>. We start fromwith964 an
operator that is used in the following proofs.

Suppose ${\hypergraphG}=({\setVertices}', \mu')$ is a ${\setSizeK}$-hypergraph and $\da \in {\setVertices}', \da'\notin
are two vertices.
Let $\sigma_{\da} \colon {\setVertices}' \cup \{\da'\} \rightarrow {\setVertices}' \cup \{\da'\}$ such that:

σ_(x) {
'     when $x = {\da}$

when $x = {\da}'$

x     otherwise

A swap of $\da$ and $\da'$ in ${\hypergraphG}$
is defined as
$\swap{\da}{\da'}{\hypergraphG} \eqdef {\hypergraphG} \circ \sigma_{\da}$.

The proof of Lemma <ref> goes viais by1003 induction on ${\setSizeK}$. We encapsulate the most important steps of the proof in
four lemmas.
Lemma <ref> is an auxiliary lemma.
Lemma <ref> forms the induction base. Lemmas
<ref> and <ref> cover the induction step.

Let $\hypergraphG$ be a $\setSizeK$-hypergraph and1007 $\simpleGraph{m}{\vec{a}}\changed{=(\setVertices,\mu)}{}{NULL}$ be an
${\setSizeK}$-hypergraphand let. Suppose,1007 $\da, \da'\notin \changed{{\setVertices}}{\support{\simpleGraph{m}{\vec{a}}}}{NULL}$
beare1007 two
Suppose and 1007$\simpleGraph{m}{\vec{a}}\in \sums{\Z}{\eqs{\cut{{\hypergraphG}}{\da}}}$.

* $\simpleGraph{m+1}{\vec{a}}=\revcut{\simpleGraph{m}{\vec{a}}}{\da} -
\revcut{\simpleGraph{m}{\vec{a}}}{\da'}$ is an $(m+1,\vec{a})-\simple$$(m+1,\vec{a})$-20

* $\simpleGraph{m+1}{\vec{a}}\in \sums{\Z}{\eqs{{\hypergraphG}}}$.

Claim 1.We start by showing Point 1.1011
Let ${\setVertices}= \setA' \cup \setB' \cup \setC'$, where $\setA', \setB',
\setC'$$\changed{{\setVertices}}{\support{\simpleGraph{m}{\vec{a}}}}{NULL}= \setA \cup \setB \cup \setC$, where $\setA,
\setB, \setC$1011 are such1011 as in
the definition of $(m,\vec{a})-\simple$$(m,\vec{a})$-20 hypergraph (Definition <ref>).
Let $\setA' = \{\da_1, {\da}_2 \ldots {\da}_m\}$ and $\setB' =
\{{\db}_1, {\db}_2 \ldots {\db}_m\}.$

$\setA = \{\da_1, {\da}_2 \ldots {\da}_m\}$ and $\setB =
\{{\db}_1, {\db}_2 \ldots {\db}_m\}.$
We define $\setA\eqdef \{{\da}_1, {\da}_2 \ldots {\da}_m, {\da}_{m+1}=\da\}$ and
$\setB \eqdef
\{{\db}_1,$ ${\db}_2 \ldots {\db}_m, {\db}_{m+1}=\da'\}.$

$\setA'\eqdef \{{\da}_1, {\da}_2 \ldots {\da}_m, {\da}_{m+1}=\da\}$ and
$\setB' \eqdef
\{{\db}_1,$ ${\db}_2 \ldots {\db}_m, {\db}_{m+1}=\da'\}.$
To show that $\simpleGraph{m+1}{\vec{a}}$ is $(m+1,\vec{a})-\simple$$(m+1,\vec{a})$-20 we split
$\changed{{\setVertices}}{\support{\simpleGraph{m}{\vec{a}}}}{NULL}\cup\{\da,\da'\}$ to
$\setA, \setB, $$\setA', \setB',
$1011 and $\setC'$$\setC$NULL and we verify
the propertiesProperties1014-1033 $1$ to $7$. The propertiesProperties1014-1033 $1$ to $3$ are trivial.
Properties $4$ to $6$ speak about function $\weight{setX}({\simpleGraph{m+1}{\vec{a}}})$ where:

* The propertyProperty1014-1033 $4$. ${\setX}$ contains exactly one vertex
from every pair ${\da}_i, {\db}_i$ for $0<i\leq m+1$. We consider only one of the two
casesHere, there are two cases: $\da\in \setX$ or $\da'\in \setX$. We consider only one of them1018
as the second one is very NULLsimilar. Suppose, that1018 $\da'\in {\setX}$.
Then $\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da}})=\vec{0}$ so

\[
\weight{setX}({\simpleGraph{m+1}{\vec{a}}})=-\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da'}})=
\]
Thus Thus, 177$\weight{setX}({\simpleGraph{m+1}{\vec{a}}})=-1\cdot (-1)^{\size{{\setX}\cap
\changed{\setB'}{\setB}{1011}}}\vec{a}=(-1)^{\size{{\setX}\cap \changed{B}{\setB}{1022}}}\vec{a}$, as required.

* The propertyProperty1014-1033 $5$. ${\setX}$ has $m+1$ elements but it is not of the type considered in one of the sets
considered in1023
the propertyProperty1014-1033 $4$. In this case
$\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da}})=\weight{setX}({\revcut{\simpleGraph{m}{\vec{a}}}{\da'}})=\vec{0}$, thus
1024, as required.

* The propertyProperty1014-1033 $6$. $\size{{\setX}}\leq m$. We consider four cases:

${\setX}\cap \{\da,\da'\}=\{\da,\da'\}$,
${\setX}\cap \set{\da,\da'}=\set{\da}$,
${\setX}\cap \set{\da,\da'}=\set{\da'}$, and