# On the distribution of eigenvalues in families of Cayley graphs

Matilde Lalin  Université de Montréal, Pavillon André-Aisenstadt, Dépt. de
mathématiques et de statistique, CP 6128, succ. Centre-ville, Montréal,
Québec, H3C 3J7, Canada<EMAIL_ADDRESS>and  Anwesh Ray  Centre de
recherches mathématiques, Université de Montréal, Pavillon André-Aisenstadt,
2920 Chemin de la tour, Montréal (Québec) H3T 1J4, Canada
<EMAIL_ADDRESS>
###### Abstract.

We consider the family of undirected Cayley graphs associated with odd cyclic
groups, and study statistics for the eigenvalues in their spectra. Our results
are motivated by analogies between arithmetic geometry and graph theory.

###### Key words and phrases:

arithmetic statistics, graph theory, eigenvalue distribution

###### 2020 Mathematics Subject Classification:

05C25, 11H06, 11N60, 11M38

##  1\. Introduction

It is well known that there are deep analogies between the arithmetic of
curves in positive characteristic and the combinatorial properties of graphs.
Ihara [Iha66a] and Sunada [Sun86] defined the zeta function associated to a
locally finite connected graph. The definition closely resembles the _Selberg
zeta function_ and encodes asymptotics for closed walks in the graph. There is
a close analogy between the zeta functions of curves in positive
characteristic and the Ihara zeta functions associated to graphs. Further
analogies have been realized by Baker and Norine [BN09], who etablished an
analogue of the Abel-Jacobi map and the Riemann-Roch theorem in graph theory.
In recent years, there has been considerable interest in graph theoretic
questions that are motivated by arithmetic statistics. The sandpile group
(also known as the Jacobian group, the critical group, or the Picard group) is
an abelian group naturally associated to a graph that codifies structural
information of the graph. The statistics of such groups have been studied by
various authors [CKL+15, Woo17]. More recently, the arithmetic statistics in
the context of the Iwasawa theory of graphs has been studied in [DRLV22].

It is natural to study statistical questions for the poles of the Ihara zeta
function [Iha66b, Bas92, Ter11]. For a finite regular graph, Ihara related the
poles of the zeta function to the spectrum of the adjacency matrix. The
spacing between the eigenvalues of regular graphs has been studied via
numerical computation, and related to the Gaussian orthogonal ensemble, cf.
[JMRR99, New05]. Cayley graphs are central objects in the combinatorial and
geometric group theory. They allow us to visualize a group with respect to a
generating set. Its spectrum can be described very concretely [Val94]. The
main focus of this work is to study distribution questions for the family of
eigenvalues that arise from Cayley graphs of finite odd cyclic groups.

###  1.1. Main result

We now state our main result. Let $r\in\mathbb{Z}_{\geq 1}$ and let
$\mathcal{F}$ be an infinite family of $r$-regular graphs with real
eigenvalues. A _counting function_ $h\mathrel{\mathop{\mathchar
58\relax}}\mathcal{F}\rightarrow\mathbb{Z}_{\geq 1}$ is a function such that
for any $x\in\mathbb{R}_{\geq 0}$, there are only finitely many graphs
$X\in\mathcal{F}$ that satisfy $h(X)\leq x$. Note that any eigenvalue of an
$r$-regular graph in $\mathcal{F}$ lies in the interval $[-r,r]$. Given an
interval $J=[a,b]$ contained in $[-r,r]$, we wish to evaluate the probability
that a random eigenvalue of a graph in $\mathcal{F}$ does lie in $J$. We
consider families of Cayley graphs associated with cyclic groups with odd
order. Given an odd natural number $n$, let $C_{n}$ denote the cyclic group
with $n$ elements, which we identify with $\mathbb{Z}/n\mathbb{Z}$. For a pair
$\gamma=(G,S)$ such that $S=S^{-1}$, recall that $X_{\gamma}$ is the
associated Cayley graph. The association $\gamma\mapsto X_{\gamma}$ gives us a
way to parametrize Cayley graphs. In greater detail, we set

$\mathcal{F}_{r}\mathrel{\mathop{\mathchar
58\relax}}=\left\\{X_{\gamma}\mid\gamma=(G,S);G=C_{n}\text{ for some odd
number }n>1,\\#S=r,S=S^{-1}\right\\}.$

Thus, $\mathcal{F}_{r}$ is an infinite family of $r$-regular graphs; define a
height function by setting $h(X_{\gamma})\mathrel{\mathop{\mathchar
58\relax}}=n$, where $\gamma=(C_{n},S)$. There are only finitely many Cayley
graphs for a given group, and hence, $h$ is a counting function.

For $x\geq 0$, let $\sqrt{x}$ be the non-negative square root of $x$. Set
$\delta$ denote the normalized arcsine distribution

$\delta(u)\mathrel{\mathop{\mathchar
58\relax}}=\begin{cases}\frac{1}{\pi\sqrt{1-u^{2}}}&\text{ if }u\in[-1,1];\\\
0&\text{ otherwise;}\\\ \end{cases}$

and let $\delta^{(k)}(u)$ be the $k$-fold convolution

$\delta^{(k)}(u)\mathrel{\mathop{\mathchar
58\relax}}=\int_{-1}^{1}\dots\int_{-1}^{1}\delta(u_{1})\delta(u_{2})\cdots\delta(u_{k-1})\delta\left(u-\sum_{i=1}^{k-1}u_{i}\right)du_{1}\cdots
du_{k-1}.$

Given a graph $X$, let $\operatorname{Sp}(X)$ denote its spectrum, i.e., the
set of eigenvalues for its adjacency matrix.

######  Theorem 1.1.

Let $r\in\mathbb{Z}_{\geq 2}$ and set $k\mathrel{\mathop{\mathchar
58\relax}}=\lfloor\frac{r}{2}\rfloor$. Let $J=[a,b]$ be an interval contained
in $[-k,k]$. Set $I=[c,d]\subseteq[-k,k]$ to denote the interval $[a/2,b/2]$
(resp. $[(a-1)/2,(b-1)/2]$) if $r$ is even (resp. $r$ is odd). Then, we have
that

$\lim_{n\rightarrow\infty}\frac{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n,\alpha\in J\\}}{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n\\}}=\int_{c}^{d}\delta^{(k)}(u)du.$

More precisely, as $n\rightarrow\infty$,

$\begin{split}&\frac{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n,\alpha\in J\\}}{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n\\}}\\\ =&\int_{c}^{d}\delta^{(k)}(u)du+O(n^{-1+\epsilon}),\end{split}$

where the implicit constant in the error term only depends on $r$.

The above theorem is a direct consequence of Theorem 5.5. We note that the
eigenvalues in the spectrum of a Cayley graph in $\mathcal{F}_{1}$ are all
equal to $1$, hence, we only consider the case when $r\geq 2$. The above
probabilities are reinterpreted in terms of certain lattice point counts in
certain regions in euclidean space. These lattice point counts are estimated
via a combination combinatorial and analytic techniques.

### Acknowledgements

The authors would like to thank Daniel Vallières for helpful discussions. This
work is supported by the Natural Sciences and Engineering Research Council of
Canada, Discovery Grant 355412-2022, the Fonds de recherche du Québec - Nature
et technologies, Projet de recherche en équipe 300951, the Simons Foundation,
and the Centre de recherches mathématiques.

##  2\. Preliminaries

###  2.1. Basic definitions and properties of graphs

In this section, we recall a few preliminary notions in graph theory. For a
more detailed exposition, we refer to [Sun13]. The data of a directed graph
$X$ consists of a tuple $(V_{X},\mathbf{E}_{X})$, where $V_{X}$ is the set of
vertices and $\mathbf{E}_{X}$ is the set of directed edges. The map
$\operatorname{inc}\mathrel{\mathop{\mathchar
58\relax}}\mathbf{E}_{X}\rightarrow V_{X}\times V_{X}$ is the incidence map.
The source and target maps $o\mathrel{\mathop{\mathchar
58\relax}}\mathbf{E}_{X}\rightarrow V_{X}$ and $t\mathrel{\mathop{\mathchar
58\relax}}\mathbf{E}_{X}\rightarrow V_{X}$ send a directed edge to the source
and target vertices respectively, and $\operatorname{inc}(e)=(o(e),t(e))$.
Given $e\in\mathbf{E}_{X}$, we say that $e$ joins $o(e)$ to $t(e)$. We shall
make the following assumptions on our graphs $X$.

  1. (1)

The sets $V_{X}$ and $\mathbf{E}_{X}$ are finite.

  2. (2)

Given vertices $v_{1}\in V_{X}$ and $v_{2}\in V_{X}$ (not necessarily
distinct), there is at most one edge joining $v_{1}$ to $v_{2}$.

  3. (3)

Given any edge $e\in\mathbf{E}_{X}$, there is an edge $\bar{e}$ such that
$o(\bar{e})=t(e)$ and $t(\bar{e})=o(e)$. Note that if $o(e)=t(e)$ (i.e., $e$
is a loop), then $\bar{e}=e$.

Consider an equivalence relation on the set $\mathbf{E}_{X}$ of directed
edges, identifying $e$ with $\bar{e}$. The equivalence classes consist of
undirected edges of the graph and are denoted by $E_{X}$. Given $v\in V_{X}$,
we consider the set of directed edges that orginate at $v$,

$\mathbf{E}_{X,v}\mathrel{\mathop{\mathchar
58\relax}}=\\{e\in\mathbf{E}_{X}\mid o(e)=v\\}.$

The valency of $v$ is defined as follows
$\operatorname{val}_{X}(v)\mathrel{\mathop{\mathchar
58\relax}}=\\#\mathbf{E}_{X,v}$. Alternatively, the valency is also the number
of undirected edges which contain $v$ as one of its vertices. The graph is
$r$-regular if $\operatorname{val}_{X}(v)=r$ for all $v\in V_{X}$. Let
$g\mathrel{\mathop{\mathchar 58\relax}}=\\#V_{X}$ and choose a labelling on
the vertices $V_{X}=\\{v_{1},\dots,v_{g}\\}$. Consider the $g\times g$
diagonal matrix defined by

$d_{i,j}=\begin{cases}&0\text{ if }i\neq j;\\\
&\operatorname{val}_{X}(v_{i})\text{ if }i=j.\\\ \end{cases}$

The adjacency matrix $A=(a_{i,j})$ is defined as follows

$a_{i,j}=\begin{cases}&\text{number of undirected edges between }v_{i}\text{
and }v_{j}\text{ if }i\neq j;\\\ &\text{twice the number of undirected loops
at }v_{i}\text{ if }i=j.\\\ \end{cases}$

The spectrum $\operatorname{Sp}(X)$ is the set of eigenvalues $\alpha$ of the
adjacency matrix $A$. The matrix $Q\mathrel{\mathop{\mathchar 58\relax}}=D-A$
is called the _Laplacian matrix_ of the graph $X$. Let us explain the explicit
relationship between the eigenvalues of the adjacency matrix and the poles of
_Ihara zeta function_ associated to $X$. A path in $X$ is a sequence
$C=a_{1},\dots,a_{k}$, where $(a_{1},\dots,a_{k})$ is a tuple of directed
edges of $X$ such that $t(a_{i})=o(a_{i+1})$. The length of $C$ is the number
of edges $\nu(C)\mathrel{\mathop{\mathchar 58\relax}}=k$. A closed path is a
path for which $o(a_{1})=t(a_{k})$, i.e. a path starting and ending at the
same vertex. The path is said to have a _backtrack_ if
$a_{j+1}=\overline{a_{j}}$ for some $j$ in the range $1\leq j\leq k-1$. The
path is said to have a _tail_ if $a_{k}=\overline{a_{1}}$. Given a closed path
$D$, and an integer $m>0$, $D^{m}$ is the path obtained by moving around $D$
$m$-times. A closed path $C$ is said to be primitive if $C$ has no backtracks
or tails and $C\neq D^{m}$ for any closed path $D$ and $m>1$. Two closed paths
are equivalent if one can be obtained from the other by changing the starting
vertex. Note that if $C$ is primitive, there are exactly $\nu(C)$ paths that
are equivalent to $C$. A _prime_ path is an equivalence class of primitive
paths. We shall sometimes denote the equivalence class of a primitive path $C$
by $[C]$, however, when there is no cause for confusion, we simply use $C$
itself to denote the prime path with primitive representative $C$.

The _Ihara polynomial_ $h_{X}(u)$ denotes the determinant

$h_{X}(u)\mathrel{\mathop{\mathchar 58\relax}}=\det(I-Au+Qu^{2}).$

Suppose that $X$ is connected with no vertex of degree $1$. With these
definitions in mind, the Ihara zeta function is defined to be the product

$\zeta_{X}(u)=\prod_{C}(1-u^{\nu(C)})^{-1},$

where the product ranges over all primes in $X$, ordered according to length.
Then the Ihara $3$-term determinant formula states that

$\zeta_{X}(u)^{-1}=(1-u^{2})^{r(X)-1}h_{X}(u),$

where $r(X)$ is rank of the fundamental group, $r(X)=|E|-|V|+1$. Note that
when $X$ is $r$-regular, where $r\geq 2$. Then $Q=(r-1)\operatorname{Id}$, and

$h_{X}(u)=\prod_{\alpha\in\operatorname{Sp}(X)}\left(1-\alpha
u+(r-1)u^{2}\right).$

Therefore, the roots of $h_{X}(u)$ are given by

$r_{\alpha}^{\pm}=\frac{\alpha\pm\sqrt{\alpha^{2}-4(r-1)}}{2(r-1)},$

where $\alpha\in\operatorname{Sp}(X)$.

