Perfect colorings of hypergraphs

Let $A=\{a_{i,j}\}$, $i=1,\ldots,n$, $j=1,\ldots,m$ be a matrix of size $n\times m$. If $n=m$ then $A$ is a matrix of order $n$.

We will say that a matrix $A$ of size $n\times m$ is a block matrix with blocks $B_{i,j}$ of sizes $n_{i}\times m_{j}$, $i=1,\ldots,k$, $j=1,\ldots,l$, $\sum\limits_{i=1}^{k}n_{i}=n$, $\sum\limits_{i=1}^{l}m_{j}=m$, if (after, possibly, appropriate permutations of rows and columns) the matrix $A$ can be presented in a form

For shortness, we write $A=\{B_{i,j}\}$.

Let $[n]=\{1,\dots,n\}$. A $d$-dimensional matrix $\mathbb{A}$ of order $n$ is an array of entries $(a_{\alpha})$, $a_{\alpha}\in\mathbb{R}$, indexed by tuples $\alpha\in[n]^{d}$, $\alpha=(\alpha_{1},\ldots,\alpha_{d})$. Vectors can be considered as $1$-dimensional matrices, and usual matrices have $2$ dimensions.

Let $\mathbb{A}$ be a $d$-dimensional matrix of order $n$. A hyperplane $\Gamma$ of direction $i$ in $\mathbb{A}$ is a $(d-1)$-dimensional submatrix obtained by fixing a value of index component $\alpha_{i}$ and letting the other $d-1$ components vary.

A matrix $\mathbb{A}$ is said to be symmetric if for every permutation $\sigma\in S_{d}$ and for every index $\alpha\in[n]^{d}$ we have $a_{\alpha}=a_{\sigma(\alpha)}$, where $\sigma(\alpha)=(\alpha_{\sigma(1)},\ldots,\alpha_{\sigma(d)})$. In other words, the matrix $\mathbb{A}$ does not change under permutations of directions of hyperplanes.

The $d$-dimensional identity matrix $\mathbb{I}$ is the matrix with entries $i_{\alpha}=1$ if $\alpha_{1}=\cdots=\alpha_{d}$ and $i_{\alpha}=0$ otherwise.

Let $\mathcal{G}=(X,E)$ be hypergraph on $n$ vertices with $m$ hyperedges. The incidence matrix $B$ of the hypergraph $\mathcal{G}$ is a matrix of size $n\times m$ such that $b_{x,e}=1$ if a vertex $x$ is incident to a hyperedge $e$ and $b_{x,e}=0$ otherwise.

If $\mathcal{G}$ is a uniform hypergraph, then we can define its multidimensional adjacency matrix. The adjacency matrix $\mathbb{A}$ of a $d$-uniform hypergraph $\mathcal{G}=(X,E)$ on $n$ vertices is a $d$-dimensional matrix of order $n$ in which entries $a_{\alpha}$ with index $\alpha=(x_{1},\ldots,x_{d})\in E$ are equal to $(d-1)!^{-1}$ and all other entries of $\mathbb{A}$ are $0$. Such scale of entries of the matrix $\mathbb{A}$ is taken for the sake of compactness of future expressions. By definition, the adjacency matrix $\mathbb{A}$ is symmetric.

If $G$ is a graph, then an eigenvalue of $G$ is an eigenvalue of its $2$-dimensional adjacency matrix. For hypergraphs, there are several ways to define eigenvalues, the most popular approaches use the following:

1. 1.

   maximization of some multilinear form generated by a hypergraph;

2. 2.

   eigenvalues of the $2$-dimensional signless Laplacian matrix $BB^{T}$;

3. 3.

   eigenvalues of the multidimensional adjacency matrix $\mathbb{A}$.

In this paper we will utilize the last of them. For a brief survey on other definitions of hypergraph eigenvalues see, e.g., the introduction of [coop.specrandcomp]. To define eigenvalues of multidimensional matrices, we use the following operation.