Let $G$ be a finite group and $S$ be a subset of $G$ such that
$S^{-1}\mathrel{\mathop{\mathchar 58\relax}}=\\{s^{-1}\mid s\in S\\}$ is equal
to $S$. Associated to the pair $\gamma=(G,S)$ is the undirected Cayley graph
$X_{\gamma}$. The vertices $V_{\gamma}\mathrel{\mathop{\mathchar
58\relax}}=V_{X_{\gamma}}$ is the set $\\{v_{g}\mid g\in G\\}$, and there is
an undirected edge joining $v_{g}$ to $v_{h}$ if and only if $gh^{-1}$ is
contained in $S$. Consider the special case when $G$ is a finite abelian group
and $\widehat{G}\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{Hom}(G,\mathbb{C}^{\times})$ be the group of
characters defined on $G$. A Cayley graph $X_{\gamma}$ is $r$-regular, where,
$r\mathrel{\mathop{\mathchar 58\relax}}=\\#S$. Given a character,
$\chi\in\widehat{G}$, set
$\lambda_{\chi}(X_{\gamma})\mathrel{\mathop{\mathchar 58\relax}}=\sum_{s\in
S}\chi(s)$. The spectrum $\operatorname{Sp}(X_{\gamma})$ is the set of
eigenvalues of the adjacency matrix and is equal to the set
$\\{\lambda_{\chi}(X_{\gamma})\mid\chi\in\widehat{G}\\}$. Since $S=S^{-1}$, we
find that the eigenvalues $\lambda_{\chi}(X_{\gamma})$ are all real and
contained in $[-r,r]$.

##  3\. Eigenvalues of Cayley graphs

Let $r\in\mathbb{Z}_{\geq 2}$, and recall that $\mathcal{F}_{r}$ is the family
of Cayley graphs

$\mathcal{F}_{r}\mathrel{\mathop{\mathchar
58\relax}}=\left\\{X_{\gamma}\mid\gamma=(G,S);G=C_{n}\text{ for some odd
number }n>1,\\#S=r,S=S^{-1}\right\\}.$

Since $n$ is assumed to be odd, we find that $r=\\#S$ is odd precisely when
$S$ contains $0$. In this case, we write

$\begin{cases}r=2k&\text{ if }r\text{ is even},\\\ r=2k+1&\text{ if }r\text{
is odd.}\\\ \end{cases}$

In either case, we may write $S\backslash\\{0\\}=T\cup\left(-T\right)$, where
$T=\\{a_{1},\dots,a_{k}\\}$ and $1\leq a_{i}\leq\left(\frac{n-1}{2}\right)$
for $i=1,\dots,k$. We shall assume without loss of generality that $1\leq
a_{1}<a_{2}<\dots<a_{k}\leq\left(\frac{n-1}{2}\right)$. Let $S$ be a subset of
$G=C_{n}$ such that $\\#S=r$ and $S=-S$. We set
$\gamma\mathrel{\mathop{\mathchar 58\relax}}=(G,S)$. As $\chi$ ranges over
$\widehat{G}$, the eigenvalues $\lambda_{\chi}(X_{\gamma})$ are all distinct.
Recall that the spectrum of $X_{\gamma}$ is given by
$\operatorname{Sp}(X_{\gamma})=\\{\lambda_{\chi}(X_{\gamma})\mid\chi\in\widehat{G}\\}$.
For an integer $m\in[0,n-1]$, let $\chi_{m}\in\widehat{C_{n}}$ be the
character defined by $\chi_{m}(x)\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{exp}\left(\frac{2\pi imx}{n}\right)$. We set
$\lambda_{m}(\gamma)\mathrel{\mathop{\mathchar
58\relax}}=\lambda_{\chi}(X_{\gamma})$ and we find that

(3.1)
$\lambda_{m}(\gamma)=\lambda_{\chi_{m}}(\gamma)=\begin{cases}1+\sum_{j=1}^{k}2\operatorname{cos}\left(\frac{2\pi
ma_{j}}{n}\right)&\text{ if }r\text{ is odd,}\\\
\sum_{j=1}^{k}2\operatorname{cos}\left(\frac{2\pi ma_{j}}{n}\right)&\text{ if
}r\text{ is even.}\\\ \end{cases}$

In particular, we note that $\lambda_{0}(\gamma)=r$ is the largest eigenvalue.

We set $A_{k}(n)$ to denote the set of all vectors
$\vec{a}=(a_{1},\dots,a_{k})\in\mathbb{Z}^{k}$ such that $1\leq
a_{1}<a_{2}<\dots<a_{k}\leq\left(\frac{n-1}{2}\right)$. Given $\vec{a}\in
A_{k}(n)$, let $\gamma_{\vec{a}}\mathrel{\mathop{\mathchar
58\relax}}=(C_{n},S_{\vec{a}})$, where $S_{\vec{a}}$ is the set with $r$
elements such that
$S\backslash\\{0\\}=\\{a_{1},-a_{1},a_{2},-a_{2},\dots,a_{r},-a_{r}\\}$. We
set

$\tau_{m}(\vec{a})=\tau_{m}(\gamma_{\vec{a}})\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i=1}^{k}\operatorname{cos}\left(\frac{2\pi
ma_{i}}{n}\right).$

Therefore, from (3.1), we find that

$\lambda_{m}(\vec{a})=\lambda_{m}(\gamma_{\vec{a}})=\begin{cases}1+2\tau_{m}(\vec{a})&\text{
if }r\text{ is odd,}\\\ 2\tau_{m}(\vec{a})&\text{ if }r\text{ is even.}\\\
\end{cases}$

We find that $\tau_{m}(\vec{a})\in[-k,k]$, and that
$\lambda_{m}(\vec{a})\in[-r,r]$. Let $\mathcal{S}(n,k)$ be the set of pairs
$\left(\gamma_{\vec{a}},\tau_{m}(\vec{a})\right)$, where $\vec{a}\in
A_{k}(n)$, and $m\in[0,n-1]$. Let $\mathcal{S}(n,k,m)$ be the subset of
$\mathcal{S}(n,k)$ where $m$ is fixed. Given and interval
$[e,f]\subset\mathbb{R}$, we set $[e,f]_{\mathbb{Z}}\mathrel{\mathop{\mathchar
58\relax}}=\mathbb{Z}\cap[e,f]$. We identify $\mathcal{S}(n,k)$ with
$A_{k}(n)\times\left[0,n-1\right]_{\mathbb{Z}}$. Moreover, we identify
$\mathcal{S}(n,k,m)$ with $A_{k}(n)$, upon identifying $\vec{a}\in A_{k}(n)$
with $(\vec{a},m)\in A_{k}(n)\times\left[0,n-1\right]_{\mathbb{Z}}$. We refer
to $\mathcal{S}(n,k,m)$ as the _$m$ -slice_ in $\mathcal{S}(n,k)$. Let
$J=[a,b]\subseteq[-r,r]$ be a closed interval and $I=[c,d]\subseteq[-k,k]$
defined by

$[c,d]=\begin{cases}[a/2,b/2]&\text{ if }r\text{ is even};\\\
[(a-1)/2,(b-1)/2]&\text{ if }r\text{ is odd}.\end{cases}$

Note that $\lambda_{m}(\vec{a})\in J$ if and only if $\tau_{m}(\vec{a})\in I$.
Set $\mathcal{S}_{I}(n,k)\subseteq\mathcal{S}(n,k)$ (resp.
$\mathcal{S}_{I}(n,k,m)\subseteq\mathcal{S}(n,k,m)$) to denote the subset for
which $\tau_{m}(\vec{a})\in I$.

We have the following identifications

(3.2) $\begin{split}&\mathcal{S}_{I}(n,k,m)=\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n\\},\\\ &\mathcal{S}_{I}(n,k,m)=\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n,\alpha\in J\\}.\\\ \end{split}$

It is easy to see that

$\begin{split}&\\#\mathcal{S}(n,k,m)=\binom{\frac{n-1}{2}}{k},\\\
&\\#\mathcal{S}(n,k)=n\binom{\frac{n-1}{2}}{k}.\\\ \end{split}$

For $n,k\in\mathbb{Z}_{\geq 1}$ such that $n$ is odd and $k\leq\frac{n-1}{2}$,
set

$\operatorname{Prob}_{I}\left(n,k\right)\mathrel{\mathop{\mathchar
58\relax}}=\frac{\\#\mathcal{S}_{I}(n,k)}{\\#\mathcal{S}(n,k)}.$

Note that after making the identifications (3.2), we have that

(3.3) $\operatorname{Prob}_{I}\left(n,k\right)=\frac{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n\text{ and }\alpha\in J\\}}{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n\\}}.$

For a fixed integer $k\in\mathbb{Z}_{\geq 1}$, we wish to compute the limit

$\begin{split}\operatorname{Prob}_{I}(k)\mathrel{\mathop{\mathchar
58\relax}}=&\lim_{n\rightarrow\infty}\operatorname{Prob}_{I}\left(n,k\right),\\\
=&\lim_{n\rightarrow\infty}\left(\frac{(2^{k}k!)\\#\mathcal{S}_{I}(n,k)}{n^{k+1}}\right).\end{split}$

We express $\operatorname{Prob}_{I}(k)$ as an average

(3.4)
$\operatorname{Prob}_{I}(n,k)=\frac{1}{n}\sum_{m=0}^{n-1}\operatorname{Prob}_{I}(n,k,m),$

where

$\operatorname{Prob}_{I}(n,k,m)\mathrel{\mathop{\mathchar
58\relax}}=\frac{\\#\mathcal{S}_{I}(n,k,m)}{\\#\mathcal{S}(n,k,m)}=\frac{\\#\mathcal{S}_{I}(n,k,m)}{\binom{\frac{n-1}{2}}{k}}.$

In the next section, we shall set up a geometric interpretation for the
probability $\operatorname{Prob}_{I}(n,k,m)$. Let $B_{k}$ denote the
$k$-dimensional box

$B_{k}\mathrel{\mathop{\mathchar 58\relax}}=\\{(x_{1},\dots,x_{k})\mid 0\leq
x_{i}<1/2\text{ for all }i\\},$

and note that $\operatorname{Vol}(B_{k})=2^{-k}$. Let $B_{k}(I)$ be the subset
of $B_{k}$ defined by

(3.5) $B_{k}(I)\mathrel{\mathop{\mathchar 58\relax}}=\\{(x_{1},\dots,x_{k})\in
B_{k}\mid\sum_{i=1}^{k}\operatorname{cos}(2\pi x_{i})\in I\\}.$

Let us compute $\operatorname{Vol}\left(B_{k}(I)\right)$ for an interval
$I=[c,d]$. Let $D_{k}(I)\mathrel{\mathop{\mathchar
58\relax}}=\\{(u_{1},\dots,u_{k})\in[-1,1]^{k}\mid\sum_{i}u_{i}\in I\\}$, and
$\Phi$ be the function taking $D_{k}(I)$ to $B_{k}(I)$ defined by
$\Phi(u_{1},\dots,u_{k})=\left(\frac{1}{2\pi}\operatorname{cos}^{-1}(u_{1}),\dots,\frac{1}{2\pi}\operatorname{cos}^{-1}(u_{k})\right)$.
For $x\geq 0$, let $\sqrt{x}$ be the non-negative square root of $x$. Set

$\delta(u)\mathrel{\mathop{\mathchar
58\relax}}=\begin{cases}\frac{1}{\pi\sqrt{1-u^{2}}}&\text{ if }u\in[-1,1];\\\
0&\text{ otherwise;}\\\ \end{cases}$

and let $\delta^{(k)}(u)$ be the $k$-fold convolution

$\delta^{(k)}(u)\mathrel{\mathop{\mathchar
58\relax}}=\int_{-1}^{1}\dots\int_{-1}^{1}\delta(u_{1})\delta(u_{2})\cdots\delta(u_{k-1})\delta\left(u-\sum_{i=1}^{k-1}u_{i}\right)du_{1}\cdots
du_{k-1}.$

######  Lemma 3.1.

Let $I=[c,d]\subseteq[-k,k]$ be an interval, $k\in\mathbb{Z}_{\geq 1}$, and
let $B_{k}(I)\subset\mathbb{R}^{k}$ be the region defined by (3.5). Then, its
volume is given by

$\operatorname{Vol}\left(B_{k}(I)\right)=2^{-k}\int_{c}^{d}\delta^{(k)}(u)du.$

###### Proof.

By the change of variables theorem, we find that

(3.6)
$\begin{split}\operatorname{Vol}\left(B_{k}(I)\right)=&\int_{D_{k}(I)}|\operatorname{det}D\Phi|\\\
=&(2\pi)^{-k}\int_{D_{k}(I)}\frac{1}{\left(\sqrt{1-u_{1}^{2}}\sqrt{1-u_{2}^{2}}\dots\sqrt{1-u_{r}^{2}}\right)}du_{1}\dots
du_{r}\\\ =&2^{-k}\int_{c}^{d}\delta^{(k)}(u)du.\end{split}$

∎

##  4\. A geometric interpretation

We wish to provide a geometric reinterpretation for the quantities
$\\#\mathcal{S}_{I}(n,k,m)$ and $\\#\mathcal{S}(n,k,m)$ introduced in the
previous section. Given an integer $n\geq 1$, let $L_{n}\subset\mathbb{R}^{k}$
be the lattice consisting of all vectors of the form
$(\frac{a_{1}}{n},\dots,\frac{a_{k}}{n})$, where
$(a_{1},\dots,a_{k})\in\mathbb{Z}^{k}$. Let $L_{n}^{\prime}$ be the subset of
$L_{n}$ consisting of such vectors $(\frac{a_{1}}{n},\dots,\frac{a_{k}}{n})$
for which the coordinates are all mutually distinct. Set
$\Omega_{n}\mathrel{\mathop{\mathchar 58\relax}}=B_{k}\cap L_{n}$,
$\Omega_{n}(I)\mathrel{\mathop{\mathchar 58\relax}}=B_{k}(I)\cap L_{n}$,
$\Omega_{n}^{\prime}\mathrel{\mathop{\mathchar 58\relax}}=B_{k}\cap
L_{n}^{\prime}$ and $\Omega_{n}^{\prime}(I)\mathrel{\mathop{\mathchar
58\relax}}=B_{k}(I)\cap L_{n}^{\prime}$ and let
$\kappa\mathrel{\mathop{\mathchar 58\relax}}\mathbb{R}\rightarrow[0,1/2]$ be
the function defined as follows

(4.1) $\kappa(x)\mathrel{\mathop{\mathchar
58\relax}}=\begin{cases}\\{x\\}&\text{ if }\\{x\\}\leq 1/2;\\\
1-\\{x\\}&\text{ if }\\{x\\}>1/2.\end{cases}$

Here, $\\{x\\}$ denotes the fractional part of $x$. We note that
$\operatorname{cos}(2\pi x)=\operatorname{cos}\left(2\pi\kappa(x)\right)$. For
a pair $\gamma=(G,S)$, such that $G=C_{n}$ and $S$ a subset of $G$ with
$S=S^{-1}$, we recall from the previous section that
$S\backslash\\{0\\}=T\cup(-T)$, where $T=\\{a_{1},\dots,a_{k}\\}$, and
$\vec{a}=(a_{1},\dots,a_{k})\in A_{k}(n)$. Let $\sigma$ be a permutation of
$\\{1,\dots,k\\}$ and $m\in[1,n-1]_{\mathbb{Z}}$. Write $m=dm_{1}$,
$n=dn_{1}$, where $d\mathrel{\mathop{\mathchar 58\relax}}=(m,n)$. Consider a
point $(\vec{a},m)\in\mathcal{S}(n,k,m)$. Associate to this point and to the
permutation $\sigma$, the point

(4.2) $\begin{split}P(\vec{a},\sigma,m,n)\mathrel{\mathop{\mathchar
58\relax}}=&\left(\kappa\left(\frac{ma_{\sigma(1)}}{n}\right),\kappa\left(\frac{ma_{\sigma(2)}}{n}\right),\dots,\kappa\left(\frac{ma_{\sigma(k)}}{n}\right)\right),\\\
=&\left(\kappa\left(\frac{m_{1}a_{\sigma(1)}}{n_{1}}\right),\kappa\left(\frac{m_{1}a_{\sigma(2)}}{n_{1}}\right),\dots,\kappa\left(\frac{m_{1}a_{\sigma(k)}}{n_{1}}\right)\right).\end{split}$

It is clear that $P(\vec{a},\sigma,m,n)$ is contained in $\Omega_{n_{1}}$.

For ease of notation, identify the $m$-slice $\mathcal{S}(n,k,m)$ with
$A_{k}(n)$, by identifying $\vec{a}$ with $(\vec{a},m)$. For
$m\in[0,n-1]_{\mathbb{Z}}$, it conveniences us to further subdivide
$\mathcal{S}(n,k,m)$ into two disjoint subsets $\mathcal{S}^{\prime}(n,k,m)$
and $\mathcal{S}^{\prime\prime}(n,k,m)$ as follows. Set
$\mathcal{S}^{\prime}(n,k,0)\mathrel{\mathop{\mathchar 58\relax}}=\emptyset$
and $\mathcal{S}^{\prime\prime}(n,k,0)\mathrel{\mathop{\mathchar
58\relax}}=\mathcal{S}(n,k,0)$. For $m\in[1,n-1]_{\mathbb{Z}}$, let
$\mathcal{S}^{\prime}(n,k,m)$ consist of all $\vec{a}\in A_{k}(n)$ such that
for $i<j$,

$a_{i}\not\equiv\pm a_{j}\mod{n_{1}},$

and set $\mathcal{S}^{\prime\prime}(n,k,m)$ to be the complement
$\mathcal{S}(n,k,m)\backslash\mathcal{S}^{\prime}(n,k,m)$. We shall set
$\mathcal{S}^{\prime}(n,k)$ (resp. $\mathcal{S}^{\prime\prime}(n,k)$) to
denote the disjoint union of slices $\mathcal{S}^{\prime}(n,k,m)$ (resp.
$\mathcal{S}^{\prime\prime}(n,k,m)$) as $m$ ranges through
$[0,n-1]_{\mathbb{Z}}$. It shall turn out that the slices
$\mathcal{S}^{\prime}(n,k,m)$ are better suited to combinatorial arguments
than $\mathcal{S}(n,k,m)$. Lemma 4.2 will show that when $k$ is fixed,
$\\#\mathcal{S}^{\prime\prime}(n,k)$ is small in comparison to
$\\#\mathcal{S}(n,k)$, as $n$ goes to $\infty$. Given an interval
$I\subseteq[-k,k]$, we set $\mathcal{S}_{I}^{\prime}(n,k,m)$ (resp.
$\mathcal{S}_{I}^{\prime\prime}(n,k,m)$) to be the subset of
$\mathcal{S}^{\prime}(n,k,m)$ (resp. $\mathcal{S}^{\prime\prime}(n,k,m)$) for
which $\tau_{m}(\vec{a})\in I$.

######  Lemma 4.1.

There is a constant $C_{k}>0$ (depending on $k$), independent of $m$ and $n$
such that

$\\#\mathcal{S}^{\prime\prime}(n,k,m)<\frac{C_{k}n^{k}}{n_{1}}.$

The constant $C_{k}$ can be taken to be a polynomial in $k$.

###### Proof.

Given a pair $\tau=(i,j)$ such that $i<j$, let
$\mathcal{S}^{\prime\prime}_{\tau}(n,k,m)$ be the subset of
$\mathcal{S}^{\prime\prime}(n,k,m)$ such that

$a_{i}\equiv\pm a_{j}\mod{n_{1}}.$

The total number of subsets $\\{a_{1},\dots,a_{j-1},a_{j+1},\dots,a_{k}\\}$ is
at most $\binom{\left(\frac{n-1}{2}\right)}{k-1}$. Given one such choice,

$\begin{split}a_{j}\in&\\{a_{i}+rn_{1}\mid-\lfloor n/n_{1}\rfloor-1\leq
r\leq\lfloor n/n_{1}\rfloor+1\\}\\\ \cup&\\{-a_{i}+rn_{1}\mid-\lfloor
n/n_{1}\rfloor-1\leq r\leq\lfloor n/n_{1}\rfloor+1\\}.\end{split}$

Therefore, we find that

$\\#\mathcal{S}^{\prime\prime}_{\tau}(n,k,m)\leq 4\left(\lfloor
n/n_{1}\rfloor+1\right)\binom{\left(\frac{n-1}{2}\right)}{k-1}.$

Thus, we have that

$\\#\mathcal{S}^{\prime\prime}(n,k,m)\leq 4\binom{k}{2}\left(\lfloor
n/n_{1}\rfloor+1\right)\binom{\left(\frac{n-1}{2}\right)}{k-1}<\frac{C_{k}n^{k}}{n_{1}}.$

∎

Given $n\in\mathbb{Z}_{\geq 1}$, let $d(n)$ denote the number of divisors of
$n$. Note that for any $\epsilon>0$, $d(n)=O(n^{\epsilon})$. Given non-
negative functions $f$, $g$ and $h$, we write

$f=g+O_{k}(h)$

if there is a constant $C_{k}>0$ which depends only on $k$ such that

$|f-g|\leq C_{k}h.$

######  Lemma 4.2.

There is a constant $C_{k}>0$, independent of $n$, and depending on $k$, such
that

$\\#\mathcal{S}^{\prime\prime}(n,k)<C_{k}n^{k}\left(\sum_{d|n}\frac{\varphi(d)}{d}\right)<C_{k}d(n)n^{k},$

where $d(n)$ is the number of divisors of $n$. As a result, we find that for
any $\epsilon>0$,

$\\#\mathcal{S}^{\prime\prime}(n,k)=O_{k}(n^{k+\epsilon}),$

and that

$\frac{\\#\mathcal{S}^{\prime\prime}(n,k)}{\\#\mathcal{S}(n,k)}=O_{k}(n^{-1+\epsilon}).$

###### Proof.

Let $m\in[1,n-1]_{\mathbb{Z}}$, set $d=(m,n)$. Then, Lemma 4.1 implies that

$\\#\mathcal{S}^{\prime\prime}(n,k,m)<C_{k}\frac{n^{k}}{n_{1}}=C_{k}n^{k-1}d.$

We find that

$\begin{split}\\#\mathcal{S}^{\prime\prime}(n,k)&=\\#\mathcal{S}^{\prime\prime}(n,k,0)+\sum_{m=1}^{n-1}\\#\mathcal{S}^{\prime\prime}(n,k,m),\\\
&=\\#\mathcal{S}^{\prime\prime}(n,k,0)+\sum_{d|n}\sum_{(m,n)=d}\\#\mathcal{S}^{\prime\prime}(n,k,m),\\\
&<n^{k}+C_{k}\sum_{d|n}n^{k-1}d\\#\\{m\in[1,n-1]_{\mathbb{Z}}\mid(m,n)=d\\},\\\
&=n^{k}+C_{k}\sum_{d|n}n^{k-1}d\varphi\left(\frac{n}{d}\right),\\\
&=n^{k}+C_{k}n^{k}\left(\sum_{d|n}\frac{\varphi(d)}{d}\right).\\\ \end{split}$

Replace $C_{k}$ above with $(C_{k}+1)$ to obtain the result. ∎

######  Remark 4.3.

The function $g(n)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{d|n}\varphi(d)\left(\frac{n}{d}\right)$ is known as Pillai’s
arithmetical function [Pil33]. Set $\omega(n)$ to denote the number of prime
divisors of $n$. We note that a bound of

$g(n)\leq 27n\left(\frac{\log n}{\omega(n)}\right)^{\omega(n)}$

is explicitly proven by Broughan [Bro01, Theorem 3.1].

######  Lemma 4.4.

Let $\sigma\in S_{k}$, $m\in[1,n-1]_{\mathbb{Z}}$, and
$\vec{a}\in\mathcal{S}^{\prime}(n,k,m)$. Let $I$ be an interval contained in
$[-k,k]$. Then, the point $P(\vec{a},\sigma,m,n)$ defined above lies in
$\Omega_{n_{1}}^{\prime}$. Furthermore, the following are equivalent

  1. (1)

$\tau_{m}(\vec{a})\in I$,

  2. (2)

$P(\vec{a},\sigma,m,n)\in\Omega_{n_{1}}^{\prime}(I)$.

###### Proof.

Suppose that

$\kappa\left(\frac{m_{1}a_{\sigma(i)}}{n_{1}}\right)=\kappa\left(\frac{m_{1}a_{\sigma(j)}}{n_{1}}\right),$

where we recall that $\kappa(x)$ is given by (4.1). Then,

$m_{1}a_{\sigma(i)}\equiv\pm m_{1}a_{\sigma(j)}\mod{n_{1}}.$

Since $m_{1}$ is coprime to $n_{1}$, we find that

$a_{\sigma(i)}\equiv\pm a_{\sigma(j)}\mod{n_{1}}.$

However, since $\vec{a}\in\mathcal{S}^{\prime}(n,k,m)$,

$a_{\sigma(i)}\not\equiv\pm a_{\sigma(j)}\mod{n_{1}}$

unless $i=j$. This proves that all the coordinates of the point
$P(\vec{a},\sigma,m,n)$ are distinct. Furthermore, all coordinates are of the
form $b_{i}/n_{1}$, where $b_{i}$ is an integer, and these numbers lie in the
range $[0,1/2]$. Therefore, the point $P(\vec{a},\sigma,m,n)$ is contained in
$\Omega_{n_{1}}^{\prime}$.

Write $P(\vec{a},\sigma,m,n)=(y_{1},\dots,y_{k})$, where,
$y_{i}=\kappa\left(\frac{ma_{\sigma(i)}}{n}\right)$. Recall that $B_{k}(I)$
consists of all tuples $(x_{1},\dots,x_{k})\in B_{k}$ such that
$\sum_{i=1}^{k}\operatorname{cos}(2\pi x_{i})\in I$. The point
$(y_{1},\dots,y_{k})\in\Omega_{n_{1}}^{\prime}$ lies in
$\Omega_{n_{1}}^{\prime}(I)$ if and only if
$\sum_{i=1}^{k}\operatorname{cos}(2\pi y_{i})\in I$. Observe that

$\begin{split}&\sum_{i=1}^{k}\operatorname{cos}(2\pi y_{i})\\\
=&\sum_{i=1}^{k}\operatorname{cos}\left(2\pi\kappa\left(\frac{m_{1}a_{\sigma(i)}}{n_{1}}\right)\right)\\\
=&\sum_{i=1}^{k}\operatorname{cos}\left(\frac{2\pi
m_{1}a_{\sigma(i)}}{n_{1}}\right)\\\
=&\sum_{i=1}^{k}\operatorname{cos}\left(\frac{2\pi
m_{1}a_{i}}{n_{1}}\right)=\tau_{m}(\vec{a}).\\\ \end{split}$

This means that the conditions are equivalent. ∎

######  Lemma 4.5.

With respect to notation above,

$\begin{split}&\\#\mathcal{S}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\\#\mathcal{S}^{\prime}(n_{1},k,m_{1}),\\\
&\\#\mathcal{S}_{I}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\\#\mathcal{S}_{I}^{\prime}(n_{1},k,m_{1}).\\\
\end{split}$

###### Proof.

Given a tuple $(a_{1},\dots,a_{k})\in\mathcal{S}^{\prime}(n_{1},k,m_{1})$ and
$(a_{1}^{\prime},\dots,a_{k}^{\prime})\in\left[0,\left(\frac{(n,m)-1}{2}\right)\right]^{k}$,
set $(b_{1},\dots,b_{k})$ be given by $b_{i}\mathrel{\mathop{\mathchar
58\relax}}=a_{i}+a_{i}^{\prime}m_{1}$. Note that since
$a_{i}\in[1,\frac{m_{1}-1}{2}]$,

$b_{i}<\left(\frac{m_{1}-1}{2}\right)+\left(\frac{(n,m)-1}{2}\right)m_{1}=\frac{m-1}{2}.$

Let $(c_{1},\dots,c_{k})$ be the permutation of the coordinates of
$(b_{1},\dots,b_{k})$ such that $1\leq
c_{1}<c_{2}<\dots<c_{k}\leq\frac{m-1}{2}$. Note that $a_{i}\not\equiv\pm
a_{j}\mod{m_{1}}$ for $i\neq j$, and therefore, $c_{i}\not\equiv\pm
c_{j}\mod{m_{1}}$ for $i\neq j$. This implies that
$(c_{1},\dots,c_{k})\in\mathcal{S}^{\prime}(n,k,m)$. The association

$\left((a_{1},\dots,a_{k}),(a_{1}^{\prime},\dots,a_{k}^{\prime})\right)\mapsto(c_{1},\dots,c_{k})$

sets up a bijection

$\mathcal{S}^{\prime}(n_{1},k,m_{1})\times\left[0,\left(\frac{(n,m)-1}{2}\right)\right]^{k}\rightarrow\mathcal{S}^{\prime}(n,k,m),$

which restricts to a bijection

$\mathcal{S}_{I}^{\prime}(n_{1},k,m_{1})\times\left[0,\left(\frac{(n,m)-1}{2}\right)\right]^{k}\rightarrow\mathcal{S}_{I}^{\prime}(n,k,m).$

Therefore, we conclude that

$\begin{split}&\\#\mathcal{S}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\\#\mathcal{S}^{\prime}(n_{1},k,m_{1}),\\\
&\\#\mathcal{S}_{I}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\\#\mathcal{S}_{I}^{\prime}(n_{1},k,m_{1}).\end{split}$

∎

######  Proposition 4.6.

For $m\in[1,n-1]_{\mathbb{Z}}$, and $I\subseteq[-k,k]$ be a subset. Then the
following assertions hold.

  1. (1)

There is a surjection

$\Phi\mathrel{\mathop{\mathchar
58\relax}}\Omega_{n_{1}}^{\prime}\rightarrow\mathcal{S}^{\prime}(n_{1},k,m_{1})$

whose fibres all have cardinality $k!$.

  2. (2)

The map $\Phi$ restricts to a map

$\Phi_{I}\mathrel{\mathop{\mathchar
58\relax}}\Omega_{n_{1}}^{\prime}(I)\rightarrow\mathcal{S}_{I}^{\prime}(n_{1},k,m_{1}),$

whose fibers also have cardinality $k!$.

###### Proof.

We set $d\mathrel{\mathop{\mathchar 58\relax}}=(m,n)$,
$m_{1}\mathrel{\mathop{\mathchar 58\relax}}=m/d$ and
$n_{1}\mathrel{\mathop{\mathchar 58\relax}}=n/d$. Consider a point
$x=(x_{1},\dots,x_{k})\in\Omega_{n_{1}}^{\prime}$. By definition, there exist
distinct integers $b_{i}\in[0,\frac{n_{1}-1}{2}]$ such that
$x_{i}=b_{i}/n_{1}$. Let $c_{i}\in[0,n_{1}-1]$ be such that $m_{1}c_{i}\equiv
b_{i}\mod{n_{1}}$ for all $i$. Then, set

$a_{i}^{\prime}=\begin{cases}c_{i}&\text{ if }c_{i}\in[0,\frac{n_{1}-1}{2}]\\\
(n_{1}-c_{i})&\text{ if }c_{i}\in[\frac{n_{1}+1}{2},n_{1}-1].\end{cases}$

Note that $a_{i}^{\prime}\in[0,\frac{n_{1}-1}{2}]$ and that
$\kappa\left(\frac{m_{1}a_{i}^{\prime}}{n_{1}}\right)=\frac{m_{1}c_{i}}{n_{1}}=\frac{b_{i}}{n_{1}}$.
There is a tuple
$\vec{a}=(a_{1},\dots,a_{k})\in\mathcal{S}^{\prime}(n_{1},k,m_{1})$ and a
permutation $\sigma\in S_{k}$ such that
$(a_{\sigma(1)},\dots,a_{\sigma(k)})=(a_{1}^{\prime},\dots,a_{k}^{\prime})$.
Thus, there is a unique permutation $\sigma$ such that

$(x_{1},\dots,x_{k})=\left(\kappa\left(\frac{m_{1}a_{\sigma(1)}}{n_{1}}\right),\dots,\kappa\left(\frac{m_{1}a_{\sigma(i)}}{n_{1}}\right),\dots,\kappa\left(\frac{m_{1}a_{\sigma(k)}}{n_{1}}\right)\right).$

We map the tuple $(x_{1},\dots,x_{k})$ to $(a_{1},\dots,a_{k})$. Consider the
action of $S_{k}$ on $\Omega_{n_{1}}^{\prime}$ via permutation of coordinates.
The fibres of this map have cardinality $k!=\\#S_{k}$. That
$\Phi^{-1}(\mathcal{S}_{I}^{\prime}(n_{1},k,m_{1}))=\Omega_{n_{1}}^{\prime}(I)$
is easy to see, and the second assertion follows. ∎

######  Lemma 4.7.

Let $m\in[1,n-1]_{\mathbb{Z}}$ and $I$ be an interval contained in $[-k,k]$.
Then we have that

$\begin{split}&\\#\mathcal{S}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}^{\prime}}{k!},\\\
&\\#\mathcal{S}^{\prime}_{I}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}^{\prime}(I)}{k!}.\end{split}$

###### Proof.

Lemma 4.5 asserts that the following relations hold

$\begin{split}&\\#\mathcal{S}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\\#\mathcal{S}^{\prime}(n_{1},k,m_{1}),\\\
&\\#\mathcal{S}_{I}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\\#\mathcal{S}_{I}^{\prime}(n_{1},k,m_{1}).\\\
\end{split}$

By Proposition 4.6, we have that

$\begin{split}&\\#\mathcal{S}^{\prime}(n_{1},k,m_{1})=\frac{\\#\Omega_{n_{1}}}{k!},\\\
&\\#\mathcal{S}_{I}^{\prime}(n_{1},k,m_{1})=\frac{\\#\Omega_{n_{1}}(I)}{k!},\end{split}$

and combining the above relations, the result follows. ∎

######  Corollary 4.8.

Let $m\in[1,n-1]$, we have that

$\begin{split}&\\#\mathcal{S}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}}{k!}+O_{k}((n,m)n^{k-1}),\\\
&\\#\mathcal{S}^{\prime}_{I}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}(I)}{k!}+O_{k}((n,m)n^{k-1}).\end{split}$

###### Proof.

Let $\Omega_{n_{1}}^{\prime\prime}\mathrel{\mathop{\mathchar
58\relax}}=\Omega_{n_{1}}\backslash\Omega_{n_{1}}^{\prime}$ and
$\Omega_{n_{1}}^{\prime\prime}(I)\mathrel{\mathop{\mathchar
58\relax}}=\Omega_{n_{1}}(I)\backslash\Omega_{n_{1}}^{\prime}(I)$. The set
$\Omega_{n_{1}}^{\prime\prime}$ consists of all tuples
$\left(x_{1},\dots,x_{k}\right)$ such that for some $i<j$, $x_{i}=x_{j}$.
Clearly, the cardinality of this set can be bounded as follows

$\\#\Omega_{n_{1}}^{\prime\prime}\leq\binom{k}{2}\left(\frac{n_{1}-1}{2}\right)^{k-1}.$

It follows from Lemma 4.7 that

$\begin{split}&\\#\mathcal{S}^{\prime}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}}{k!}-\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}^{\prime\prime}}{k!},\\\
&\\#\mathcal{S}^{\prime}_{I}(n,k,m)=\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}(I)}{k!}-\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}^{\prime\prime}(I)}{k!}.\end{split}$

Therefore, the error term can be bounded as follows

$\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}^{\prime\prime}}{k!}\leq\frac{1}{k!}\binom{k}{2}\left(\frac{n_{1}-1}{2}\right)^{k-1}\left(\frac{(n,m)+1}{2}\right)^{k}=O_{k}((n,m)n^{k-1}),$