Let $\mathbb{A}$ be a $d$-dimensional matrix of order $n$ and $\mathbb{B}$ be a $t$-dimensional matrix of the same order. Define the product $\mathbb{A}\circ\mathbb{B}$ to be the $((d-1)(t-1)+1)$-dimensional matrix $\mathbb{C}$ of order $n$ with entries

where indices $\beta^{2},\ldots,\beta^{d}\in[n]^{t-1}$, $i\in[n]$.

The following properties of the product $\circ$ can be derived directly from the definition or found in [shao.tensprod].

Let $\mathbb{A}$ be a $d$-dimensional matrix of order $n$. We will say that $\lambda$ is an eigenvalue of $\mathbb{A}$ if there is a vector $x=(x_{1},\ldots,x_{n})$ such that $A\circ x=\lambda\mathbb{I}\circ x$, where $\mathbb{I}$ is a $d$-dimensional identity matrix of order $n$ and $\mathbb{I}\circ x$ is a vector $(x_{1}^{d-1},\ldots,x_{n}^{d-1})$. The vector $x$ is called an eigenvector corresponding to the eigenvalue $\lambda$, a pair $(\lambda,x)$ is said to be an eigenpair for $\mathbb{A}$.

If $\mathcal{G}$ is a $d$-uniform hypergraph with the $d$-dimensional adjacency $\mathbb{A}$, then the eigenvalues of the matrix $\mathbb{A}$ are said to be the eigenvalues of $\mathcal{G}$, the eigenvectors of $\mathbb{A}$ are the eigenvectors of $\mathcal{G}$.

The set $V(\lambda)\subset\mathbb{C}^{n}$ of all eigenvectors for an eigenvalue $\lambda$ is a complex algebraic variety, and the geometric multiplicity of the eigenvalue $\lambda$ is the dimension of $V(\lambda)$.

The present definition of eigenvalues and eigenvectors for tensors was proposed in 2005 by Lim [lim.eigentensor] and was studied for symmetric matrices by Qi [qi.eigentensor]. They used the theory of determinants of multidimensional matrices and resultants of multilinear systems developed in book [GeKaZe.multdet] by Gelfand, Kapranov, and Zelevinsky. In particular, they proved that all eigenvalues of a multidimensional matrix $\mathbb{A}$ are roots of its characteristic polynomial $\varphi_{\mathbb{A}}$.

The algebraic multiplicity of an eigenvalue $\lambda$ is said be its multiplicity as a root of the characteristic polynomial. It is well known that for $2$-dimensional matrices geometric and algebraic multiplicities coincide. Unfortunately, in the multidimensional case it is not true. For more information on relations between these multiplicities see [HuYe.multeigen].

The study of eigenvalues of multidimensional matrices and hypergraphs grows now extensively, so we mention here only several papers. In [CoopDut.hyperspec] Cooper and Dutle proved some properties of hypergraph spectra and calculate eigenvalues of certain classes of hypergraphs. In [shao.tensprod] it was introduced several products of hypergraphs and multidimensional matrices and then considered the eigenvalues of the result. Algebraic properties of eigenvalues and determinats of multidimensional matrices with respect to various matrix operations were studied in [ShaoShanZhang.detoftens]. At last, for some survey on the spectral theory of nonnegative matrices see [ChaQiZhang.survspecthyper].

Let us review some basic definitions and facts on perfect colorings of graphs that we aim to generalize for hypergraphs. Most of them can be found in [my.perfstrct].

A coloring of a graph $G=(X,E)$ in $k$ colors is a surjective function $f:X\rightarrow\{1,\ldots,k\}$. To every $k$-coloring $f$, we can put into a correspondence a rectangular color matrix $P$ of size $|X|\times k$ with entries $p_{x,i}=1$ if $f(x)=i$ and $p_{x,i}=0$ otherwise. Note that each row of $P$ contains exactly one nonzero entry. A coloring of a graph parts its vertex set $X$ into disjoint color classes $\{C_{1},\ldots,C_{k}\}$, where $C_{i}=\{x:f(x)=i\}$. In what follows, we usually define a coloring with the help of the color matrix $P$, but in some cases we also refer to the coloring function $f$ and the color classes $\{C_{1},\ldots,C_{k}\}$.