and the result follows. ∎

##  5\. Proof of the main theorem

In the previous section, we obtained a geometric interpretation for the
quantities $\\#\mathcal{S}^{\prime}(n,k,m)$ and
$\\#\mathcal{S}^{\prime}_{I}(n,k,m)$, in terms of the quantities
$\\#\Omega_{n_{1}}^{\prime}$ and $\\#\Omega_{n_{1}}^{\prime}(I)$ respectively.
In order to effectively bound $\\#\Omega_{n}^{\prime}(I)$, it suffices bound
$\\#\Omega_{n}(I)$.

######  Lemma 5.1.

Suppose that $I=[c,d]$ is an interval contained in $[-k,k]$, and suppose that
$(\frac{a_{1}}{n},\dots,\frac{a_{k}}{n})\in B_{k}(I)$. Then,
$(\frac{a_{1}+1}{n},\frac{a_{2}+1}{n},\dots,\frac{a_{k}+1}{n})\in
B_{k}\left(\left[c-\frac{2\pi k}{n},d+\frac{2\pi k}{n}\right]\right)$.

###### Proof.

It suffices to prove that

$\sum_{i=1}^{k}\cos\left(\frac{2\pi
a_{i}}{n}\right)\in[c,d]\Longrightarrow\sum_{i=1}^{k}\cos\left(\frac{2\pi(a_{i}+1)}{n}\right)\in\left[c-\frac{2\pi
k}{n},d+\frac{2\pi k}{n}\right].$

To see the above, notice that for $0\leq x\leq\pi$ and $\epsilon>0$ such that
$x+\epsilon\leq\pi$, it follows from the mean value theorem that

$\operatorname{cos}(x)-\epsilon\leq\cos(x+\epsilon)\leq\operatorname{cos}(x)+\epsilon.$

∎

######  Proposition 5.2.

Let $I=[c,d]$ be an interval contained in $[-k,k]$. With respect to notation
above,

$\\#\Omega_{n}(I)=n^{k}\operatorname{Vol}(B_{k}(I))+O_{k}(n^{k-1}).$

###### Proof.

For a given element $(\frac{a_{1}}{n},\dots,\frac{a_{n}}{n})\in\Omega_{n}(I)$,
let $\mathcal{B}_{(a_{1},\dots,a_{k})}$ denote the box

$\mathcal{B}_{(a_{1},\dots,a_{k})}=\left\\{(x_{1},\dots,x_{k})\left|\frac{a_{j}}{n}\leq
x_{j}\leq\frac{a_{j}+1}{n}\right.\right\\}.$

It is clear that
$\operatorname{Vol}(\mathcal{B}_{(a_{1},\dots,a_{k})})=\frac{1}{n^{k}}$. Now
we consider the set $U_{k,n}$ which is the union of
$\mathcal{B}_{(a_{1},\dots,a_{k})}$, where
$(\frac{a_{1}}{n},\dots,\frac{a_{n}}{n})\in\Omega_{n}(I)$. This is a set
containing $B_{k}(I)$. We have

$\operatorname{Vol}(B_{k}(I))\leq\frac{\\#\Omega_{n}(I)}{n^{k}}=\operatorname{Vol}(U_{k,n}).$

From Lemma 5.1, it follows that

$U_{k,n}\subseteq B_{k}\left(\left[c-\frac{2\pi k}{n},d+\frac{2\pi
k}{n}\right]\right).$

Thus we conclude that

$\begin{split}n^{k}\operatorname{Vol}(B_{k}(I))&\leq\\#\Omega_{n}(I)\\\ &\leq
n^{k}\operatorname{Vol}\left(B_{k}\left(\left[c-\frac{2\pi k}{n},d+\frac{2\pi
k}{n}\right]\right)\right)\\\ &=n^{k}\operatorname{Vol}(B_{k}(I))\\\
+&n^{k}\operatorname{Vol}\left(B_{k}\left(\left[c-\frac{2\pi
k}{n},c\right]\right)\right)+n^{k}\operatorname{Vol}\left(B_{k}\left(\left[d,d+\frac{2\pi
k}{n}\right]\right)\right).\end{split}.$

To estimate the error term, it suffices to bound

$\left(\frac{n}{2}\right)^{k}\int^{c}_{c-\frac{2\pi
k}{n}}\delta^{(k)}(u)du\text{ and
}\left(\frac{n}{2}\right)^{k}\int^{d+\frac{2\pi k}{n}}_{d}\delta^{(k)}(u)du.$

Note that the support of $\delta$ is contained in $[-1,1]$, and hence the
support of $\delta^{(k)}$ is contained in $[-k,k]$. Therefore, if $c=-k$,
then, $\int^{c}_{c-\frac{2\pi k}{n}}\delta^{(k)}(u)du=0$. Without loss of
generality, assume that $c\in(-k,k)$, and let $c^{\prime}\in(-k,c)$. Set
$M\mathrel{\mathop{\mathchar
58\relax}}=\operatorname{sup}\\{|\delta^{(k)}(u)|\mid u\in[c^{\prime},c]\\}$.
Note that for $n>\frac{2\pi k}{(c-c^{\prime})}$,

$\int^{c}_{c-\frac{2\pi k}{n}}\delta^{(k)}(u)du\leq\frac{2\pi kM}{n}.$

Therefore, we have shown that

$\left(\frac{n}{2}\right)^{k}\int^{c}_{c-\frac{2\pi
k}{n}}\delta^{(k)}(u)du=O_{k}(n^{k-1}).$

The same reasoning shows that

$\left(\frac{n}{2}\right)^{k}\int^{d+\frac{2\pi
k}{n}}_{d}\delta^{(k)}(u)du=O_{k}(n^{k-1}).$

Therefore, we have shown that

$\\#\Omega_{n}(I)=n^{k}\operatorname{Vol}(B_{k}(I))+O_{k}\left(n^{k-1}\right).$

∎

######  Proposition 5.3.

With respect to notation above,

$\\#\mathcal{S}^{\prime}_{I}(n,k,m)=\\#\mathcal{S}^{\prime}(n,k,m)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}((n,m)n^{k-1}).$

###### Proof.

We have

$\begin{split}\\#\mathcal{S}^{\prime}_{I}(n,k,m)=&\left(\frac{(n,m)+1}{2}\right)^{k}\frac{\\#\Omega_{n_{1}}(I)}{k!}+O_{k}((n,m)n^{k-1}),\\\
=&\left(\frac{(n,m)+1}{2}\right)^{k}\frac{n_{1}^{k}}{k!}\operatorname{Vol}(B_{k}(I))+O_{k}((n,m)n^{k-1})\\\
=&\left(\frac{(n,m)+1}{2}\right)^{k}\\#\Omega_{n_{1}}\frac{2^{k}}{k!}\operatorname{Vol}(B_{k}(I))+O_{k}((n,m)n^{k-1})\\\
=&\\#\mathcal{S}^{\prime}(n,k,m)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}((n,m)n^{k-1}).\end{split}$

For the above set of inequalities, we use Corollary 4.8 and Proposition 5.2. ∎

######  Proposition 5.4.

With respect to notation above,

$\\#\mathcal{S}^{\prime}_{I}(n,k)=\\#\mathcal{S}^{\prime}(n,k)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}(n^{k+\epsilon}).$

###### Proof.

Note that $\mathcal{S}^{\prime}(n,k,0)$ is empty. By an argument similar to
the one employed in Lemma 4.2,

$\begin{split}\\#\mathcal{S}_{I}^{\prime}(n,k)&=\sum_{m=1}^{n-1}\\#\mathcal{S}_{I}^{\prime}(n,k,m),\\\
&=\sum_{m=1}^{n-1}\\#\mathcal{S}^{\prime}(n,k,m)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}\left(n^{k-1}\sum_{m=1}^{n-1}(n,m)\right),\\\
&=\\#\mathcal{S}^{\prime}(n,k)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}\left(n^{k-1}\sum_{d|n}d\varphi\left(\frac{n}{d}\right)\right),\\\
&=\\#\mathcal{S}^{\prime}(n,k)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}(n^{k+\epsilon}),\end{split}$

where in the second line, we have applied Proposition 5.3. ∎

######  Theorem 5.5.

For $k\geq 1$ fixed, and $I=[c,d]\subseteq[-k,k]$,

$\operatorname{Prob}_{I}(n,k)=\int_{c}^{d}\delta^{(k)}(u)du+O_{k}(n^{-1+\epsilon}).$

###### Proof.

Recall from (3.4) that

$\operatorname{Prob}_{I}(n,k)=\frac{1}{n}\sum_{m=0}^{n-1}\operatorname{Prob}_{I}(n,k,m),$

where

$\operatorname{Prob}_{I}(n,k,m)=\frac{\\#\mathcal{S}_{I}(n,r,m)}{\\#\mathcal{S}(n,r,m)}=\frac{\\#\mathcal{S}_{I}(n,k,m)}{\binom{\frac{n-1}{2}}{k}}.$

Note that
$\\#\mathcal{S}_{I}(n,k,m)=\\#\mathcal{S}_{I}^{\prime}(n,k,m)+\\#\mathcal{S}_{I}^{\prime\prime}(n,k,m)$,
and therefore,

$\begin{split}\operatorname{Prob}_{I}(n,k)=&\frac{1}{n}\sum_{m=0}^{n-1}\operatorname{Prob}_{I}(n,k,m)\\\
=&\frac{1}{n}\sum_{m=0}^{n-1}\frac{\mathcal{S}_{I}^{\prime}(n,k,m)}{\binom{\frac{n-1}{2}}{k}}+\frac{\mathcal{S}_{I}^{\prime\prime}(n,k)}{n\binom{\frac{n-1}{2}}{k}}.\\\
\end{split}$

By Lemma 4.2, we find that

$\mathcal{S}_{I}^{\prime\prime}(n,k)\leq\mathcal{S}^{\prime\prime}(n,k)=O_{k}(d(n)n^{k})=O_{k}(n^{k+\epsilon}),$

and therefore,

$\begin{split}\operatorname{Prob}_{I}(n,k)=&\frac{1}{n}\frac{\mathcal{S}_{I}^{\prime}(n,k)}{\binom{\frac{n-1}{2}}{k}}+O_{k}(n^{-1+\epsilon}).\end{split}$

By Proposition 5.4,

$\begin{split}\\#\mathcal{S}^{\prime}_{I}(n,k)=&\\#\mathcal{S}^{\prime}(n,k)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}(n^{k+\epsilon}),\\\
=&\\#\mathcal{S}(n,k)2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}(n^{k+\epsilon}),\\\
=&n\binom{\frac{n-1}{2}}{k}2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}(n^{k+\epsilon}).\\\
\end{split}$

Therefore,

$\begin{split}\operatorname{Prob}_{I}(n,k)=&2^{k}\operatorname{Vol}(B_{k}(I))+O_{k}(n^{-1+\epsilon}),\\\
=&\int_{c}^{d}\delta^{(k)}(u)du+O_{k}(n^{-1+\epsilon}).\end{split}$

This completes the proof. ∎

###### Proof of Theorem 1.1.

It follows from (3.3) that

$\operatorname{Prob}_{I}(n,k)=\frac{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n,\alpha\in J\\}}{\\#\\{(X,\alpha)\mid
X\in\mathcal{F}_{r},\alpha\in\operatorname{Sp}(X),\text{ such that
}h(X)=n\\}}.$

By theorem 5.5,

$\operatorname{Prob}_{I}(n,k)=\int_{c}^{d}\delta^{(k)}(u)du+O_{k}(n^{-1+\epsilon}),$

which proves the result. ∎

## References

  * [Bas92] Hyman Bass.  The Ihara-Selberg zeta function of a tree lattice.  Internat. J. Math., 3(6):717–797, 1992.
  * [BN09] Matthew Baker and Serguei Norine.  Harmonic morphisms and hyperelliptic graphs.  Int. Math. Res. Not. IMRN, (15):2914–2955, 2009.
  * [Bro01] Kevin A. Broughan.  The gcd-sum function.  J. Integer Seq., 4(2):Article 01.2.2, 19, 2001.
  * [CKL+15] Julien Clancy, Nathan Kaplan, Timothy Leake, Sam Payne, and Melanie Matchett Wood.  On a Cohen-Lenstra heuristic for Jacobians of random graphs.  J. Algebraic Combin., 42(3):701–723, 2015.
  * [DRLV22] Cédric Dion, Anwesh Ray, Antonio Lei, and Daniel Vallières.  On the distribution of Iwasawa invariants associated to multigraphs.  Preprint, arXiv:2207.07213, 2022.
  * [Iha66a] Yasutaka Ihara.  On discrete subgroups of the two by two projective linear group over $\mathfrak{p}$-adic fields.  J. Math. Soc. Japan, 18:219–235, 1966.
  * [Iha66b] Yasutaka Ihara.  On discrete subgroups of the two by two projective linear group over $\wp$-adic fields.  J. Math. Soc. Japan, 18:219–235, 1966.
  * [JMRR99] Dmitry Jakobson, Stephen D. Miller, Igor Rivin, and Zeév Rudnick.  Eigenvalue spacings for regular graphs.  In Emerging applications of number theory (Minneapolis, MN, 1996), volume 109 of IMA Vol. Math. Appl., pages 317–327. Springer, New York, 1999.
  * [New05] Derek B. Newland.  Kernels in the Selberg trace formula on the k-regular tree and zeros of the Ihara zeta function.  ProQuest LLC, Ann Arbor, MI, 2005.  Thesis (Ph.D.)–University of California, San Diego.
  * [Pil33] S. S. Pillai.  On an arithmetic function.  J. Annamalai Univ., 2:243–248, 1933.
  * [Sun86] Toshikazu Sunada.  $L$-functions in geometry and some applications.  In Curvature and topology of Riemannian manifolds (Katata, 1985), volume 1201 of Lecture Notes in Math., pages 266–284. Springer, Berlin, 1986.
  * [Sun13] Toshikazu Sunada.  Topological crystallography, volume 6 of Surveys and Tutorials in the Applied Mathematical Sciences.  Springer, Tokyo, 2013.  With a view towards discrete geometric analysis.
  * [Ter11] Audrey Terras.  Zeta functions of graphs, volume 128 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, 2011.  A stroll through the garden.
  * [Val94] Alain Valette.  Can one hear the shape of a group?  Rend. Sem. Mat. Fis. Milano, 64:31–44 (1996), 1994.
  * [Woo17] Melanie Matchett Wood.  The distribution of sandpile groups of random graphs.  J. Amer. Math. Soc., 30(4):915–958, 2017.


# Attempting perfect hypergraphs

Maria Chudnovsky
Princeton University, Princeton, NJ 08544, USA

and Gil Kalai
Reichman University, Herzliya 4610101, Israel
and The Hebrew University of Jerusalem, Jerusalem 91904, Israel This material
is based upon work supported in part by the U. S. Army Research Office under
grant number W911NF-16-1-0404, and supported by NSF grant DMS 1763817 and ERC
advanced grant 320924.Supported by ERC advanced grant 320924 and by ISF Grant
1612/17 .

(June 7, 2020; revised )

###### Abstract

We study several extensions of the notion of perfect graphs to $k$-uniform
hypergraphs. One main definition extends to hypergraphs the notion of perfect
graphs based on coloring. Let $G$ be a $k$-uniform hypergraph. A coloring of a
$k$-uniform hypergraph $G$ is proper if it is a coloring of the $(k-1)$-tuples
with elements in $V(G)$ in such a way that no edge of $G$ is a monochromatic
$K_{k}^{k-1}$.

A $k$-uniform hypergraph $G$ is $C_{\omega}$-perfect if for every induced
subhypergraph $G^{\prime}$ of $G$ we have:

  * •

if $X\subseteq V(G^{\prime})$ with $|X|<k-1$, then there is a proper
$(\omega(G^{\prime})-k+2)$-coloring of $G^{\prime}$ (so $(k-1)$-tuples are
colored) that restricts to a proper $(\omega(G^{\prime})-k+2)$-coloring of
$lk_{G^{\prime}}(X)$ (so $(k-|X|-1)$-tuples are colored).

Another main definition is the following: A $k$-uniform hypergraph $G$ is
hereditary perfect (or, briefly, $H$-perfect) if all links of sets of $(k-2)$
vertices are perfect graphs.

The notion of $C_{\omega}$ perfectness is not closed under complementation
(for $k>2$) and we define $G$ to be doubly perfect if both $G$ and its
complement are $C_{\omega}$ perfect. We study doubly-perfect hypergraphs: In
addition to perfect graphs nontrivial doubly-perfect graphs consist of a
restricted interesting class of 3-uniform hypergraphs, and within this class
we give a complete characterization of doubly-perfect $H$-perfect hypergraphs.

##  1 Introduction

The purpose of this paper is to study some extensions of the notion of perfect
graphs to $k$-uniform hypergraphs, $k>2$. We start with basic notation and
terminology regarding hypergraphs followed by basic definitions and properties
of perfect graphs. Denote by $K^{p}_{q}$ the complete $p$-uniform hypergraph
on $q$ vertices. Let $G$ be a $k$-uniform hypergraph. The complement $G^{c}$
of $G$ is the $k$ uniform hypergraph such that a $k$-subset $X$ of $V(G)$ is a
hyperedge of $G^{c}$ if and only if $X$ is not a hyperedge of $G$. For
$X\subseteq V(G)$ we denote by $G[X]$ the $k$-uniform hypergraph induced by
$G$ on $X$, and by $lk_{G}(X)$ the $(k-|X|)$-uniform hypergraph with vertex
set $V(G)\setminus X$ and such that $Y\in E(G(X))$ if and only if $X\cup Y\in
E(G)$ (this is the link of $X$). Observe that $lk_{G}^{c}(X)=lk_{G^{c}}(X)$.
We denote by $\omega(G)$ the maximum size of $X\subseteq V(G)$ such that
$G[X]$ is a complete $k$-uniform hypergraph, and by $\alpha(G)$ the maximum
size of $X\subseteq V(G)$ such that $G^{c}[X]$ is a complete $k$-uniform
hypergraph.

Figure 1: Classes of perfect hypergraphs considered in this paper. The figure
describes (out of scale) the case of 3-uniform hypergraphs. For graphs all the
classes coincide with the class of perfect graphs. For $k$-uniform
hypergraphs, $k>3$ the class of doubly-perfect hypergraphs contains only the
empty hypergraph and complete hypergraph.

A graph $G$ is perfect if for every induced subgraph $H$ of $G$,
$\chi(H)=\omega(H)$. The Weak Perfect Graph Theorem [12] asserts that $G$ is
perfect iff its complement $G^{c}$ is perfect. The Strong Perfect Graph
Theorem [5] asserts that $G$ is perfect iff $G$ is a Berge graph, namely
neither $G$ nor $G^{c}$ contains an induced cycle of odd length greater than
3. The class of perfect graphs is a remarkable class of graphs with profound
connections in mathematics, theoretical computer science and optimization.
There is also a rich area of graph theory devoted to the study of graphs with
forbidden induced subgraphs, and perfect graphs play a central role in this
study.

Our purpose here is to propose several extensions of the notion of perfect
graphs to $k$-uniform hypergraphs, $k>2$. Our main definition extends to
hypergraphs the notion of perfect graphs based on coloring. Let $G$ be a
$k$-uniform hypergraph. A coloring of $G$ is proper if it is a coloring of the
$(k-1)$-tuples with elements in $V(G)$ in such a way that no edge of $G$ is a
monochromatic $K_{k}^{k-1}$.

A $k$-uniform hypergraph is $C_{\omega}$-perfect if for every induced
subhypergraph $G^{\prime}$ of $G$ we have:

  * •

if $X\subseteq V(G^{\prime})$ with $|X|<k-1$, then there is a proper
$(\omega(G^{\prime})-k+2)$-coloring of $G^{\prime}$ (so $(k-1)$-tuples are
colored) that restricts to a proper $(\omega(G^{\prime})-k+2)$-coloring of
$lk_{G^{\prime}}(X)$ (so $(k-|X|-1)$-tuples are colored).