If $G$ is a bipartite graph and $f$ is a coloring of $G$, we will say that $f$ is a bipartite coloring if there are no color classes of $f$ that intersect both parts of $G$.

A $k$-coloring $f$ of a graph $G$ is called perfect if there exist integer $s_{i,j}$, $i,j\in\{1,\ldots,k\}$, such that every vertex of color $i$ in $f$ is adjacent to exactly $s_{i,j}$ vertices of color $j$. The matrix $S=(s_{i,j})$ of order $k$ is called the parameter matrix of the perfect coloring.

It is not hard to see that if $A$ is the adjacency matrix of a graph $G$, then $P$ is a perfect coloring with the parameter matrix $S$ if and only if $AP=PS$. Moreover, if $y$ is an eigenvector of the parameter matrix $S$ with an eigenvalue $\lambda$, then $Py$ is the eigenvector of $A$ with the same eigenvalue $\lambda$.

Given a coloring $P$, let us denote by $N$ the matrix $P^{T}P$. It can be checked that $N$ is a diagonal matrix with entries $n_{i,i}$ equal to the number of vertices of color $i$ and that the matrix $NS=P^{T}PS$ is symmetric.

We will say that a coloring $f$ of a graph $G$ with color classes $\{C_{1},\ldots,C_{k}\}$ is a refinement of a coloring $g$ with color classes $\{D_{1},\ldots,D_{l}\}$ if each color class $D_{i}$ is a union of some classes $C_{j}$. For a given graph $G$, its colorings (and perfect colorings) compose a partially ordered set with respect to the refinement.

For every coloring of a graph, there is the unique coarsest refinement that will be a perfect coloring. The method of finding such refinements is known as Weisfeiler–Leman algorithm [WeiLeh.algo].

A graph $G=(X,E)$ covers a graph $H=(Y,U)$ if there exists a surjective function $\varphi:X\rightarrow Y$ such that for each $x\in X$ the equality $\{\varphi(x^{\prime})|(x,x^{\prime})\in E\}=\{y|(y,\varphi(x))\in U\}$ holds. A covering $\varphi$ of a graph $H$ by $G$ is a $k$-covering if for every $y\in Y$ there are exactly $k$ vertices $x\in X$ such that $\varphi(x)=y$. It is well known that every covering is a $k$-covering for some $k\in\mathbb{N}$.

It is not hard to see that a graph $G$ covers a graph $H$ if and only if there is a perfect coloring of $G$ with the parameter matrix equal to the adjacency matrix of $H$. It implies, for example, the following simple properties of coverings:

• •

  If a graph $G$ covers a graph $H$ and a graph $H$ covers a graph $F$, then $G$ covers $F$.

• •

  If a graph $G$ covers a graph $H$ and $\lambda$ is an eigenvalue of $H$, then $\lambda$ is an eigenvalue of $G$.

In [leighton.comcover, AngGard.comcover], it was proved that if graphs $H_{1}$ and $H_{2}$ have perfect colorings with the same parameter matrices, then there exists a graph $G$ that covers both $H_{1}$ and $H_{2}$.

For more information of graph coverings and their applications see [GodRoy.alggrath].

Let $\mathcal{G}(X,E)$ be a hypergraph. We will say that a surjective function $f:X\rightarrow\{1,\ldots,k\}$ is a coloring of $\mathcal{G}$ into $k$ colors (or $k$-coloring). In other words, $f$ defines a partition of the set $X$ in $k$ color classes. Given a coloring $f$ and a hyperedge $e$, let the color range $f(e)$ be the multiset of colors of all incident vertices: $f(e)=\{f(x)|x\in e\}$.