In Section 2 we show that a weaker coloring property which resembles the Berge
property for graphs suffices for $C_{\omega}$-perfectness. Define next $G$ to
be $C_{\alpha}$-perfect if its complement $G^{C}$ is $C_{\omega}$-perfect.
Now, call $G$ doubly perfect if $G$ is both $C_{\omega}$-perfect and
$C_{\alpha}$-perfect. We study the class of doubly-perfect hypergraphs in
Section 4. A $k$-uniform hypergraph is clique friendly if every set of $k+1$
vertices contains either $k+1$ edges or at most two edges. It follows easily
from the definition that $C_{\omega}$-perfect hypergraphs are clique friendly
and this implies that if $G$ is a doubly-perfect hypergraph which is neither
complete nor empty, then $k\leq 3$. Moreover, for $k=3$ to be doubly perfect
$G$ must be a cocycle, namely every 4 vertices span an even number of edges.
An equivalent definition of cocycles which we rely on in Section 4 is the
following: for a graph $G$ we write $co(G)$ to be the 3-uniform hypergraph
whose edges correspond to triples of vertices of $G$ that span an odd number
of edges. Every 3-regular cocycle $C$ can be written as $co(G)$ for some graph
$G$.

A $k$-uniform hypergraph $G$ is $H$-perfect (or hereditary perfect) if the
link $lk_{G}(X)$ of every set $X$ of $k-2$ vertices is a perfect graph. A
$k$-uniform hypergraph is $H_{\omega}$-perfect if it is $H$-perfect and clique
friendly. In Section 2 we also prove that $H_{\omega}$-perfect hypergraphs are
$C_{\omega}$-perfect. (The converse is not true.) Examples of
$H_{\omega}$-perfect (hence also $C_{\omega}$-) hypergraphs include
$k$-partite hypergraphs, simple hypergraphs and hypergraphs of $k$-cliques of
perfect graphs. More examples are given in Section 3 where we also discuss
simple extremal problems for perfect hypergraphs. In Section 4 we also give a
full description of doubly-perfect hypergraphs which are also $H$-perfect.

Seeking hypergraph analogs of perfect graphs fits the ‘high-dimensional
combinatorics’ programme of Linial [10, 11]. Our concluding Section 5
discusses other related notions of perfectness and possible connections. We
note that a different notion of perfectness for hypergraphs was pioneered by
Voloshin [17, 18] and further studied by Bujtás and Tuza [4].

##  2 Perfect hypergraphs and proper colorings

###  2.1 Basic properties of $C_{\omega}$ perfect hypergraphs

######  2.1.

Let $G$ be a $C_{\omega}$-perfect $k$-uniform hypergraph with $V(G)=k+1$. Let
$X\subseteq V(G)$ with $|X|<k-1$, and suppose that $lk_{G}(X)$ is a clique.
Then $G$ is a clique. Consequently, every $C_{\omega}$-perfect hypergraph is
clique friendly.

###### Proof.

Suppose $G$ is not a clique, and so $\omega(G)=k$. Let $a,b,c\in V(G)\setminus
X$. Since $G$ is Berge, there exists a proper $2$-coloring of $G$ (so the
$k-1$-tuples are colored) that restricts to a proper $2$-coloring of the
complete graph with vertex set $\\{a,b,c\\}$ (so the vertices are colored), a
contradiction. This proves 2.1. ∎

######  2.2.

If $G$ is $C_{\omega}$-perfect then for every $X\subseteq V(G)$ with
$|X|<k-1$, $\omega(lk_{G}(X))\leq\omega(G)-|X|$.

###### Proof.

Induction on $|X|$. Let $K$ be a clique in $lk_{G}(X)$. Assume first that
$X=\\{x\\}$. By 2.1, $K\cup\\{x\\}$ is a clique of $G$, and so
$|K|\leq\omega(G)-1$.

Now let $x\in X$; write $X^{\prime}=X\setminus\\{x\\}$ and $H=lk_{G}(x)$. Then
$K$ is a clique in $lk_{H}(X^{\prime})$, and so inductively
$|K|\leq\omega(lk_{G}(x))-|X^{\prime}|=\omega(lk_{G}(x))-|X|+1$. But also, as
we have seen, $\omega(lk_{G}(x))\leq\omega(G)-1$, so $|K|\leq\omega(G)-|X|$,
This proves 2.2. ∎

######  2.3.

Let $G$ be a clique-friendly $k$-uniform hypergraph with $V(G)=k+1$. Let
$X\subseteq V(G)$ with $|X|<k-1$, and suppose that $lk_{G}(X)$ is a clique.
Then $G$ is a clique.

###### Proof.

Suppose $G$ is not a clique. Then $|E(G)|<k+1$. Since $lk_{G}(X)$ is a clique,
and $|V(G)|-|X|\geq 3$, we have that $|E(G)|\geq 3$, contrary to the fact that
$G$ is clique friendly. This proves 2.3. ∎

######  2.4.

If $G$ is clique friendly then for every $X\subseteq V(G)$ with $|X|<k-1$, and
every clique $K$ in $lk_{G}(X)$, we have that $K\cup X$ is a clique of $G$.
Consequently, $\omega(lk_{G}(X))\leq\omega(G)-|X|$.

###### Proof.

First we prove the first statement. Induction on $|X|$. Let $K$ be a clique in
$lk_{G}(X)$. Assume first that $X=\\{x\\}$. By 2.3, $K\cup\\{x\\}$ is a clique
of $G$, as required.

Now let $x\in X$; write $X^{\prime}=X\setminus\\{x\\}$. Then $K$ is a clique
in $lk_{G}(x)(X^{\prime})$, and so inductively $K\cup X^{\prime}$ is a clique
in $lk_{G}(x)$. But also, as we have seen in the base case of the induction,
$(K\cup X^{\prime})\cup\\{x\\}$ is a clique in $G$, as required. This proves
the first statement.

To prove the second statement, let $K$ be a clique in $lk_{G}(X)$ of size
$\omega(lk_{G}(X)$. We have proved that $K\cup X$ is a clique of $G$, and
consequently $\omega(G)\geq\omega(lk_{G}(X))+|X|$. Next let $K$ be a clique of
$G$ of size $\omega(G)$ and with $X\subseteq K$. Then $K\setminus X$ is a
clique of $lk_{G}(X)$, and therefore $\omega(lk_{G}(X)\geq\omega(G)-|X|$, and
the second statement follows. This proves 2.4. ∎

###  2.2 Berge is perfect

A $k$-uniform hypergraph is Berge if for every induced subhypergraph
$G^{\prime}$ of $G$ we have:

  * •

If $X\subseteq V(G^{\prime})$ with $|X|=k-2$, then there is a proper
$(\omega(G^{\prime})-k+2)$-coloring of $G^{\prime}$ (so $(k-1)$-tuples are
colored) that restricts to a proper $(\omega(G^{\prime})-k+2)$-coloring of
$lk_{G^{\prime}}(X)$ (so $(k-|X|-1)$-tuples are colored).

######  2.5.

A $k$-uniform hypergraph $G$ is Berge iff it is $C_{\omega}$-perfect.

###### Proof.

Clearly if $G$ is $C_{\omega}$-perfect, then $G$ is Berge. Thus we assume that
$G$ is Berge and show that $G$ is $C_{\omega}$-perfect. Since being Berge and
being $C_{\omega}$-perfect are both closed under taking induced
subhypergraphs, it is enough to prove that:

  * •

If $X\subseteq V(G)$ with $|X|\leq k-2$, then there is a proper
$(\omega(G)-k+2)$-coloring of $G$ (so $(k-1)$-tuples are colored) that
restricts to a proper $(\omega(G)-k+2)$-coloring of $lk_{G}(X)$ (so
$(k-|X|-1)$-tuples are colored).

Let $X\subseteq V(G)$. If $|X|=k-2$, the statement follows immediately from
the first bullet in the definition of Bergeness. So we may assume that
$|X|<k-2$.

Order the vertices of $V(G)$ as $v_{1},\ldots,v_{n}$ such that
$X=\\{v_{1},\ldots v_{|X|}\\}$. Let $Y\subseteq V(G)$ with $|Y|=k-2$. and let
$i$ be maximum such that $v_{i}\in Y$ let
$R(Y)=lk_{G}(Y)[v_{i+1},\ldots,v_{n}]$. Then $R(Y)$ is a graph. Since
$|Y|=k-2$, the first bullet of the definition of Bergeness implies that there
is a proper $(\omega(G)-k+2)$-coloring $c_{Y}$ of $G$ (so $(k-1)$-tuples are
colored) that restricts to a proper $(\omega(G)-k+2)$-coloring of $lk_{G}(Y)$
(so vertices are colored). Since $R(Y)$ is a subgraph of $lk_{G}(Y)$, the
coloring $c_{Y}$ is also a coloring of $R(Y)$.

Let $Z$ be a ($k-1$)-tuple of vertices of $G$, and let $Y$ be the
$(k-2)$-initial segment of $Z$. Define $c(Z)=c_{Y}(Z\setminus Y)$.

We show that $c$ is proper. Let $F\in E(G)$, and let $Y$ be the initial
$(k-2)$-segment of $F$. Then $F\setminus Y$ is an edge $ab$, say, of $R(Y)$
and so $c_{Y}(a)\neq c_{Y}(b)$. But now $c(Y\cup\\{a\\})\neq c(Y\cup\\{b\\})$,
and so $F$ is not a monochromatic $K_{k}^{k-1}$ in $c$.

Next we show that $c$ restricts to a proper coloring of $lk_{G}(X)$. Let $F\in
E(lk_{G}(X))$, let $Z$ be the initial $(k-2-|X|)$-segment of $F$, and let
$Y=X\cup Z$. Then $c(F\cup X)=c_{Y}(F\setminus Z)$. Note that $F\setminus Z$
is an edge $ab$, say, of $R(Y)$ and so $c_{Y}(a)\neq c_{Y}(b)$. But now
$c(Z\cup\\{a\\})\neq c(Z\cup\\{b\\})$, and so $F$ is not a monochromatic
$K_{k-|X|}^{k-1-|X|}$ in $c$ when viewed as a coloring of $lk_{G}(X)$. This
proves that $G$ is $C_{\omega}$-perfect.

∎

We now prove:

######  2.6.

An $H_{\omega}$-perfect hypergraph is $C_{\omega}$-perfect.

###### Proof.

Let $G$ be an $H_{\omega}$-perfect $k$-uniform hypergraph. By 2.5 it is enough
to prove that $G$ is Berge. We need to show that for every induced
subhypergraph $G^{\prime}$ of $G$ we have

  * •

If $X\subseteq V(G^{\prime})$ with $|X|=k-2$, then there is a proper
$(\omega(G^{\prime})-k+2)$-coloring of $G^{\prime}$ (so $(k-1)$-tuples are
colored) that restricts to a proper $(\omega(G^{\prime})-k+2)$-coloring of
$lk_{G^{\prime}}(X)$ (so $(k-|X|-1)$-tuples are colored).

Let $G^{\prime}$ be an induced subhypergraph of $G$, and let $X\subseteq
V(G^{\prime})$ with $|X|=k-2$. Since $G$ is $H_{\omega}$-perfect, and
therefore $H$-perfect, we have that $lk_{G^{\prime}}(X)$ is a perfect graph.
Consequently, $lk_{G^{\prime}}(X)$ has a proper
$\omega(lk_{G^{\prime}}(X))$-coloring $c$. Since $G$ is $H_{\omega}$-perfect,
and therefore clique friendly, it follows from 2.4 that
$\omega(lk_{G^{\prime}}(X)\leq\omega(G^{\prime})-k+2$. Now coloring every
$(k-1)$-tuple $Z$ of $G$ by $c(Z\setminus X)$, we obtain a proper
$(\omega(G^{\prime})-k+2)$-coloring of $G^{\prime}$ (so $(k-1)$-tuples are
colored) that restricts to a proper $(\omega(G^{\prime})-k+2)$-coloring of
$lk_{G^{\prime}}(X)$. This proves that $G$ is Berge. Now 2.6 follows from 2.5.
∎

To summarize we have:

######  2.7.

$H_{\omega}$-perfect $\rightarrow$ Berge $\rightarrow C_{\omega}$-perfect, and
$C_{\omega}$-perfect $\rightarrow$ Berge.

###  2.3 Proper coloring and Ramsey numbers

A well-known equivalent definition of perfect graphs (at the heart of the
alternative proof of the Weak Perfect Graph Theorem given in [6]) is the
following key fact:

######  2.8.

A graph $G$ is perfect if and only if for every induced subgraph $G^{\prime}$
of $G$ we have that $\alpha(G^{\prime})\omega(G^{\prime})\geq|V(G^{\prime})|$.

Denote by $R_{s}(k)$ the minimum integer such that for every $n\geq R_{s}(k)$
in every $s$-coloring of $K^{k-1}_{n}$ there is a monochromatic $K^{k-1}_{k}$.
Then $R_{s}(2)=s+1$, and $G$ is perfect if
$|V(G^{\prime})|<R_{\alpha(G^{\prime})\omega(G^{\prime})}(2)$ for every
induced subgraph $G^{\prime}$ of $G$.

We mention yet another related notion of perfect hypergraphs. Denote by
$R_{s}(k)$ the minimum integer such that for every $n\geq R_{s}(k)$ in every
$s$-coloring of $K^{k-1}_{n}$ there is a monochromatic $K^{k-1}_{k}$. Then
$R_{s}(2)=s+1$, and $G$ is perfect if
$|V(G^{\prime})|<R_{\alpha(G^{\prime})\omega(G^{\prime})}(2)$ for every
induced subgraph $G^{\prime}$ of $G$.

Definition of $R$-perfect: A $k$ uniform hypergraph $G$ is $R$-perfect if
$|V(G)|<R_{(\alpha(G)-k+2)(\omega(G)-k+2)}(k)$, and this property holds for
all induced subhypergraphs and links.

######  2.9.

Let $G$ be a $k$-uniform hypergraph. If

  * [PC

] $G$ admits a proper coloring with $\omega(G)-k+2$ colors and its complement
$G^{C}$ admits a proper coloring with $\alpha(G)-k+2$ coloring

then

(1) $|V(G)|<R_{(\alpha(G)-k+2)(\omega(G)-k+2)}(k).$

###### Proof.

Let $c^{G}$ be the $(\omega(G)-k+2)$-coloring of $K^{k-1}_{[V(G)]}$ and let
$c^{G^{c}}$ be the $(\alpha(G)-k+2)$-coloring of $K^{k-1}_{[V(G)]}$. For every
$e\in E(G)$ let $c(e)=(c^{G}(e),c^{G^{c}}(e))$. Then $c$ is a coloring of
$K^{k-1}_{[V(G)]}$ with $(\alpha(G)-k+2)(\omega(G)-k+2)$ colors.

It remains to show that there is no monochromatic $K^{k-1}_{k}$ in $c$.
Suppose that $Y\subseteq V(G)$ is a monochromatic $K^{k-1}_{k}$ in $c$. If
$Y\in E(G)$, then the coloring is not monochromatic in the first coordinate,
and if $Y\not\in E(G)$, then the coloring is not monochromatic in the second
coordinate, a contradiction. This proves 2.9. ∎

The class of $k$-uniform hypergraphs described by property [PC] for all
induced subhypergraphs (but not necessary links), and the subclass of
$R$-perfect hypergraphs are both self-complementary classes that again, for
$k=2$ consist of the class of perfect graphs.

##  3 Examples and extremal properties

###  3.1 Basic examples of $H_{\omega}$-perfect hypergraphs

In this subsection we list a few constructions that yield $H_{\omega}$-perfect
$k$-uniform hypergraphs. First, a disjoint union of two $H_{\omega}$-perfect
hypergraphs is $H_{\omega}$-perfect. Next, let $H$ be a $k$-uniform hypergraph
and $u\notin V(H)$. The cone over $H$, $v*H$, is a $(k+1)$-uniform hypergraph
whose edges are $\\{\\{v\\}\cup A:A\in E(H)\\}$. It is easy to see that a cone
over every $H_{\omega}$-perfect hypergraph is $H_{\omega}$-perfect. Thus we
can start with a perfect graph, and increase $k$ by repeatedly taking cones.
Simple 3-uniform hypergraphs are $H_{\omega}$-perfect, and so are tripartite
3-uniform hypergraphs. More generally $k$-uniform hypergraphs, in which no two
edges share more than $k-2$ vertices, are $H_{\omega}$-perfect and so are
$k$-partite $k$-uniform hypergraphs.

A simple induction gives another natural family:

######  3.1.

Let $G$ be a $H_{\omega}$\- perfect $k$-uniform hypergraph, and let $H$ be the
hypergraph of cliques of size $r$ ($r>k$) in $G$. Then $H$ is
$H_{\omega}$-perfect.

Remark: The class of graphs ${\cal P}_{k}$ for which the hypergraphs of
cliques of size $k$ are $H_{\omega}$-perfect seems an interesting refinement
of the class of perfect graphs.

###  3.2 Turán-type problems for $H_{\omega}$-perfect hypergraphs

The celebrated Mantel-Turán theorem can be stated as follows:

######  3.2.

Let $G$ be a triangle-free graph. Then $G$ has at most the number of edges of
a bipartite graph on $|V(G)|$ vertices.

For 3-uniform hypergraphs we have:

######  3.3.

Let $G$ be an $H_{\omega}$\- perfect 3-uniform hypergraph without $K_{4}^{3}$.
Then $G$ has at most the number of edges of a tripartite hypergraph.

###### Proof.

Let $v$ be a vertex contained in the maximum number of edges of $G$. Then
$lk_{G}(v)$ is a bipartite graph. Let $Z$ be the set of all vertices $u$ that
are isolated vertices of the graph $lk_{G}(v)$. Construct a new hypergraph as
follows: delete all edges of $G$ that are contained in $Z$, and for every
$u\in Z$ and every edge $xy$ of the graph $lk_{G}(v)$, add the edge
$\\{u,x,y\\}$. Now $H$ is a tripartite hypergraph, and every vertex of $H$ is
contained in at least as many edges as it was in $G$. ∎

The result extends to $r$-uniform $H_{\omega}$-perfect hypergraphs without
$K_{m}^{r}$. It is interesting to ask if we can find a larger class of
$r$-uniform hypergraphs, $r\geq 3$, defined by forbidden induced
subhypergraphs, for which the assertion of Theorem 3.3 holds. We do not know
the situation for $C_{\omega}$-perfect hypergraphs. For general
$K_{4}^{3}$-free hypergraphs, there is a famous conjecture by Turán for the
maximum number of edges. Turán conjectured that the maximum is attained by the
following construction: Partition the vertices to three, as equal as possible,
parts $A,B$, and $C$. Consider the hypergraphs with all edges of the form
$\\{a,b,c\\},$$\\{a,a^{\prime},b\\},$$\\{b,b^{\prime},c\\}$, and
$\\{c,c^{\prime},a\\}$. (Here $a,a^{\prime}$ represents vertices in $A$, etc.)
In Turan’s example, all links are (very simple) perfect graphs. For example,
the link of $a\in A$ consists of all edges with vertices in $C$, all edges
with one vertex in $B$ and one in $C$, and all edges with one vertex in $A$
(different from $a$) and one vertex in $B$. It follows that Turán’s example is
$H$-perfect, and it is also easy to see that, in the example, four vertices
cannot span precisely one edge, and therefore the example is
$H_{\alpha}$-perfect. Interesting special cases of Turán’s conjecture are to
show that it holds for $H_{\alpha}$-perfect 3-uniform hypergraphs or also for
all $H$–perfect 3-uniform hypergraphs.

It could also be of interest to study other Turán type questions for perfect
$k$-uniform hypergraphs (under the various definitions). For example, a
hypergraph is called intersecting if every two edges have non-empty
intersection, and we can ask what is the maximum number of edges in an
intersecting $H_{\omega}$-perfect 3-uniform hypergraph with $n$ vertices?

Examples that may give the maximum are (here $n$ is the number of vertices of
the hypergraph):

  1. a)

$K_{5}^{3}$ ($n=5$),

  2. b)

An $n$-vertex hypergraph $H$ that has three special vertices $a,b,c$, where
the hyperedges of $H$ are all triples with at least two elements in
$\\{a,b,c\\}$ ($6\geq n\geq 11$),

  3. c)