Let $G$ be the incidence graph of the hypergraph $\mathcal{G}$. To each coloring $f$ of $\mathcal{G}$, we associate an induced coloring $g$ of $G$ such that for every $x\in X$ we have $g(x)=f(x)$ and for every $e\in E$ we define $g(e)=f(e)$. Here the color ranges $f(e)$ of hyperedges are considered as colors of the coloring $g$. Note that every induced coloring of $G$ is bipartite, but not every bipartite coloring of $G$ is induced by some coloring of $\mathcal{G}$.

A coloring $f$ of a hypergraph $\mathcal{G}$ is said to be perfect if each two vertices $x$ and $y$ of the same color have the same set of color ranges of incident hyperedges. Directly from the definitions, it follows that $f$ is a perfect coloring of $\mathcal{G}$ if and only if the induced bipartite coloring $g$ of $G$ is perfect.

We will say that a rectangular $(0,1)$-matrix $P$ is a color matrix if every row of $P$ contains exactly one $1$. To every $k$-coloring $f$ of a hypergraph $\mathcal{G}(X,E)$ on $n$ vertices, we associate the color matrix $P$ of size $n\times k$ such that $p_{x,i}=1$ if $f(x)=i$ and $p_{x,i}=0$ otherwise.

Assume that a hypergraph $\mathcal{G}(X,E)$ has $n$ vertices, $m$ hyperedges, and the incidence matrix $B$. Let $f$ be a perfect $k$-coloring of $\mathcal{G}$ such that the number of different color ranges $\gamma$ of hyperedges is equal to $l$. Then the induced coloring $g$ of the incidence graph $G$ gives us the following matrix equation:

or, equivalently,

where

• •

  $P$ and $R$ are vertex and hyperedge color matrices of sizes $n\times k$ and $m\times l$, respectively; the coloring $R$ is induced by the coloring $P$.

• •

  $V$ and $W$ are matrices of sizes $k\times l$ and $l\times k$, respectively. An entry $v_{i,\gamma}$ of $V$ is equal to the number of hyperedges of color range $\gamma$ in $\mathcal{G}$ incident to a vertex of color $i$, entry $w_{\gamma,i}$ of $W$ is equal to the number of vertices of color $i$ in $\mathcal{G}$ contained in a hyperedge of color range $\gamma$.

We will say that the pair $(V,W)$ is the incidence parameters of the perfect coloring $f$: the matrix $V$ is said to be the XE-parameter matrix (describing incidence of vertices $x$ to hyperedges $e$), and $W$ is the EX-parameter matrix (describing incidence of hyperedges $e$ to vertices $x$).

Example 1. Let $\mathcal{G}$ be a $3$-uniform hypergraph with the vertex set $X=\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6}\}$ and the hyperedge set $E=\{e_{1},e_{2},e_{3},e_{4}\}$, where $e_{1}=\{x_{1},x_{2},x_{3}\}$, $e_{2}=\{x_{1},x_{4},x_{5}\}$, $e_{3}=\{x_{2},x_{4},x_{6}\}$, $e_{4}=\{x_{3},x_{5},x_{6}\}$.

Let $f$ be a coloring of $X$ into two colors such that $f(x_{1})=f(x_{2})=f(x_{3})=1$ and $f(x_{4})=f(x_{5})=f(x_{6})=2$. Then the color ranges of hyperedges are $f(e_{1})=\{1,1,1\}$ and $f(e_{2})=f(e_{3})=f(e_{4})=\{1,2,2\}$. Note that each vertex of color $1$ is incident to one hyperedge of color range $\{1,1,1\}$ and one hyperedge of color range $\{1,2,2\}$, and each vertex of color $2$ is incident to two hyperedges of color range $\{1,2,2\}$. Therefore, $f$ is a perfect coloring of $\mathcal{G}$.

The incidence graph $G$ of $\mathcal{G}$ with the induced perfect coloring $g$ is given at Figure 1.

The incidence matrix of the hypergraph $G$ is

By the definition, the vertex color matrix $P$ and the hyperedge color matrix $R$ for the perfect coloring $f$ are

and the incidence parameters $(V,W)$ are