a cone over a balanced complete bipartite graph ($n\geq 11$.).

Another example with the same number of edges as b) is the following: $H$ is
an $n$ vertex hypergraph with four special vertices $\\{a,b,c,d\\}$. Every
triple contained in $\\{a,b,c,d\\}$ is a hyperedge of $H$. Further, for every
vertex $v$ of the remaining $n-4$ vertices, choose arbitrarily one of the
triples on $\\{a,b,c,d\\}$, say $T$; then the three triples consisting of $v$
and two vertices of $T$ are also edges of $H$. In other words the link of $v$
is a triangle on the vertices $\\{a,b,c,d\\}$. Yet another example is obtained
by having the link of $v$ be one of the four stars on these four vertices.

###  3.3 $H_{\omega}$-perfect triangulated spheres

Recall that $k$-partite $k$-uniform hypergraphs are $H_{\omega}$-perfect. The
converse is far from being true: indeed, simple hypergraphs are
$H_{\omega}$-perfect and they can have arbitrary large chromatic number [13].
Here is an especially nice class of $H_{\omega}$-perfect hypergraphs.

######  3.4.

Let $G$ be an $r$-uniform hypergraph whose edges form a triangulation of an
$(r-1)$-dimensional sphere other than $K$. Then if $G$ is $H_{\omega}$-perfect
it is $r$-partite.

This is a reformulation of Ore’s theorem for planar graphs $(r=3)$ and its
well known high dimensional extensions. (See, e.g., [7, 9].)

##  4 Perfect cocycles

Figure 2: A graph whose cocycle is doubly perfect yet not $H$-perfect since
$lk_{co(G)}(v)\sim C_{7}$.

Let $G$ be a graph. An unordered triple $\\{x,y,z\\}\subseteq V(G)$ is $G$-odd
if $|E(G[\\{x,y,z\\}])|$ is odd. We denote by $co(G)$ the $3$-uniform
hypergraph with vertex set $V(G)$ and such that $\\{x,y,z\\}\in E(co(G))$ if
and only $\\{x,y,z\\}$ is $G$-odd. Hypergraphs in $co(G)$ are called
3-cocycles or two-graphs ([16]). Note that every cocyle and every complement
of a cocycle is clique friendly. Moreover, by (2.1) doubly perfect 3-uniform
hypergraphs are cocycles.

We start with two observations.

######  4.1.

Let $G$ be a graph. Then

  1. 1.

$co(G)^{c}=co(G^{c})$.

  2. 2.

For $X\subseteq V(G)$, $co(G)[X]=co(G[X])$.

######  4.2.

A $3$-cocycle is $H$-perfect if and only if it is both $H_{\omega}$-perfect
and $H_{\alpha}$-perfect. In particular, if a $3$-cocycle is $H$-perfect, then
it is doubly perfect.

###### Proof.

Let $F$ be an $H$-perfect $3$-cocycle. Then $F^{c}$ is $H$-perfect. By 4.1
$F^{c}$ is a cocycle. Then both $F$ and $F^{c}$ are clique friendly. It
follows that $F$ and $F^{c}$ are both $H_{\omega}$-perfect, and therefore $F$
is both $H_{\omega}$-perfect and $H_{\alpha}$-perfect. Now by 2.7 both $F$ and
$F^{c}$ are $C_{\omega}$-perfect, and therefore $F$ is doubly perfect. ∎

The goal of this section is to describe graphs $G$ for which $co(G)$ is
$H$-perfect, and to study the larger class of graphs $G$ for which $co(G)$ is
doubly perfect.

For a graph $G$ and a vertex $v\in V(G)$ we denote by $N_{G}(v)$ the set of
neighbors of $v$, and by $M_{G}(v)$ the set of non-neighbors of $v$. Note that
$v\not\in N_{G}(v)\cup M_{G}(v)$. When there is no danger of confusion we omit
the subscript $G$. Let $v\in V(G)$. We define the graph $G^{+}(v)$ as follows.
$V(G^{+}(v))=V(G)\setminus\\{v\\}$ and $xy\in E(G^{+}(v))$ if and only if one
of the following statements holds:

  * •

$x,y\in N_{G}(v)$ and $xy\in E(G)$

  * •

$x,y\in M_{G}(v)$ and $xy\in E(G)$

  * •

$x\in N(v)$, $y\in M(v)$ and $xy\not\in E(G)$.

Note that $G^{+}(v)=lk_{co(G)}(v)$.

Next we define a family of graphs that we call “pre-odd-holes”. A pair $(G,v)$
where $G$ is a graph with an even number $\geq 6$ of vertices, and $v\in V(G)$
is a pre-odd-hole centered at $v$ if there exists an even integer $k$ such
that $V(G)\setminus\\{v\\}$ can be partitioned into $k$ disjoint non-empty
subsets $P_{1},\ldots,P_{k}$ and the edges of $G$ are as follows.

  * •

$N_{G}(v)=\bigcup_{i\text{ even}}P_{i}$.

  * •

For every $i$, $G[P_{i}]$ is a path with vertices
$p_{1}^{i},\ldots,p_{n_{i}}^{i}$ in order.

  * •

If $i\neq j$ and $i=j\mod 2$ then there are no edges between $P_{i}$ and
$P_{j}$.

  * •

If $i\neq j\mod 2$ and $|i-j|\neq 1\mod k$, then every vertex of $P_{i}$ is
adjacent to every vertex of $P_{j}$.

  * •

If $k>2$, $j=i+1$, or $i=k$ and $j=1$ then $p_{n_{i}}^{i}$ is non-adjacent to
$p_{1}^{j}$ and all the other edges between $P_{i}$ and $P_{j}$ are present.

  * •

If $k=2$, then $p_{n_{1}}^{1}$ is non-adjacent to $p_{1}^{2}$, $p_{1}^{1}$ is
non-adjacent to $p_{n_{2}}^{2}$, and all the other edges between $P_{1}$ and
$P_{2}$ are present.

.

A pair $(G,v)$ is a pre-odd-antihole centered at $v$ if $(G^{c},v)$ is a pre-
odd-hole centered at $v$. We say that a graph $G$ is a pre-odd-hole if $(G,v)$
is a pre-odd-hole centered at $v$ for some $v\in V(G)$; a pre-odd-antihole is
defined similarly.

For a graph $G$ and an induced subgraph $H$ of $G$, we say that $v\not\in
V(H)$ is a center for $H$ is $v$ is complete to $V(H)$, and an anticenter for
$H$ if $v$ is anticomplete to $H$.

We say that $G$ is pure if

  * •

No odd hole of $G$ has a center.

  * •

No odd antihole of $G$ has a center.

  * •

No odd hole of $G$ has an anticenter.

  * •

No odd antihole of $G$ has an anticenter.

  * •

No induced subgraph of $G$ is a pre-odd-hole.

  * •

No induced subgraph of $G$ is a pre-odd-anti-hole.

We prove:

######  4.3.

$co(G)$ is $H$-perfect perfect if and only if $G$ is pure.

###### Proof.

By the Strong Perfect Graph theorem, it is enough to prove that $G$ is pure if
and only if for every $v\in V(G)$, the graph $G^{+}(v)$ is Berge.

Let us say that $v\in V(G)$ is pure if all of the following hold.

  1. 1.

$v$ is not a center for an odd hole of $G$.

  2. 2.

$v$ is not a center for an odd antihole of $G$.

  3. 3.

$v$ is not an anticenter for an odd hole of $G$.

  4. 4.

$v$ is not an anticenter for an odd antihole of $G$.

  5. 5.

$(H,v)$ is not a pre-odd-hole with center $v$ for any induced subgraph $H$ of
$G$.

  6. 6.

$(H,v)$ is not a pre-odd-antihole with center $v$ for any induced subgraph of
$H$ of $G$.

Cleary $G$ is pure if and only if every vertex of $G$ is pure.

We show that for $v\in V(G)$ the graph $G^{+}(v)$ is Berge if and only if $v$
is pure. Let $v\in V(G)$, write $N=N_{G}(v)$ and $M=M_{G}(v)$. Suppose $C$ is
an odd hole in $G^{+}(v)$ with vertices $c_{1},\ldots,c_{2t+1},c_{1}$ in
cyclic order. If $V(C)\subseteq N$, then $v$ is a center for $C$, and if
$V(C)\subseteq M$, then $v$ is a an anticenter for $C$. Now assume that $C$
meets both $N$ and $M$. Let $\\{A,B\\}=\\{N,M\\}$. Note that

  * •

if $x$ and $y$ are two consecutive vertices of $C$, and they are both in $A$
or both in $B$, then $xy\in E(G)$,

  * •

if $x$ and $y$ are two consecutive vertices of $C$, and $x\in A$ and $y\in B$,
then $xy\not\in E(G)$

  * •

if $x,y$ are non-consecutive vertices of $C$, and they are both in $A$ or both
in $B$, then $xy\not\in E(G)$,

  * •

if $x,y$ are non-consecutive vertices of $C$, and $x\in A$ and $y\in B$, then
$xy\in E(G)$.

A sector of $C$ is the vertex set of a maximal path of $C$ that is contained
in $M$ or in $N$. Thus for some even integer $k$, the set
$\\{c_{1},\ldots,c_{2t+1}\\}$ can be partitioned into sectors
$P_{1},\ldots,P_{k}$ where $\\{c_{1},\ldots,c_{2t+1}\\}\cap N=\bigcup_{i\text{
even}}P_{i}$. Now it is easy to check that $G[\\{v,c_{1},\ldots,c_{2t+1}\\}]$
is a pre-odd-hole centered at $v$.

Conversly, if $(H,v)$ is a pre-odd-hole centered at $v$, then traversing the
paths $P_{1},\ldots,P_{k}$ (from the defintion of a pre-odd-hole) in order we
obtain and odd hole in $G^{+}(v)$.

This show that $G^{+}(v)$ contains an odd hole if and only if $v$ fails to
satisfy one of the odd-numbered conditions for being pure. Applying this to
$G^{c}$, we deduce that $G^{+}(v)$ contains an odd antihole if and only if $v$
fails to satisfy one of the even-numbered conditions for being pure. Thus we
showed that $v$ is pure if and only if $G^{+}(v)$ is Berge. Since $G$ is pure
if and only if every vertex of $G$ is pure, this proves 4.3. ∎

In view of 4.2 we deduce

######  4.4.

$G$ is pure if and only if $co(G)$ is both $H_{\omega}$-perfect and
$H_{\alpha}$-perfect. In particular, if $G$ is pure, then $co(G)$ is doubly
perfect.

###  4.1 Doubly-perfect cocycles

We present many examples of graphs $G$ such that $co(G)$ is not doubly
perfect. The class of graphs $G$ for which $co(G)$ is doubly perfect is closed
under induced subgraphs and hence it can be described in terms of forbidden
induced subgraphs. However, our examples suggest that such a description could
be out of reach.

Start with a triangle-free graph $H$ with chromatic number $\chi(H)>4$. Next,
add a new vertex $v$ adjacent to an arbitrary subset $A\subset V(H)$. Consider
now the graph $G$ obtained from $H+v$ by the following operation: for every
edge $e=(x,y)$ where $x\in A$ and $y\in V(H)\backslash A$, $e\in E(G)$ iff
$e\notin E(H)$. For all other edges $e\in E(G)$ iff $e\in E(H)$. (In other
words, we switch between edges and nonedges between $A$ and $V(H)\backslash
A$.)

######  4.5.

$co(G)$ is not $C_{\omega}$-perfect.

###### Proof.

We need two claims.

######  4.6.

Let $v\in V(G)$. Then $lk_{co(G)}(v)=H$

###### Proof.

A triple $\\{v,a,b\\}$ belongs to $co(G)$ if it has an odd number of edges
from $G$. If $a$ and $b$ are both in $A$ or in $V(H)\backslash A$ this occurs
iff $ab$ is an edge in $H$. If $a\in A$ and $b\in V(H)\backslash A$ this
occurs iff $ab$ is not an edge of $G$ and hence is an edge in $H$. ∎

######  4.7.

$\omega(co(G))=4$.

###### Proof.

Since $lk_{co(G)}(v)=H$, there is not even $K_{4}^{3}$ in $co(G)$ that include
the vertex $v$. $co(G)$ and $co(H)$ restricted to all other vertices coincide
and it is easy to verify that $co(H)$ contains no $K_{5}^{3}$ when $H$ is
triangle-free. ∎

To conclude the proof of 4.5 we note that a proper coloring of the edges of
$co(G)$ with $t$ colors restricts to a proper vertex coloring of $H$ with $t$
colors, and since the number of colors exceeds 4, $co(G)$ is not
$C_{\omega}$-perfect. ∎

##  5 Connections, problems, and other notions of perfectness

###  5.1 Vertex colorings and $\chi$-boundedness

The families of hypergraphs described in this paper are closed under induced
subhypergraphs and therefore can be described in terms of forbidden induced
subhypergraphs. The study of families of graphs described in terms of
forbidden induced subgraphs is a rich part of graph theory and extensions for
uniform hypergraphs are of interest. In our definitions we replaced vertex
coloring for perfect graphs with proper colorings of sets of $(k-1)$ vertices
but it is of interest to also examine vertex colorings.

A family of $k$-uniform hypergraphs is $\chi$-bounded if for some function $f$
the vertices of every hypergraph $G$ in the family can be covered by
$f(\omega(G))$ independent sets. A family of $k$-uniform hypergraphs is
$\chi^{c}$-bounded if the family of its complements are $\chi$-bounded or , in
other words, if for some function $f$ the vertices of every hypergraph $G$ in
the family can be covered by $f(\alpha(G))$ cliques. For graphs ($k=2$) this
notion was studied starting with works of Gyárfás and others, see [15] for a
recent survey. For example, it is known that the class of graphs with no odd
holes is $\chi$-bounded.

Problem: Are $H_{\omega}$-perfect (or even $C_{\omega}$-perfect) $k$-uniform
hypergraphs $\chi^{c}$-bounded? (Equivalent formulation: Are
$H_{\alpha}$-perfect hypergraphs $\chi$-bounded?)

As we already mentioned, $H_{\omega}$-perfect hypergraphs are not
$\chi$-bounded since simple hypergraphs that can have arbitrary large
chromatic number are $\omega$-perfect.

It is easy to see (directly) that doubly-perfect 3-hypergraphs are
$\chi$-bounded with $f(m)=m-1$. Indeed if $\omega(G)=t$ then for a vertex $v$
$\omega(lk_{G}(v))=t-1$ and therefore the vertices of $lk_{G}(v)$ can be
covered by $t-1$ independent sets. Now, since $G$ is a cocycle these
independent sets remain independent in $G$ and adding $v$ to one of them
describes $V(G)$ as the union of $t-1$ independent set. The class of
$\chi$-bounded $k$-uniform hypergraphs with $f(m)=m-k+1$ seems another
interesting extension of perfect graphs. The strongest form of
$\chi$-boundedness that we can have for $k$-uniform hypergraphs is with
$f(n)=\lceil n/(k-1)\rceil$, and the restricted class of $\chi$-bounded
$k$-uniform hypergraphs with $f(n)=\lceil n/(k-1)\rceil$ is yet another
extension of perfect graphs worthy of study.

###  5.2 Analogs for chordal graphs and for interval graphs

A different avenue for perfect hypergraphs could start with various high
dimensional extensions from the literature for chordal graphs. One definition
is that a $k$-uniform hypergraph $G$ is chordal if its clique complex $C(G)$
is $k$-Leray, meaning that $H_{i}(K)=0$ for every $i\geq k-1$ and every
induced subcomplex $K$ of $C(G)$. (Here, the clique complex $C(G)$ of a
hypergraph $G$ is the simplicial complex on the vertices of $G$ whose faces
correspond to sets of vertices that span a complete hypergraph.) This
definition of chordality coincided with the definition of chordal graphs for
$k=2$, namely the homological condition simply asserts that the graph has no
induced cycles with more than three edges. Certain refinements of this notion
were considered in [2, 1].

It is known, [3] that if $G$ is a $k$-uniform chordal hypergraph (according to
the definition above) then it $\chi^{C}$-bounded, in other words if
$\alpha=\alpha(G)$ then $G$ can be covered by $f(\alpha,k)$ cliques.

An interesting larger class of hypergraphs extending the class of graphs with
no odd holes would allow $k$-dimensional homological cycles provided they are
$k$-partite. We do not know if $\chi^{c}$-boundedness still holds. (Imposing
this condition both for $G$ and its complement leads again to the class of
perfect graphs for $k=2$.)

A special case of chordal $k$-uniform hypergraphs (which motivated their
definition) are those represented by collections of convex sets in $R^{d}$.
Given such a collection we consider the hypergraph where vertices correspond
to sets of the collection, and edges correspond to $k$ sets with non-empty
intersection. When $k=2$ we obtain the class of interval graphs.

###  5.3 The Hadwiger-Debrunner property

Another aspect worth considering is the following: Consider the class of
$k$-uniform hypergraphs with the following property (that we call the
$HD_{r}$-property): If every set of $p$ vertices contains a complete
subhypergraph of size $q$ where $q\geq k$ and

(2) $p(r-1)<(q-1)(r)$

then $V(G)$ can be covered by $p-q+1$ cliques. We note that every $k$-uniform
hypergraph has the $HD_{k}$ property, and we are mainly interested in the case
that $r=k-1$. For $k=2,r=1$ those are perfect graphs. A proof of the
$HD_{k-1}$-property for $k$-uniform hypergraphs associated with families of
convex sets in $R^{k-1}$ goes back to [8].

###  5.4 Voloshin’s C-perfectness

A different notion of perfectness for hypergraphs was pioneered by Voloshin
[17, 18] and further studied by Bujtás and Tuza [4]. Voloshin considered
colorings of hypergraphs $G$ where no edge is multicolored (or rainbow). He
defined $\bar{\chi}(G)$ as the maximum number of colors in such a coloring.
Clearly, $\bar{\chi}(G)\geq\alpha(G)$, and $G$ is perfect according to
Voloshin if for every induced subhypergraph $H$, $\bar{\chi}(H)=\alpha(H)$.

###  5.5 Is there a homological description of perfect graphs?

We mentioned that chordal graphs have a simple homological description: $G$ is
chordal if and only if for every induced subgraph $H$ of $G$, $H_{i}(C(H))=0$,
for every $i>0$, where $C(H)$ is the clique complex of $H$. It is an
interesting question if a similar homological definition exists for perfect
graphs.

## References

  * [1] K. Adiprasito, Toric chordality, J. Math. Pures Appl. 108 (2017), 783–807.
  * [2] K. Adiprasito, E. Nevo, A. Samper, Higher chordality: from graphs to complexes.Proc. Amer. Math. Soc. 144 (2016), 3317–3329.
  * [3] N. Alon, G. Kalai, J. Matousek, and R. Meshulam, Transversal numbers for hypergraphs arising in geometry, Adv. Appl. Math. 29 (2002), 79–101.
  * [4] C. Bujtás and Z. Tuza, C-perfect hypergraphs, J. Graph theory 64 (2009), 132–149.
  * [5] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Annals of Mathematics, 164 (2006), 51–229.
  * [6] G. S. Gasparian, Minimal imperfect graphs: A simple approach Combinatorica 16(1996), 209–212.
  * [7] J. E. Goodman and H. Onishi, Even Triangulations of $S^{3}$ and the Coloring of Graphs, Trans. of the Amer. Math. Soc. 246 (1978) 501–510.
  * [8] H. Hadwiger and H. Debrunner, Über eine Variante zum Helly‘schen Satz, Arch. Math. 8 (1957), 309–313.
  * [9] I. Izmestiev, M. Joswig, Branched coverings, triangulations, and 3-manifolds Adv. Geom., 3 (2003), 191–225.
  * [10] N. Linial, What is high-dimensional combinatorics, Lecture at Random-Approx., August ’08, https://www.cs.huji.ac.il/ nati/PAPERS/random_approx_08.pdf.
  * [11] N. Linial, Challenges of high-dimensional combinatorics, lecture at Laszlo Lovász 70th birthday conference, Budapest July 2018\. http://www.cs.huji.ac.il/ nati/PAPERS/challenges-hdc.pdf .
  * [12] L. Lovász, Normal hypergraphs and the perfect graph conjecture Disc. Math., 2 (1972), 253-267.
  * [13] J. Nesetril and V. Rodl, A short proof of the existence of highly chromatic hypergraphs without short cycles J. Combin. Theory Ser. B, 27 (1979) 225–227
  * [14] V. Rödl, On the chromatic number of subgraphs of a given graph, Proc. Amer. Math. Soc. 64 (1977), 370–371.
  * [15] A. Scott and P.D. Seymour, a survey of $\chi$-boundedness, preprint.
  * [16] J. J. Seidel, A survey of two-graphs. In: Colloquio Internazionale sulle Teorie Combinatorie (Proceedings, Rome, 1973), Vol. I,(1976), pp. 481–511.
  * [17] V. I. Voloshin, On the upper chromatic number of a hypergraph, Australasian J. Combinatorics 11 (1995), 25–45.
  * [18] V. I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, Fields Institute Monograph, American Mathematical Society, Providence, RI, 2002.