It can be checked directly that $BR=PV$ and $B^{T}P=RW$.

Let us derive several simple observations from the given definition of a perfect coloring of hypergraphs.

First of all, if vertices $x$ and $y$ of a hypergraph $\mathcal{G}$ have different degrees, then $f(x)\neq f(y)$ for every perfect coloring $f$ of $\mathcal{G}$ because the same is true for perfect colorings of graphs. The sum of entries in the $i$-th row of the XE-parameter matrix $V$ is equal to the degree of vertices of color $i$, and the sum of entries in the $\gamma$-th row of the EX-parameter matrix $W$ is equal to the size of a hyperedge of the color range $\gamma$.

Next, if $P$ is a coloring of vertices and $R$ is a coloring of hyperedges, then $N=P^{T}P$ and $M=R^{T}R$ are diagonal matrices. Entries $n_{i,i}$ of $N$ are equal to the numbers of vertices colored by color $i$ in $P$, and entries $m_{j,j}$ of $M$ are the numbers of hyperedges colored by color $j$ in $R$.

We also prove the following results on the structure of the incidence matrix $B$ and a relation between the incidence parameters $(V,W)$ and matrices $N$ and $M$.

At last, we define refinements of perfect colorings in hypergraphs similar to graphs. We will say that a coloring $f$ of a hypergraph $\mathcal{G}$ is a refinement of a coloring $g$ if the coloring of the incidence graph of $\mathcal{G}$ induced by $f$ is a refinement of the coloring induced by $g$. The set of perfect colorings of a hypergraph with respect to the refinement forms a partially ordered set. Theorem 2 implies the following.

We will say that the coloring $f$ from Theorem 4 is the minimal perfect coloring of the hypergraph $\mathcal{G}$.

Let $\mathcal{G}(X,E)$ be a $d$-uniform hypergraph on $n$ vertices, $\mathbb{A}$ be the $d$-dimensional adjacency matrix of $\mathcal{G}$, and $P$ be a coloring of $\mathcal{G}$ into $k$ colors (color matrix of vertices). We will say that $P$ is perfect if there exists a $d$-dimensional matrix $\mathbb{S}$ of order $k$ such that

where the product $\circ$ of multidimensional matrices is defined in Section 2. The matrix $\mathbb{S}$ is called the parameter matrix of the perfect coloring $P$.

Let us show that this definition of perfect colorings in case of uniform hypergraphs is equivalent to the previous one. Moreover, we express entries of the parameter matrix $\mathbb{S}$ by the incidence parameters $(V,W)$.

Note that a perfect coloring $P$ defines only the factor $v_{\gamma_{1},\gamma}$ in the entries $s_{\gamma}$ of the matrix $\mathbb{S}$, while the factor ${d-1\choose d_{1},\ldots,d_{k}}^{-1}$ in $s_{\gamma}$ depends only on the index $\gamma$ and it is the same for all $d$-dimensional parameter matrices $\mathbb{S}$.

Example 2. Let $\mathcal{G}$ be the $3$-uniform hypergraph on $6$ vertices from Example 1 and $P$ be its perfect coloring:

Recall that the incidence parameters $(V,W)$ for this coloring are

The adjacency matrix $\mathbb{A}$ of the hypergraph $\mathcal{G}$ is the following $3$-dimensional matrix of order $6$:

It can be checked directly that $\mathbb{A}\circ P=P\circ\mathbb{S}$ for the $3$-dimensional parameter matrix

where $s_{1,1,1}=v_{1,1}/1=1$, $s_{1,2,2}=v_{1,2}/1=1$, $s_{2,2,1}=s_{2,1,2}=v_{2,2}/2=1$. Note that $s_{1,1,2}=s_{1,2,1}=s_{2,1,1}=s_{2,2,2}=0$ because there are no hyperedges of color ranges $\{1,1,2\}$ and $\{2,2,2\}$ in the perfect coloring $P$.

Using the obtained results, let us prove several properties of the parameter matrix $\mathbb{S}$.