# Evaluating Lebesgue constants by Chebyshev polynomial meshes on cube,
simplex and ball

L. Białas-Cież  Jagiellonian University, Poland  D.J. Kenne  Doctoral School
of Exact and Natural Sciences, Jagiellonian University  A. Sommariva  M.
Vianello

###### Abstract

We show that product Chebyshev polynomial meshes can be used, in a fully
discrete way, to evaluate with rigorous error bounds the Lebesgue constant,
i.e. the maximum of the Lebesgue function, for a class of polynomial
projectors on cube, simplex and ball, including interpolation,
hyperinterpolation and weighted least-squares. Several examples are presented
and possible generalizations outlined. A numerical software package
implementing the method is freely available online.

2020 AMS subject classification: 65D05, 65D10, 65K05. Keywords: Multivariate
polynomial meshes, cube, simplex, ball, polynomial projectors, interpolation,
least-squares, hyperinterpolation, polynomial optimization, Lebesgue constant.

##  1 Introduction

Starting from the seminal paper by Calvi and Levenberg [16], the notion of
polynomial (admissible) mesh has been emerging in the last years as a
fundamental theoretical and computational tool in multivariate polynomial
approximation. Let $K\subset\mathbb{R}^{d}$ (or $K\subset\mathbb{C}^{d}$) be a
polynomially determining compact set (i.e., polynomials vanishing there vanish
everywhere) and denote by $\mathbb{P}_{n}=\mathbb{P}_{n}^{d}$ the space of
$d$-variate polynomials of degree not exceeding $n$, and by

$N=N_{n}=dim(\mathbb{P}_{n})={n+d\choose n}$ (1)

its dimension.

A polynomial admissible mesh of $K$ is a sequence of finite norming subsets
$X_{n}\subset K$ such that

$\|p\|_{K}\leq c\|p\|_{X_{n}}\;,\;\;\forall p\in\mathbb{P}_{n}\;,$ (2)

with $card(X_{n})=O(n^{\alpha})$, $\alpha\geq d$, and $c$ a constant
independent of $n$. Here and below, $\|\cdot\|_{Y}$ denotes the sup-norm on a
continuous or discrete compact set $Y$. The fact that $card(X_{n})\geq N$
necessarily holds, each $X_{n}$ being $\mathbb{P}_{n}$-determining, since
polynomials vanishing on $X_{n}$ vanish everywhere on $K$. Such a mesh is
termed optimal when $\alpha=d$.

To give only a flavour of the topic, we recall that polynomial meshes are
invariant by affine transformations, are stable under small perturbations, and
can be assembled by finite union, finite product and algebraic
transformations, starting from known instances. These include cubes (boxes),
simplices and balls, but also more general linear and curved polytopes, as
well as convex bodies and more general compact domains satysfying Markov
polynomial inequalities. On the other hand, when available optimal polynomial
meshes are preferable in applications due to their low cardinality, for
example in the extraction of extremal points such as Fekete-like and Leja-like
points. We do not even attempt here to give a comprehensive survey of the
already considerable literature on polynomial meshes, referring the reader
e.g. to [2, 3, 8, 12, 18, 34, 43, 50] with the references therein.

In the present paper, by exploiting the connection with the polynomial
optimization methods studied for example in [44, 56, 57], we develop
theoretical estimates together with a numerical algorithm to approximate the
value of fitting operators uniform norms (Lebesgue constants). Indeed,
computation of Lebesgue constants is a matter of optimization of Lebesgue
functions, which ultimately corresponds to the computation of the maximum
modulus of fitting polynomials. The method works in a fully discrete way on
special polynomial meshes of product Chebyshev type on cubes, simplices and
balls, producing approximations of the Lebesgue constant from above and below,
with rigorous error bounds. We also point out that, by the finite union
property of polynomial meshes, the method can be readily applied, with the
same error bounds, to complicated geometrical objects relevant in
applications, namely single polytopes (via triangulation), union of polytopes
and union of balls.

Computation of Lebesgue constants is important in applications, in order to
check the quality of the sampling nodes e.g. for interpolation. In the
literature this step is typically made, for example within spectral and high-
order methods for numerical PDEs, by empirical approaches, namely by
evaluation of Lebesgue functions on increasingly dense discretizations. In the
present paper we provide, apparently for the first time, a fully discrete
method with rigorous error bounds as well as the corresponding numerical
codes.

The paper is organized as follows. In Section 2 we state and prove the main
theoretical results and we also outline an extended (but less accurate)
approach via general polynomial meshes on multidimensional compact sets. In
Section 3 we discuss some computational and implementation issues, and in
Section 4 we present several examples concerning evaluation of the size of
Lebesgue constants for polynomial interpolation and least-squares (including
hyperinterpolation) on cube, simplex and ball.

##  2 Lebesgue constants by Chebyshev meshes

In the sequel, the following constant will play a key role

$c_{m}=\frac{1}{\cos(\pi/(2m))}\;,\;\;m>1\;.$

Moreover, we shall denote by $\mathscr{C}_{k}$ the set of $k$ Chebyshev zeros
in $(-1,1)$, $\cos((2j-1)\pi/(2k))$, $1\leq j\leq k$ (Chebyshev points), or
the set of $k+1$ Chebyshev extrema in $[-1,1]$, $\cos(j\pi/k)$, $0\leq j\leq
k$ (Chebyshev-Lobatto points).

###  2.1 The cube

We discuss first the case of the $d$-cube. By invertible affine
transformation, the result can be immediately extended to any $d$-box, with
invariance of the mesh constant $c$. The following result has been proved in
[44] essentially following [6], by the notion of Dubiner distance on a compact
set (which is tailored to polynomial spaces; cf. e.g. [10, 58]) with the
references therein).

###### Lemma 1

Let $\mathscr{C}_{k}$ be Chebyshev or Chebyshev-Lobatto points in $[-1,1]$.
Then the sequence of product Chebyshev grids
$X_{n}^{m}=(\mathscr{C}_{mn})^{d}$, $n=1,2,\dots$, for a fixed $m>1$, is an
admissible polynomial mesh for the $d$-cube $[-1,1]^{d}$, with constant
$c=c_{m}$.

We can now state and prove a basic result on approximation of Lebesgue
constants by polynomial meshes on the $d$-cube.

###### Proposition 1

Let $X_{n}^{m}=(\mathscr{C}_{mn})^{d}$ be a product Chebyshev admissible mesh
of $K=[-1,1]^{d}$ as in Lemma 1, and $L_{n}:C(K)\to\mathbb{P}_{n}$ a linear
projection operator such that

$L_{n}f(x)=\sum_{i=1}^{M}{f(\xi_{i})\,\varphi_{i}(x)}\;,$ (3)

where $\Xi=\\{\xi_{i}\\}\subset K$ and $\\{\varphi_{i}\\}$ is a set of
generators of $\mathbb{P}_{n}$. Moreover, let

$\lambda_{n}(x)=\sum_{i=1}^{M}{|\varphi_{i}(x)|}$

be the “Lebesgue function”of $L_{n}$ and

$\|L_{n}\|=\sup_{f\neq 0}\frac{\|L_{n}f\|_{K}}{\|f\|_{K}}=\|\lambda_{n}\|_{K}$

its “Lebesgue constant”. Then, the following estimate holds for every $m>1$

$\|\lambda_{n}\|_{X_{n}^{m}}\leq\|L_{n}\|\leq
c_{m}\|\lambda_{n}\|_{X_{n}^{m}}\;.$ (4)

Proof. First we prove that $\|L_{n}\|=\|\lambda_{n}\|_{K}$ for any projection
operator of the form (3), on a general compact set $K$. Indeed, inequality
$\|L_{n}f\|_{K}\leq\|f\|_{K}\|\lambda_{n}\|_{K}$ is immediate, whereas
existence of $g^{\ast}\in C(K)$ such that
$g^{\ast}(\xi_{i})=sign(\varphi_{i}(x^{\ast}))$, where
$\|\lambda_{n}\|_{K}=\lambda_{n}(x^{\ast})$ with $x^{\ast}\in K$, and
$\|g^{\ast}\|_{K}=1$, is guaranteed by a quite general topological result,
namely the celebrated Tietze extension theorem of continuous functions from a
closed subset of a normal topological space, preserving the range (cf. e.g.
[27, Ch.7, Thm.5.1]). Indeed, defining a function $g$ on the sampling set
$\Xi$ such that $g(\xi_{i})=sign(\varphi_{i}(x^{\ast}))$, $1\leq i\leq M$,
since $g$ is trivially continuous on the closed discrete subset $\Xi\subset
K$, there exists an extension $g^{\ast}\in C(K)$ taking values in $[-1,1]$,
with $L_{n}g^{\ast}(x^{\ast})=\lambda_{n}(x^{\ast})$.

Now, applying Lemma 1 to the polynomial $L_{n}f$ we get

$\|L_{n}f\|_{K}\leq c_{m}\|L_{n}f\|_{X_{n}^{m}}\;.$

On the other hand
$|L_{n}f(x)|\leq\|f\|_{\Xi}\lambda_{n}(x)\leq\|f\|_{K}\lambda_{n}(x)$ and thus
$\|L_{n}f\|_{K}\leq c_{m}\|f\|_{K}\|\lambda_{n}\|_{X_{n}^{m}}$, from which we
get immediately

$\|L_{n}\|=\|\lambda_{n}\|_{K}\leq c_{m}\|\lambda_{n}\|_{X_{n}^{m}}\;,$

and thus (4), since $\|\lambda_{n}\|_{K}\geq\|\lambda_{n}\|_{X_{n}^{m}}$ by
inclusion. $\square$

###### Remark 1

Notice that $c_{m}\to 1$ and thus, if the sampling set $\Xi$ is independent of
$m$, $\|\lambda_{n}\|_{X_{n}^{m}}\to\|L_{n}\|$ as $m\to\infty$. Moreover, from
(4) we also get a relative error estimate, namely

$0\leq\frac{\|L_{n}\|-\|\lambda_{n}\|_{X_{n}^{m}}}{\|L_{n}\|}\leq(c_{m}-1)\sim\frac{\pi^{2}}{8m^{2}}\approx\frac{1.23}{m^{2}}\;,$
(5)

i.e. $\|\lambda_{n}\|_{X_{n}^{m}}$ approximates the Lebesgue constant from
below with a $\mathscr{O}(1/m^{2})$ relative error. On the other hand, (4)
gives also the rigorous and computable absolute error estimate
$0\leq\|L_{n}\|-\|\lambda_{n}\|_{X_{n}^{m}}\leq(c_{m}-1)\|\lambda_{n}\|_{X_{n}^{m}}$.
We finally notice that (4) is an interval approximation of the Lebesgue
constant. Hence we can use the midpoint approximation

$\frac{|\,\|L\|_{n}-\Lambda_{n}^{m}\,|}{\|L_{n}\|}\leq\frac{c_{m}-1}{2}\;,\;\;\Lambda_{n}^{m}=\|\lambda_{n}\|_{X_{n}^{m}}\,\frac{1+c_{m}}{2}\;,$
(6)

which improves the error estimates by a factor $1/2$.

###### Remark 2

The structure of projection operators like (3) includes interpolation
operators at unisolvent nodes $\Xi=\\{\xi_{1},\dots,\xi_{N}\\}\subset K$,
where, denoting by $V_{n}=[p_{j}(\xi_{i})]$, $1\leq i,j\leq N$, the
Vandermonde-like matrix in any fixed polynomial basis
$span\\{p_{1},\dots,p_{N}\\}=\mathbb{P}_{n}$, we have that

$\varphi_{j}(x)=\ell_{j}(x)=\frac{det(V_{n}(\xi_{1},\dots,\xi_{j-1},x,\xi_{j+1},\dots,\xi_{N}))}{det(V_{n}(\xi_{1},\dots,\xi_{j-1},\xi_{j},\xi_{j+1},\dots,\xi_{N}))}$
(7)

are the corresponding Lagrange cardinal polynomials. But also discrete
weighted least-squares operators at $\mathbb{P}_{n}$-determining nodes
$\Xi=\\{\xi_{1},\dots,\xi_{M}\\}\subset K$ with positive weights
$W=\\{w_{1},\dots,w_{M}\\}$, $M>N$, are included. Indeed, denoting by
$\\{\pi_{k}\\}$, $1\leq k\leq N$, the orthonormal polynomials with respect to
the corresponding discrete scalar product
$(f,g)_{\ell^{2}_{W}(\Xi)}=\sum_{j=1}^{M}{w_{j}f(\xi_{j})g(\xi_{j})}$, we have
that

$L_{n}f(x)=\sum_{k=1}^{N}{(f,\pi_{k})_{\ell^{2}_{W}(\Xi)}\,\pi_{k}(x)}=\sum_{j=1}^{M}{f(\xi_{j})w_{j}K_{n}(x,\xi_{j})}\;,$
(8)

i.e. $\varphi_{j}(x)=w_{j}K_{n}(x,\xi_{j})$, where
$K_{n}(x,y)=\sum_{k=1}^{N}{\pi_{k}(x)\pi_{k}(y)}$ is the reproducing kernel of
the discrete scalar product. Notice that in this case (unless $M=N$ where
least-squares approximation coincides with interpolation) the $\varphi_{j}$
are linearly dependent, thus forming a set of generators of $\mathbb{P}_{n}$.

We stress that the structure (8) also includes hyperinterpolation operators, a
topic that has seen an increasing interest as a valid alternative to
multivariate polynomial interpolation, after the seminal paper [48] by Sloan
in the mid ’90s; cf., e.g., [1, 22, 31, 32, 52, 59, 61] with the references
therein. Indeed hyperinterpolation operators are substantially truncated
Fourier-like expansions in series of orthogonal polynomials with respect to a
continuous measure with density. The continuous scalar products are there
substituted by discrete scalar products, corresponding to a suitable positive
quadrature formula exact in $\mathbb{P}_{2n}$.

###  2.2 The simplex

We consider now the $d$-simplex

$T_{d}=\\{x=(x_{1},\dots,x_{d})\in\mathbb{R}^{d}:\,0\leq x_{d}\leq\dots\leq
x_{1}\leq 1\\}\;,$ (9)

along with the $d$-dimensional Duffy-like transformation
$\mathscr{D}:\,[-1,1]^{d}\to T_{d}$, which can be defined as follows (cf. e.g.
[49])

$x_{i}=\mathscr{D}_{i}(t)=\prod_{j=1}^{i}(t_{j}/2+1/2)\;,\;1\leq i\leq
d\;\;,\;\;t=(t_{1},\dots,t_{d})\in[-1,1]^{d}\;.$ (10)

We again notice that the results can be immediately extended to any simplex by
invertible affine transformation, with invariance of the mesh constant $c$.

###### Lemma 2

Let $\mathscr{C}_{k}$ be the Chebyshev or Chebyshev-Lobatto points in $[-1,1]$
and $\mathscr{D}$ the Duffy-like transformation $[-1,1]^{d}\to T_{d}$ in (10),
where $T_{d}$ is the $d$-simplex. Then the sequence
$X_{n}^{m}=\mathscr{D}((\mathscr{C}_{mn})^{d})$, $n=1,2,\dots$, for a fixed
$m>1$, is an admissible polynomial mesh for $T_{d}$, with constant
$c=(c_{m})^{d}$.

Proof. Let us denote by $\mathbb{P}_{n}^{1}$ the space of univariate real
algebraic polynomials of degree not exceeding $n$. For every
$p\in\mathbb{P}_{n}$ we have that
$\|p\|_{T_{d}}=\|p\circ\mathscr{D}\|_{[-1,1]^{d}}$. Now, since $\mathscr{D}$
is a $d$-linear (surjective) mapping,
$p\circ\mathscr{D}\in\bigotimes_{k=1}^{d}\mathbb{P}_{n}^{1}$, the space of
tensorial polynomials of degree not exceeding $n$. Reasoning component by
component and using iteratively the univariate version of Lemma 1, it is
immediate to write the inequality

$\|p\circ\mathscr{D}\|_{[-1,1]^{d}}\leq(c_{m})^{d}\|p\circ\mathscr{D}\|_{(\mathscr{C}_{mn})^{d}}=(c_{m})^{d}\|p\|_{X_{n}^{m}}\;.\hskip
28.45274pt\square$

###### Proposition 2

Let $X_{n}^{m}=\mathscr{D}((\mathscr{C}_{mn})^{d})$ be a polynomial admissible
mesh of the $d$-simplex $K=T_{d}$ as in Lemma 2, and
$L_{n}:C(K)\to\mathbb{P}_{n}$ a linear projection operator with the structure
defined in Proposition 1. Then, the following estimate holds for every $m>1$

$\|\lambda_{n}\|_{X_{n}^{m}}\leq\|L_{n}\|\leq(c_{m})^{d}\|\lambda_{n}\|_{X_{n}^{m}}\;.$
(11)

Proof. We can proceed exactly as in the proof of Proposition 1, simply by
substituting $c_{m}$ with $(c_{m})^{d}$. $\square$

###### Remark 3

We observe that, since $(c_{m})^{d}\to 1$ as $m\to\infty$, the same assertions
of Remark 1 are valid, with $(c_{m})^{d}$ replacing $c_{m}$. The only
difference is that estimate (5) is asymptotically increased by a factor $d$,
namely

$0\leq\frac{\|L_{n}\|-\|\lambda_{n}\|_{X_{n}^{m}}}{\|L_{n}\|}\leq(c_{m})^{d}-1=(c_{m}^{d-1}+\dots+c_{m}+1)(c_{m}-1)$
$\leq\left(\left(\frac{m}{m-1}\right)^{d-1}+\dots+\frac{m}{m-1}+1\right)(c_{m}-1)\sim\frac{d\pi^{2}}{8m^{2}}\approx
1.23\,\frac{d}{m^{2}}$ (12)

for $d$ fixed and $m\to\infty$, where we have used the elementary inequality
$\cos(\theta)=\sin(\pi/2-\theta)\geq 1-2\theta/\pi$, $0\leq\theta\leq\pi/2$.

###### Remark 4

It is worth observing that, by the finite union extension property of
admissible polynomial meshes (cf. e.g. [16]), the results above are valid via
“triangulation” (subdivision into non overlapping simplices) on any polytope,
e.g. on any polygon in $d=2$ or polyhedron in $d=3$. We recall that for $d\geq
3$ in nonconvex instances the triangulation could require extra vertices, in
view of the well-known Schönardt counterexample [46]. On the other hand, for
the same reason it is also valid on any union of (even overlapping) polytopes,
where again the mesh is the union of the single polytope meshes obtained via
triangulation (in practice, this avoids tracking and triangulating the union
polytope which can be very complicated).

###  2.3 The ball

As a third relevant case, we discuss the unit Euclidean ball, i.e.
$B_{d}=\\{x\in\mathbb{R}^{d}:\,\|x\|_{2}\leq 1\\}$, by no loss of generality
since it is affinely equivalent to any other ball by translation and scaling,
with invariance of the mesh constant $c$. Again, the results can be extended
to a finite union of possibly overlapping balls, a geometrical object that is
relevant in applications, e.g. in the field of molecular modelling [41].

Below we denote by $\mathbb{P}_{n}^{1}$ the space of univariate real algebraic
polynomials of degree not exceeding $n$, and by $\mathbb{T}_{n}^{1}([a,b])$
the space of univariate real trigonometric polynomials of degree not exceeding
$n$, i.e $span\\{1,\sin(j\theta),\cos(j\theta)\,,\,j=1,\dots,n\\}$, restricted
to a subinterval $[a,b]$ of the period, $b-a\leq 2\pi$.

Moreover, we make use of the generalized spherical coordinates in $B_{d}$,
$d\geq 2$ ($B_{1}=[-1,1]$ is treated in section 2.1), corresponding to the
surjective transformation

$\mathscr{G}:J=[0,1]\times[0,\pi]^{d-2}\times[0,2\pi]\to B_{d}$

defined by

$\;x_{j}=r\cos(\theta_{j})\prod_{k=1}^{j-1}\sin(\theta_{k})\;,\;1\leq j\leq
d-2\;,$
$x_{d-1}=r\cos(\theta_{d-1})\prod_{k=1}^{d-2}\sin(\theta_{k})\;,\;x_{d}=r\sin(\theta_{d-1})\prod_{k=1}^{d-2}\sin(\theta_{k})\;,$
(13)

where$\;r\in[0,1]\;,\;\;\theta_{k}\in[0,\pi]\;,\;1\leq k\leq d-2$,
$\theta_{d-1}\in[0,2\pi]$; cf., e.g., [5]. These coordinates coincide with the
usual polar coordinates for the disk $B_{2}$ and spherical coordinates for the
3-ball $B_{3}$.

First, we state a basic Lemma on a norming inequality for univariate
trigonometric polynomials in the subperiodic case, whose proof can be found in
[57].

###### Lemma 3

Let $\mathscr{C}_{k}$ be the Chebyshev or Chebyshev-Lobatto points in $[-1,1]$
and let $\sigma_{a,b}:[-1,1]\to[a,b]$, $b-a\leq 2\pi$, be the invertible map

$\sigma_{a,b}(u)=2\arcsin(\alpha
u)+\beta\;,\;\;u\in[-1,1]\;,\;\alpha=\sin\left(\frac{b-a}{4}\right)\;,\;\beta=\frac{b+a}{2}\;.$
(14)

Then the following inequality holds

$\|\phi\|_{a,b}\leq
c_{m}\|\phi\|_{\sigma_{a,b}(\mathscr{C}_{2mn})}\;,\;\forall\phi\in\mathbb{T}_{n}([a,b])\;.$
(15)

###### Remark 5

We observe that the Chebyshev-like angles $\sigma_{a,b}(\mathscr{C}_{2mn})$
cluster at the interval endpoints for $b-a<2\pi$ (subperiodic instances),
whereas are equally spaced for $b-a=2\pi$ (periodic case).

###### Lemma 4

Let $\mathscr{C}_{k}$ be the Chebyshev or Chebyshev-Lobatto points in $[-1,1]$
and consider the composed transformation

$\mathscr{S}=\mathscr{G}\circ\mathscr{U}:[-1,1]^{d}\to B_{d}\;,$ (16)
$\mathscr{U}(u_{1},u_{2},\dots,u_{d-1},u_{d})=\left(\frac{u_{1}}{2}+\frac{1}{2},\sigma_{0,\pi}(u_{2}),\dots,\sigma_{0,\pi}(u_{d-1}),\sigma_{0,2\pi}(u_{d})\right)\;,$

where $B_{d}$ is the $d$-ball. Then the sequence
$X_{n}^{m}=\mathscr{S}(\mathscr{C}_{mn}\times(\mathscr{C}_{2mn})^{d-1})$,
$n=1,2,\dots$, for a fixed $m>1$, is an admissible polynomial mesh for
$B_{d}$, with constant $c=(c_{m})^{d}$.

Proof. For every $p\in\mathbb{P}_{n}$, it is easily seen by basic
trigonometric identities that the composed function $p\circ\mathscr{G}$
belongs to an algebraic-trigonometric tensorial space on the box
$J=[0,1]\times[0,\pi]^{d-1}\times[0,2\pi]=\mathscr{U}([-1,1]^{d})$, namely

$p\circ\mathscr{G}\in\mathbb{P}_{n}^{1}\bigotimes\mathbb{T}_{n}([0,\pi])\bigotimes\dots\bigotimes\mathbb{T}_{n}([0,\pi])\bigotimes\mathbb{T}_{n}([0,2\pi])\;.$

Moreover, $\|p\|_{B_{d}}=\|p\circ\mathscr{G}\|_{J}$ by surjectivity of
$\mathscr{G}$. Then, reasoning component by component by using the univariate
version of Lemma 1 and iteratively Lemma 3, it is immediate to write

$\|p\|_{B_{d}}=\|p\circ\mathscr{G}\|_{J}\leq(c_{m})^{d}\|p\circ\mathscr{G}\|_{\mathscr{U}(\mathscr{C}_{mn}\times(\mathscr{C}_{2mn})^{d-1})}$
$=(c_{m})^{d}\|p\circ\mathscr{S}\|_{\mathscr{C}_{mn}\times(\mathscr{C}_{2mn})^{d-1}}=(c_{m})^{d}\|p\|_{X_{n}^{m}}\;.\hskip
28.45274pt\square$

###### Proposition 3

Let $X_{n}^{m}=\mathscr{S}(\mathscr{C}_{mn}\times(\mathscr{C}_{2mn})^{d-1})$
be a polynomial admissible mesh of the $d$-ball $K=B_{d}$ as in Lemma 4, and
$L_{n}:C(K)\to\mathbb{P}_{n}$ a linear projection operator with the structure
defined in Proposition 1. Then, the following estimate holds for every $m>1$

$\|\lambda_{n}\|_{X_{n}^{m}}\leq\|L_{n}\|\leq(c_{m})^{d}\|\lambda_{n}\|_{X_{n}^{m}}\;.$
(17)

Proof. Again (see Proposition 2), we can proceed exactly as in the proof of
Proposition 1, simply by substituting $c_{m}$ with $(c_{m})^{d}$. $\square$

We can finally observe that in view of (18), the considerations in Remark 3
apply also to the case of the ball.

###  2.4 General polynomial meshes

In the case of more general compact sets, we can still get a fully discrete
but less accurate approximation of Lebesgue constants by polynomial meshes,
based on the approach developed in [56] for polynomial optimization.

###### Proposition 4

Let $K\subset\mathbb{R}^{d}$ be a compact set, $\\{X_{n}\\}$ a polynomial
admissible mesh of $K$, and $L_{n}:C(K)\to\mathbb{P}_{n}$ a linear projection
operator with the structure defined in Proposition 1. Then, the following
estimates hold for every $m\geq 1$

$\|\lambda_{n}\|_{X_{mn}}\leq\|L_{n}\|\leq c^{1/m}\|\lambda_{n}\|_{X_{mn}}\;.$
(18)

Proof. First, observe that by definition of polynomial mesh, for every
$p\in\mathbb{P}_{n}$ and for every $m\geq 1$ we can write

$\|p\|_{K}\leq c^{1/m}\|p\|_{X_{mn}}\;,$

since $p^{m}\in\mathbb{P}_{mn}$ and $\|p^{m}\|_{K}=\|p\|_{K}^{m}\leq
C\|p^{m}\|_{X_{mn}}=C\|p\|_{X_{mn}}^{m}$. Then we can reason as in the proof
of Proposition 1 to reach the conclusion, with $c^{1/m}$ substituting $c_{m}$.
$\square$

###### Remark 6

Notice that $c^{1/m}\to 1$ and thus again, if the sampling set $\Xi$ is
independent of $m$, $\|\lambda_{n}\|_{X_{mn}}\to\|L_{n}\|$ as $m\to\infty$.
Moreover, from (18) we also get a relative error estimate, namely

$\frac{\|L_{n}\|-\|\lambda_{n}\|_{X_{mn}}}{\|L_{n}\|}\leq e^{\log(c)/m}-1\leq
e^{\log(c)/m}\,\frac{\log(c)}{m}$ (19)

by the mean value theorem and the monotonicity of the exponential function,
that is a $\mathscr{O}(1/m)$ relative approximation of the Lebesgue constant
by $\|\lambda_{n}\|_{X_{mn}}$. Again, (18) gives also the rigorous and
computable absolute error estimate
$0\leq\|L_{n}\|-\|\lambda_{n}\|_{X_{mn}}\leq(c^{1/m}-1)\|\lambda_{n}\|_{X_{mn}}$.
Notice that also in this general case we may resort to the midpoint
approximation $\Lambda_{X_{mn}}=\|\lambda_{n}\|_{X_{mn}}(1+c^{1/m})/2$ whose
relative error estimate is improved by a factor $1/2$, namely
$|\,\|L_{n}\|-\Lambda_{X_{mn}}\,|/\|L_{n}\|\leq(c^{1/m}-1)/2$.

##  3 Numerical examples

###  3.1 Computational issues

We make some observations on the main computational issues. Dealing with
polynomial projectors, most computations can be seen as a matter of numerical
linear algebra, by standard algorithms applied to the relevant Vandermonde-
like matrices. Indeed, given a finite set of points
$Z=\\{z_{1},\dots,z_{k}\\}$, and selected a polynomial basis
$[p_{1}(x),\dots,p_{N}(x)]$ of $\mathbb{P}_{n}$, we can construct the matrix

$V_{n}(Z)=[p_{j}(z_{i})]\;,\;1\leq i\leq k\;,\;1\leq j\leq N\;.$ (20)

In order to control the conditioning of such matrices, that becomes
unacceptable already at moderate degrees with the standard monomial basis, we
have chosen to use a total-degree product Chebyshev basis corresponding to the
minimal enclosing box, say $[a_{1},b_{1}]\times\dots\times[a_{d},b_{d}]$,
namely $p_{j}(x)=\prod_{s=1}^{d}T_{m_{s}}(\alpha_{s}x_{s}+\beta_{s})$ where
$\alpha_{s}=(b_{s}-a_{s})/2$, $\beta_{s}=(b_{s}+a_{s})/2$ and
$T_{m_{s}}(\cdot)=\cos(m_{s}\arccos(\cdot))$ is the standard Chebyshev
polynomial of the second-kind for degree $m_{s}$. Here $j=1,\dots,N$
corresponds to some ordering (for example a lexicographical ordering) of the
$d$-uples $(m_{1},\dots,m_{d})$, $0\leq m_{1}+...+m_{d}\leq n$.

Alternatively, when known one could adopt orthonormal polynomial bases with
respect to some continuous measure with density on the specific domain, such
as the Logan-Shepp or the Zernike basis for the disk [60], the Dubiner basis
for the 2-simplex [26].

Notice that, in view of (8), the Lebesgue constant on the mesh of either an
interpolation or weighted least-squares projection operator, can then be
simply computed via the relevant matrices as

$\|\lambda_{n}\|_{X_{n}^{m}}=\max_{i}\sum_{j}w_{j}\left|\sum_{k}\pi_{k}(x_{i})\pi_{k}(\xi_{j})\right|=\|V_{n}(X_{n}^{m})R^{-1}Q^{t}diag(\sqrt{W})\|_{\infty}\;,$
(21)

where $\Xi=\\{\xi_{j}\\}$ are either the interpolation or the weighted least-
squares sampling points, and

$diag(\sqrt{W})\,V_{n}(\Xi)=QR$ (22)

the factorization of the corresponding weighted Vandermonde-like matrix, with
$Q$ (rectangular) orthogonal and $R$ square upper-triangular, that is

$[\pi_{1}(x),\dots,\pi_{N}(x)]=[p_{1}(x),\dots,p_{N}(x)]R^{-1}$ (23)

is the corresponding discrete orthonormal polynomial basis in
$\ell^{2}_{W}(\Xi)$.

To have an idea of the approximation quality, we report here a table of the
relative error estimates using the midpoint approximation (cf. (6), with
$c_{m}^{d}$ replacing $c_{m}$ for simplex and ball). Observe that to get an
error below 10%, that is to recover the Lebesgue constant with one correct
figure thus computing accurately its order of magnitude (which is the relevant
parameter in applications), one can take $m=3$ for the $d$-cube, $m=4$ in
$d=2$ for simplex and disk, and $m=5$ in $d=3$ for simplex and ball (in all
cases the error is around $8\%$).

$m$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---
$c_{m}-1$ | 11% | 7.7% | 4.1% | 2.6% | 1.8% | 1.3% | 0.98% | 0.77 % | 0.62%
$c_{m}^{2}-1$ | 50% | 17% | 8.6% | 5.3% | 3.6% | 2.6% | 2.0% | 1.6% | 1.3%
$c_{m}^{3}-1$ | 90% | 27% | 13% | 8.1% | 5.5% | 4.0% | 3.0% | 2.4% | 1.9%
Table 1: Relative error estimates in the approximation of the Lebesgue
constants on Chebyshev polynomial meshes $X_{n}^{m}$: $d$-cube (first row),
2-simplex and disk (second row), 3-simplex and ball (third row).

We observe that the present fully discrete approach for Lebesgue constants
evaluation, being based on product Chebyshev meshes of cardinality
$\mathscr{O}((mn)^{d})$, suffers of the curse of dimensionality and hence is
essentially a low-dimensional tool. Considering for example the polynomial
meshes corresponding to (transformed) grids of Chebyshev points, which are in
the interior of the domains, the cardinalities are exactly $(mn)^{d}$ for the
$d$-cube and the $d$-simplex, and $2^{d-1}(mn)^{d}$ for the $d$-ball. To have
an idea of the sizes, we plot in Figure 1 the values of the cardinality
corresponding to the choices of $m$ suggested above, for a range of polynomial
degrees in dimension $d=2$ and $d=3$.

Figure 1:  Cardinalities (log scale) of some Chebyshev polynomial meshes in
dimension $d=2,3$ for degree $n=1,2,\dots,30$ (Lebesgue constant approximated
at less than $10\%$, cf. Table 1): $(mn)^{d}$ with $m=3$ ($d$-cube,
$\square$), $m=4$ (2-simplex, $\triangle$) and $m=5$ (3-simplex, $\lozenge$);
$2^{d-1}(mn)^{d}$ with $m=4$ (disk, o) and $m=5$ (ball, $\ast$).

Below we show a number of numerical tests in dimension 1, 2 and 3. The
corresponding numerical codes and demos, implemented in Matlab, are freely
available at [33].

###  3.2 Univariate interpolation points

In the univariate case Lebesgue constants for interpolation on intervals have
been extensively studied, with a number of theoretical results and estimates;
cf. e.g. [14, 37] and the references therein. In order to test our method, we
compare here the computed Lebesgue constants of Chebyshev points, Gauss-
Legendre-Lobatto points (which are known to be Fekete points, i.e. points that
maximize the absolute value of the Vandermonde determinant) and Gauss-Legendre
points. The Lebesgue constant of the first two is known to be
$\mathscr{O}(\log(n))$, whereas the third is $\mathscr{O}(\sqrt{n})$.
Moreover, we also compute the Lebesgue constant of equally spaced points,
which is known to grow exponentially (cf. [39]). The results are collected in
Figure 2.

Figure 2:  Left: Lebesgue constants of some pointsets on the interval $[-1,1]$
for degrees $n=1,\dots,100$: Chebyshev (red dots), Legendre (blue line),
Legendre-Lobatto (cyan dashes), equispaced points (magenta dashes). Right: the
three lowest curves in detail. In these experiments, $m=3$ with a relative
error $\approx 7.7\%$.

###  3.3 Comparing interpolation points on the square

We compare here the computed Lebesgue constants of some well-known families of
interpolation points on the square. The results are collected in Figure 3.

The Padua points on the square, discovered in 2005 [15], are the union of two
suitable Chebyshev subgrids. They are the first and till now the only
explicitly known optimal point set for total-degree multivariate polynomial
interpolation. For such points it has indeed been proved that the Lebesgue
constant is $\mathscr{O}(\log^{2}(n))$; cf. [7].

The Morrow-Patterson points support one of the few known minimal positive
cubature formulas, namely a formula with $N$ nodes that has degree of
exactness $2n$ for the product Chebyshev measure of the second kind, cf. [40].
Hence, the hyperinterpolation polynomial of degree not greater than $n$ at
these points, in view of minimality, turns out to be exactly the interpolation
polynomial, by [48, Lemma 3]. For such points it is proved that the Lebesgue
constant is $\mathscr{O}(n^{3})$ and it is conjectured that the actual growth
is $\mathscr{O}(n^{2})$; cf. [21].

For the purpose of comparison we also compute the Lebesgue constant of $N$
Halton points. In view of the recent result [19], $N$ uniformly distributed
(random) points are almost surely unisolvent, the probability that
$det(V_{n}(\Xi))=0$ being null, but we expect that the Lebesgue constant has
exponential growth, as observed numerically. A theoretical explanation is that
a subexponential growth would imply weak-* convergence of the uniform discrete
probability measure supported at the interpolation points, to the potential
theoretic equilibrium measure of the compact set (that in this case is the
product Chebyshev measure); cf. [4]. On the contrary, with uniform random and
Halton points there is weak-* convergence to the Lebesgue measure (a fact that
is at the base of MonteCarlo and Quasi-MonteCarlo integration). The
exponential growth is clearly visible in Figure 3-left, and in all the figures
with uniform or Halton points as a trend up to some oscillations (in Figure
2-left where high degrees are considered, the behavior becomes numerically
erratic when the Lebesgue constant goes beyond a size around $10^{17}$).

Figure 3:  Left: Lebesgue constants of some pointsets on the square
$[-1,1]^{2}$ for degrees $n=1,\dots,25$: Padua points (red dots), Morrow-
Patterson (blue dots), Halton points (cyan dashes). Right: the two lowest
curves in detail. In these experiments, $m=3$ with a relative error $\approx
7.7\%$.

###  3.4 Waldron points on the simplex

Good total-degree interpolation points on the simplex are relevant in the
numerical solution of PDEs by spectral and high-order methods, and for this
reason have been extensively investigated, in most cases numerically; cf. e.g.
[62] with the references therein.

Quite recently a promising theoretical approach has been proposed,
constructing the so-called Waldron points, that are obtained by looking for an
appropriate spacing with respect to a distance related to the equilibrium
measure of the domain (such as the Baran distance; cf. [11]). In Figure 4 we
compare the Lebesgue constant of the Waldron points for the 2-simplex with
that of the so-called Simplex Points (SIMP) (a triangular grid corresponding
to equally spaced points in the Euclidean distance on the equilateral
triangle), and two families of points corresponding to a greedy minimization
of the Lebesgue constant, the Approximate Lebesgue Points (ALP) and the
Symmetric Approximate Lebesgue Points (SALP). The SALP are useful in the
framework of spectral element methods for PDEs; cf. [13, 45].

We see that as expected with the Simplex Points there is an exponential
growth. On the other hand, the Lebesgue constant of ALP and SALP are slowly
increasing, whereas that of the Waldron points increase slowly up to about
degree $n=10$ and then it turns to a manifestly exponential growth (though
slower than with the Simplex Points).

Figure 4:  Left: Lebesgue constants of some pointsets on the unit simplex with
vertices $(0,0)$, $(1,0)$, $(0,1)$, for degrees $n=1,\dots,25$: ALP (cyan
dashes), SALP (blue line), Waldron points (red dots), simplex points (magenta
dashes). Right: the three lowest curves in detail. In these experiments, $m=4$
with a relative error $\approx 8.6\%$.

###  3.5 Approximate Fekete and Leja points

The cases where good interpolation sets are known analytically are very few.
Already in dimension $d=2$ to our knowledge there is no known explicit family
for the disk, and in $d=3$ the same can be said for cube and ball.

On the other hand, interpolation points with slowly increasing Lebesgue
constant can be determined numerically, for example the Approximate Fekete
Points (AFP) and the Discrete Leja Points (DLP), both corresponding to a
greedy maximization of the Vandermonde determinant modulus, typically
extracting such points from polynomial meshes by numerical linear algebra
algorithms; cf., e.g., [8, 9]. Moreover, for example in [13, 38] Approximate
Lebesgue Points (ALP) have been computed once and forall on square, simplex
and disk for restricted degree ranges, working heuristically just with
polynomial meshes and suitable greedy algorithms. Other pointsets with low
Lebesgue constant can be computed by the optimization algorithm proposed in
[55].

For the purpose of illustration, in Figures 5-7 we plot the computed Lebesgue
constants for interpolation at AFP, DLP and Halton points on disk, cube and
ball. The AFP and DLP have been computed on the same polynomial meshes
$X_{n}^{m}$ used for the Lebesgue constant evaluation. On the disk we also
consider the Carnicer-Godes interpolation points [17] and the Approximate
Lebesgue Points (ALP) computed in [38].

Figure 5:  Left: Lebesgue constants of some pointsets on the unit disk
$B_{2}$, for degrees $n=1,\dots,25$: AFP (red dots), DLP (blue dots), ALP
(cyan dashes), Carnicer-Godes (black dashes), Halton points (magenta dashes).
Right: the four lowest curves in detail. In these experiments, $m=4$ with a
relative error $\approx 8.6\%$.

Figure 6:  Left: Lebesgue constants of some pointsets on the cube
$[-1,1]^{3}$, for degrees $n=1,\dots,15$: AFP (red dots), DLP (blue dashes),
Halton points (cyan dashes). Right: the two lowest curves in detail. In these
experiments, $m=3$ with a relative error $\approx 7.7\%$.

Figure 7:  Left: Lebesgue constants of some pointsets on the unit ball
$B_{3}$, for degrees $n=1,\dots,10$: AFP (red dots), DLP (blue dashes), Halton
points (cyan dashes). Right: the two lowest curves in detail. In these
experiments, $m=5$ with a relative error $\approx 8.1\%$.

###  3.6 Standard and weighted least-squares

As observed in Remark 2, discrete least-squares operators, one of the very
basic tools of computational mathematics in both the standard (equally
weighted) and the weighted case, fall into the class of projectors where we
can evaluate the Lebesgue constant, i.e. their uniform norm, by polynomial
meshes.

It is worth recalling that a connection of (standard) least-squares with
polynomial meshes was already pointed out in [16], where it was shown that if
the sampling set is a polynomial mesh on $K$, say $\Xi=X_{n}$ with constant
$c$, then $\|L_{n}\|\leq c\sqrt{card(X_{n})}$. This is however only a rough
bound (as there observed), whereas estimating the actual size is important in
applications.

Concerning weighted least-squares, we may also recall that they include for
example hyperinterpolation operators (see Remark 2), as well as instances
coming from the recent topic of “compression” of discrete measures. Roughly
summarizing, given a discrete measure with large support, such a compression
corresponds to extract from the support a subset of re-weighted points, such
that the corresponding discrete measure keeps the same polynomial moments up
to a given degree. This topic has been receiving an increasing attention in
the literature of the last decade, in both the probabilistic and the
deterministic setting; cf., e.g., [12, 28, 30, 36, 42, 50, 54] with the
references therein.

In particular, for discrete least-squares approximation of degree $n$ on a
sampling set $\Xi$, moment matching has to be imposed up to degree $2n$, thus
preserving orthogonal polynomials and reproducing kernels. This can be
obtained by seeking a sparse nonnegative solution to the underdetermined
moment-matching system $V_{2n}^{t}(\Xi)w=V_{2n}^{t}(\Xi)u$, where
$u=(1,\dots,1)^{t}$. Such a solution with no more than
$N_{2n}=dim(\mathbb{P}_{2n})$ nonzero components exists, by the well-known
Caratheodory theorem on conical combinations applied to the columns of the
matrix, and can be computed by solving the NonNegative Least Squares (NNLS)
problem

$\min_{u\geq 0}\|V_{2n}^{t}(\Xi)w-V_{2n}^{t}(\Xi)u\|_{2}$ (24)

via the Lawson-Hanson NNLS-solver [35] and its accelerated variants, such as
that based on the recently developed “deviation maximization” criterion
instead of column pivoting in the underlying $QR$ factorizations (cf. [20, 23,
24, 25, 47]). The nonzero components of $w$ then determine a compressed
support $\Xi_{n}\subset\Xi$ with $N_{n}\leq card(\Xi_{n})\leq N_{2n}$, where
the weighted least-squares polynomial can be computed; cf. [42].

For the purpose of illustration, in Figures (8)-(9) we compare on square and
disk the Lebesgue constants of hyperinterpolation and of polynomial least-
squares on Halton points and on Chebyshev polynomial meshes for degrees
$n=1,\dots,20$, together with their compressed versions. To give an idea of
the compression ratios, those on the disk are reported in Table 2. We recall
that in the case of hyperinterpolation it is theoretically known that the
Lebesgue constant is $\mathscr{O}(n^{2})$ for the square and $\mathscr{O}(n)$
for the disc with the Lebesgue measure, and $\mathscr{O}(\log^{2}(n))$ for the
square with the product Chebyshev measure; cf. e.g. [21, 59, 61].

It is numerically manifest that Lebesgue constants of full and compressed
least-squares have substantially the same size, with a remarkable reduction of
the sampling cardinality for the latter. Moreover, the Lebesgue constant of
least-squares on Chebyshev meshes and of hyperinterpolation with the product
Chebyshev measure turn out to be very close (see Figure 8). This is not really
surprising, since the uniform discrete measure supported at univariate
Chebyshev points is an algebraic quadrature formula for the (normalized)
Chebyshev measure, and such a behavior extends to a product-like framework.
Hence, standard discrete least-squares on a Chebyshev mesh of the square are
equivalent to an hyperinterpolation with respect to the product Chebyshev
measure, whose Lebesgue constant is expected to be $\mathscr{O}(\log^{2}(n))$
in view of [61]. The same can be said for the compressed least-squares, since
they also correspond to an algebraic quadrature with the same moments up to
degree $2n$. Notice that the Lebesgue functions of standard and compressed
least-squares are not coincident, but both correspond to hyperinterpolation
with respect to the product Chebyshev measure.

A similar argument applies in interpreting Figure 9, since standard discrete
least-squares on a polar Chebyshev mesh of the disk are equivalent to an
hyperinterpolation with respect to its equilibrium measure
$dx_{1}\,dx_{2}/(\pi\sqrt{1-x_{1}^{2}-x_{2}^{2}})=r\,dr\,d\theta/(\pi\sqrt{1-r^{2}})$,
whose Lebesgue constant is expected to be $\mathscr{O}(\sqrt{n})$ in view of
[59].

Figure 8:  Left: Lebesgue constants of least-squares on the square
$[-1,1]^{2}$, for degrees $n=1,\dots,20$, on: 10000 Halton points (HAL, red
dots) and compressed version (HALC, red dashes); Chebyshev mesh
$X_{20}^{5}=\mathscr{C}_{100}\times\mathscr{C}_{100}$ with 10000 points (blue
line, AM20) and compressed version (AM20C, blue dashes); hyperinterpolation
with product Gauss-Chebyshev quadrature (HYP, cyan line). Right: the three
lowest curves in detail. In these experiments, $m=3$ with a relative error
$\approx 7.7\%$.

Figure 9:  Left: Lebesgue constants of least-squares on the unit disk $B_{2}$, for degrees $n=1,\dots,20$, on: 12800 Halton points (HAL, red dots) and compressed version (HALC, red dashes); Chebyshev mesh $X_{20}^{4}=\mathscr{S}(\mathscr{C}_{80}\times\mathscr{C}_{160})$ with 12800 points (AM20, blue line) and compressed version (AM20C, blue dashes); hyperinterpolation via low cardinality rules for the Lebesgue measure (HYP, cyan line). Right: the three lowest curves in detail. In these experiments, $m=4$ with a relative error $\approx 8.6\%$. $n$ | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20
---|---|---|---|---|---|---|---|---|---|---
$card=N_{2n}$ | 15 | 45 | 91 | 153 | 231 | 325 | 435 | 561 | 703 | 861
$cmp\;ratio$ | 853 | 284 | 141 | 84 | 55 | 40 | 29 | 23 | 18 | 15
Table 2: Cardinalities and sampling compression ratios for compressed
polynomial LS of degree $n$ on 12800 points of the disk.

Acknowledgements. Work partially supported by the DOR funds of the University
of Padova, by the INdAM-GNCS grant “Multivariate approximation and integration
with application to integral equations” (A. Sommariva, M. Vianello), and by
the National Science Center - Poland, grant Preludium Bis 1, N.
2019/35/O/ST1/02245 (D.J. Kenne). The research cooperation was funded by the
program Excellence Initiative – Research University at the Jagiellonian
University in Krakòw (A. Sommariva). This research has been accomplished
within the RITA “Research ITalian network on Approximation” and the SIMAI
Activity Group ANA&A (A. Sommariva, M. Vianello), and the UMI Group TAA
“Approximation Theory and Applications” (A. Sommariva).

## References

  * [1] C. An, H.-N. Wu, Lasso hyperinterpolation over general regions, SIAM J. Sci. Comput. 43 (2021), A3967–A3991.
  * [2] L. Białas-Cież, J.P. Calvi, Pseudo Leja sequences, Annali di Matematica 191 (2012), 53–75.
  * [3] L. Białas-Cież, J.P. Calvi, Invariance of polynomial inequalities under polynomial maps, J. Math. Anal. Appl. 439 (2016), 449–464.
  * [4] T. Bloom, L. Bos, J.-P. Calvi, N. Levenberg, Polynomial Interpolation and Approximation in $C^{d}$, Ann. Polon. Math. 106 (2012), 53–81.
  * [5] L.E. Blumenson, A Derivation of n-Dimensional Spherical Coordinates, Amer. Math. Monthly 67 (1960), 63–66.
  * [6] L. Bos, A Simple Recipe for Modelling a d-cube by Lissajous curves, Dolomites Res. Notes Approx. DRNA 10 (2017), 1–4.
  * [7] L. Bos, M. Caliari, S. De Marchi, M. Vianello, Y. Xu, Bivariate Lagrange interpolation at the Padua points: the generating curve approach, J. Approx. Theory 143 (2006), 15–25.
  * [8] L. Bos, J.P. Calvi, N. Levenberg, A. Sommariva, M. Vianello, Geometric Weakly Admissible Meshes, Discrete Least Squares Approximations and Approximate Fekete Points, Math. Comp. 80 (2011), 1601–1621.
  * [9] L. Bos, S. de Marchi, A. Sommariva, M. Vianello, Computing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Numer. Anal. 48 (2010), 1984–1999.
  * [10] L. Bos, N. Levenberg, S. Waldron, Pseudometrics, distances and multivariate polynomial inequalities, J. Approx. Theory 153 (2008), 80–96.
  * [11] L. Bos, S. Ma’u, S. Waldron, On Waldron Interpolation on a Simplex in $\mathbb{R}^{d}$, arXiv:2306.08392.
  * [12] L. Bos, F. Piazzon, M. Vianello, Near G-optimal Tchakaloff designs, Comput. Statistics 35 (2020), 803–819.
  * [13] M. Briani, A. Sommariva, M. Vianello, Computing Fekete and Lebesgue points: simplex, square, disk, J. Comput. Appl. Math. 236 (2012), 2477–2486.
  * [14] L. Brutman, Lebesgue functions for polynomial interpolation—a survey, Ann. Numer. Math. 4 (1997), 111–127.
  * [15] M. Caliari, S. De Marchi, M. Vianello, Bivariate polynomial interpolation on the square at new nodal sets, Appl. Math. Comput. 165/2 (2005), 261–274.
  * [16] J.P. Calvi, N. Levenberg, Uniform approximation by discrete least squares polynomials, J. Approx. Theory 152 (2008), 82–100.
  * [17] J. Carnicer, C. Godes, Interpolation on the disk, Numer. Algorithms 66 (2014), 1–16.
  * [18] F. Dai, A. Prymak, Optimal Polynomial Meshes Exist on any Multivariate Convex Domain, Found Comput Math (2023), https://doi.org/10.1007/s10208-023-09606-x.
  * [19] F. Dell’Accio, A. Sommariva, M. Vianello, Random sampling and unisolvent interpolation by almost everywhere analytic functions, Appl. Math. Lett. 145 (2023).
  * [20] M. Dell’Orto, M. Dessole, F. Marcuzzi, The Lawson-Hanson Algorithm with Deviation Maximization: Finite Convergence and Sparse Recovery, Numer. Linear Algebra Appl. 30(5) (2023).
  * [21] S. De Marchi, A. Sommariva, M. Vianello, Multivariate Christoffel functions and hyperinterpolation, Dolomites Res. Notes Approx. DRNA 7 (2014), 26–33.
  * [22] S. De Marchi, M. Vianello, Y. Xu, New cubature formulae and hyperinterpolation in three variables, BIT Numerical Mathematics 49 (2009), 55–73.
  * [23] M. Dessole, F. Marcuzzi, Deviation maximization for rank-revealing QR factorizations, Numer. Algorithms 91 (2022), 1047-1079.
  * [24] M. Dessole, F. Marcuzzi, M. Vianello, Accelerating the Lawson-Hanson NNLS solver for large-scale Tchakaloff regression designs, Dolomites Res. Notes Approx. DRNA 13 (2020), 20–29.
  * [25] M. Dessole, F. Marcuzzi, M. Vianello, dCATCH: a numerical package for d-variate near G-optimal Tchakaloff regression via fast NNLS, MDPI-Mathematics 8(7) (2020) - Special Issue ”Numerical Methods”.
  * [26] M. Dubiner, Spectral methods on triangles and other domains, J. Sci. Comput. 6 (1991), 345–390.
  * [27] J. Dugundji, Topology, Allyn&Bacon, Boston, 1966.
  * [28] G. Elefante, Sommariva, M. Vianello, CQMC: an improved code for low-dimensional Compressed Quasi-MonteCarlo cubature, Dolomites Res. Notes Approx. DRNA 15 (2022) (Special Issue ”Software for Approximation 2022”, 92–100).
  * [29] M. Festa, A. Sommariva, Computing almost minimal formulas on the square, J. Comput. Appl. Math. 236 (2012), 4296–4302.
  * [30] S. Hayakawa, Monte Carlo cubature construction, Jpn. J. Ind. Appl. Math. 38 (2021) 561–577.
  * [31] O. Hansen, K. Atkinson, D. Chien, On the norm of the hyperinterpolation operator on the unit disc and its use for the solution of the nonlinear Poisson equation, IMA J. Numer. Anal. 29 (2009), 257–283.
  * [32] K. Hesse, I.H. Sloan, Hyperinterpolation on the sphere, Frontiers in interpolation and approximation, 213–248, Pure Appl. Math. (Boca Raton), 282, Chapman & Hall/CRC, Boca Raton, FL, 2007.
  * [33] D. Kenne, A. Sommariva, M. Vianello, LEBEVAL: Matlab codes for Lebesgue constant evaluation on interval, square, disk, cube, simplex and ball, https://github.com/alvisesommariva/LEBEVAL.
  * [34] A. Króo, On optimal polynomial meshes, J. Approx. Theory 163 (2011), 1107–1124.
  * [35] C.L. Lawson, R.J. Hanson, Solving least squares problems, revised reprint of the 1974 original, SIAM, Philadelphia, 1995.
  * [36] C. Litterer, T. Lyons, High order recombination and an application to cubature on Wiener space, Ann. Appl. Probab. 22 (2012) 1301–1327.
  * [37] G. Mastroianni, G.V. Milovanovic, Interpolation Processes: Basic Theory and Applications, Springer, 2008.
  * [38] G. Meurant, A. Sommariva, On the computation of sets of points with low Lebesgue constant on the unit disk, J. Comput. Appl. Math. 345 (2019), 388–404.
  * [39] T.M. Mills, S.J. Smith, The Lebesgue constant for Lagrange interpolation on equidistant nodes, Numer. Math. 61 (1992), 111–115.
  * [40] C.R. Morrow and T.N. Patterson, Construction of algebraic cubature rules using polynomial ideal theory, SIAM J. Numer. Anal. 15 (1978), 953–976.
  * [41] M. Petitjean, Spheres Unions and Intersections and Some of their Applications in Molecular Modeling, in: A. Mucherino & al., Eds., Distance Geometry: Theory, Methods, and Applications, Springer New York, 2013, pp. 61–83.
  * [42] F. Piazzon, A. Sommariva, M. Vianello, Caratheodory-Tchakaloff Least Squares, Sampling Theory and Applications 2017, IEEE Xplore Digital Library, DOI: 10.1109/SAMPTA.2017.8024337.
  * [43] F. Piazzon, M. Vianello, Small perturbations of polynomial meshes, Appl. Anal. 92 (2013), 1063–1073.
  * [44] F. Piazzon, M. Vianello, A note on total degree polynomial optimization by Chebyshev grids, Optim. Lett. 12 (2018), 63–71.
  * [45] F. Rapetti, A. Sommariva, M. Vianello, On the generation of symmetric Lebesgue-like points in the triangle, J. Comput. Appl. Math. 236 (2012), 4925–4932.
  * [46] E. Schönhardt, Über die Zerlegung von Dreieckspolyedern in Tetraeder, Mathematische Annalen 98 (1928), 309–312.
  * [47] M. Slawski, Nonnegative least squares: comparison of algorithms. Paper and code available online at: https://sites.google.com/site/slawskimartin/code.
  * [48] I.H. Sloan, Interpolation and hyperinterpolation over general regions, J. Approx. Theory 83 (1995), 238–254.
  * [49] A. Slobodkins, J. Tausch, A node elimination algorithm for cubature of high-dimensional polytopes, Comput. Math. Appl. 144 (2023), 229–236.
  * [50] A. Sommariva, M. Vianello, Polynomial fitting and interpolation on circular sections, Appl. Math. Comput. 258 (2015), 410–424.
  * [51] A. Sommariva, M. Vianello, Compression of multivariate discrete measures and applications, Numer. Funct. Anal. Optim. 36 (2015), 1198–1223.
  * [52] A. Sommariva, M. Vianello, Numerical hyperinterpolation over nonstandard planar regions, Math. Comput. Simulation 141 (2017), 110–120.
  * [53] N. Takaki, G.W. Forbes, J.P. Rolland, Schemes for cubature over the unit disk found via numerical optimization, J. Comput. Appl. Math. 407 (2022), 114076.
  * [54] M. Tchernychova, Caratheodory cubature measures. Ph.D. dissertation in Mathematics (supervisor: T. Lyons), University of Oxford, 2015.
  * [55] M. Van Barel, M. Humet, L. Sorber, Approximating optimal point configurations for multivariate point configurations, Electron. Trans. Numer. Anal. 42 (2014), 41–63.
  * [56] M. Vianello, An elementary approach to polynomial optimization on polynomial meshes, J. Math. Fund. Sci. 50 (2018), 84–91.
  * [57] M. Vianello, Subperiodic Dubiner distance, norming meshes and trigonometric polynomial optimization, Optim. Lett. 12 (2018), 1659–1667.
  * [58] M. Vianello, Dubiner distance and stability of Lebesgue constants, J. Inequal. Spec. Funct. 10-2 (2019), 49–60.
  * [59] J. Wade, On hyperinterpolation on the unit ball, J. Math. Anal. Appl. 401 (2013), 140–145.
  * [60] S. Waldron, Orthogonal polynomials on the disc, J. Approx. Th. 50 (2008), 117–131.
  * [61] H. Wang, K. Wang, X. Wang, On the norm of the hyperinterpolation operator on the d-dimensional cube, Comput. Math. Appl. 68 (2014), 632–638.
  * [62] T. Warburton, An explicit construction of interpolation nodes on the simplex, J. Eng. Math. 56 (2006), 247–262.


#  Generalized Cayley graphs of complete groups††thanks: This research was
supported by NSFC (No. 12071484). E-mail addresses: liaoqianfen@163.com(Q.
Liao), wjliu6210@126.com(W. Liu, corresponding author).

Qianfen Liaoa, Weijun Liub,c
a. Department of Mathematics, Guangdong University of Education,
Guangzhou, Guangdong, 510303, P.R. China.
b. School of Mathematics and Statistics, Central South University,
Changsha, Hunan, 410083, P.R. China.
c. College of General Education, Guangdong University of Science and
Technology,
Dongguan Guangdong, 523083, P.R. China.

###### Abstract

A group $G$ is complete group if it satisfies $Z(G)=e$ and $Aut(G)=Inn(G)$. In
this paper, on the one hand, we study the basic properties of generalized
Cayley graphs and characterize two classes isomorphic generalized generalized
Cayley graphs of complete groups. On the other hand, we give the sufficient
and necessary conditions of complete group to be $GCI$ group and restricted
$GCI$ group. As an application, we complete the classification of restricted
$GCI$-groups for symmetric groups.

Key words: generalized Cayley graph; complete group.

##  1 Introduction

The generalized Cayley graph, as a generalization of the Cayley graph, was
first proposed in 1992 by D. Marušič et al. [5].

######  Definition 1.1.

Given a finite group $G$, for $S\subseteq G$ and
$\alpha\in{\rm\textsf{Aut}}(G)$, if they satisfy several conditions below:

  1. (a)

$\alpha^{2}=\mathrm{id}$, where $\mathrm{id}$ is the identity of
${\rm\textsf{Aut}}(G)$;

  2. (b)

for any $g\in G$, $(g^{-1})^{\alpha}g\notin S$;

  3. (c)

for $g,h\in G$, if $(h^{-1})^{\alpha}g\in S$, then $(g^{-1})^{\alpha}h\in S$.

Then the graph with vertices $G$ and edges
$\\{\\{g,h\\}\mid(g^{-1})^{\alpha}h\in S\\}$ is denoted by $GC(G,S,\alpha)$.
We call $S$ a generalized Cayley subset and $GC(G,S,\alpha)$ a generalized
Cayley graph of $G$ with respect to the ordered pair $(S,\alpha)$.

Some basic properties about $GC(G,S,\alpha)$ deserve to be mentioned. Firstly,
$GC(G,S,\alpha)$ is a simple and undirected graph. Secondly, for each vertex
$g\in G$, the set of vertices that adjacent to $g$ is $N(g)=\\{g^{\alpha}s\mid
s\in S\\}$, so $GC(G,S,\alpha)$ is $|S|$-regular. Thirdly, the subsets
$\omega_{\alpha}=\\{(g^{-1})^{\alpha}g\mid g\in G\\}$,
$\Omega_{\alpha}=\\{g\mid
g^{\alpha}=g^{-1}~{}\text{and}~{}g\notin\omega_{\alpha}\\}$ and
$\mho_{\alpha}=\\{g\mid g^{\alpha}\neq
g^{-1}\\}=G\setminus\\{\omega_{\alpha}\cup\Omega_{\alpha}\\}$ construct a
partition of $G$. In addition, for generalized subset $S$, the condition $(b)$
implies that $S\cap\omega_{\alpha}=\emptyset$ and the condition (c) yields
that $\alpha(S)=S^{-1}$. Hence, if $s\in S\cap\mho_{\alpha}$, then
$\alpha(s^{-1})\in S$. At last, the condition (a) above implies that $\alpha$
is id or an involutory automorphism of $G$. Particularly, if
$\alpha=\mathrm{id}$, $S$ is called a Cayley subset and it gives the Cayley
graph.

As is well-known, Cayley graphs are vertex-transitive, but the generalized
Cayley graphs may not be. Marušič et al. provide specific examples in the
article to illustrate this point. In fact, vertex-transitive generalized
Cayley graphs are rare. Hujdurović et al. [2] construct a series of non-Cayley
vertex-transitive generalized Cayley graphs. Subsequently, to investigate the
isomorphism problem of generalized Cayley graphs, Yang, Liu and Feng [7]
introduce the definitions of $GCI$ groups and restricted $GCI$ groups. Then
$GCI$ groups and restricted $GCI$ groups for certain special groups have been
studied, including cyclic groups, dihedral groups, alternating groups and non-
abelian simple groups, see references [4, 6, 8].

A group $G$ is complete group if it satisfies $Z(G)=e$ and $Aut(G)=Inn(G)$. In
this paper, we study the basic properties of generalized Cayley graphs of
complete group. As an application, we complete the classification of
restricted $GCI$-groups for symmetric groups.

We introduce some notations in group theory. For a group $G$ and element $g\in
G$, let $C_{G}(g)=\\{h\in G\mid hg=gh\\}$ be the centralizer of $g$ in $G$,
and $Z(G)=\\{h\in G\mid gh=hg~{}\text{for all}~{}g\in G\\}=\cap_{g\in
G}C_{G}(g)$ the central of $G$. Given a subset $H$ of $G$, let
$N_{G}(H)=\\{g\in G\mid Hg=gH\\}$ be the normalizer of $H$ in $G$. Two
elements $g$ and $h$ are conjugate in $G$ if there exists element $x\in G$
such that $g=xhx^{-1}$. Let $C(g)$ be the conjugate class containing $G$, that
is the set of elements that conjugate to $g$. Then $|C(g)|=|G:C_{G}(g)|$. The
conjugate relation is an equivalent relation, and $G$ can be divided into some
disjoint conjugate classes. Let $[g,h]=g^{-1}h^{-1}gh$ be the commutator of
elements $g$ and $h$. For each element $g\in G$, let $\sigma(g):h\mapsto
h^{g}=ghg^{-1}$ be the inner automorphism of $G$ induced by $g$. Then
$Inn(G)=\\{\sigma(g)\mid g\in G\\}$ is an subgroup of $Aut(G)$ and called the
inner automorphism group of $G$. Let $\alpha$ and $\beta$ be permutations on
$G$, for any $g\in G$, define $g^{\beta\alpha}=(g^{\alpha})^{\beta}$. In the
following discussion of this paper, we assume that $G$ is complete group and
all generalized Cayley graphs are induced by some involutory automorphism.

##  2 Basic properties

In this section, we study the properties of generalized Cayley graphs of
complete graphs. Firstly, some observations about the involutory automorphism
of complete group $G$ are presented.

######  Observation 2.1.

For $g\in G$, $\sigma(g)$ is involutory automorphisms of $G$ if and only if
$g$ is involution of $G$.

######  Observation 2.2.

The automorphisms $\sigma(g)$ and $\sigma(h)$ of $G$ are conjugate in $Aut(G)$
if and only if $g$ and $h$ are conjugate in $G$.

###### Proof.

If $\sigma(g)$ and $\sigma(h)$ are conjugate in $Aut(G)$, let $\sigma(y)$ be
an automorphism of $G$ such that
$\sigma(h)=\sigma(y)\sigma(g)(\sigma(y))^{-1}$. Since
$(\sigma(y))^{-1}=\sigma(y^{-1})$, we obtain that for any element $x\in G$,

$x^{\sigma(h)}=hxh^{-1}=x^{\sigma(y)\sigma(g)\sigma(y^{-1})}=ygy^{-1}xyg^{-1}y^{-1}=(ygy^{-1})x(gyy^{-1})^{-1}.$

It follows that $h^{-1}(ygy^{-1})\in C_{G}(x)$. From the arbitrary of $x$, we
have $h^{-1}(ygy^{-1})\in Z(G)$. Recall that $G$ is complete group, then
$Z(G)=e$, which yields that $h=ygy^{-1}$.

Conversely, if $g$ and $h$ are conjugate in $G$, which means there exists
element $x$ such that $g=xhx^{-1}$. It can be verified that
$\sigma(g)=\sigma(xhx^{-1})=\sigma(x)\sigma(h)\sigma(x)^{-1}$. Thus,
$\sigma(g)$ and $\sigma(h)$ are conjugate. ∎

Let $\sigma(g)$ be any involutory automorphism of $G$, then we find the
relationship between subset $\mho_{\sigma(g)}(G)$ and the order of element.

######  Observation 2.3.

$x\in\mho_{\sigma(g)}(G)$ if and only if $gx$ is not involution of $G$.

###### Proof.

$x\in\mho_{\sigma(g)}(G)$ is equivalent to $x^{\sigma(g)}=gxg\neq x^{-1}$.
Since $gxg\neq x^{-1}$ is equivalent to $xg\neq(xg)^{-1}$, the proof is
complete. ∎

Let $K_{\sigma(g)}(G)=\omega_{\sigma(g)}(G)\cup\Omega_{\sigma(g)}(G)$. The
Observation 2.3 also indicates that $x\in K_{\sigma(g)}(G)$ if and only if
$gx$ is involution of $G$.

######  Lemma 2.4.

$g\in\Omega_{\sigma(g)}(G)$.

###### Proof.

Since $g^{\sigma(g)}=g$, $g\in\omega_{\sigma(g)}(G)\cup\Omega_{\sigma(g)}(G)$.
If $g=[g,h]$ for some $h\in G$, then $g=g^{-1}h^{-1}gh$. It follows that
$gh=h$ and then $g=e$, which is a contradiction. Thus,
$g\in\Omega_{\sigma(g)}(G)$. ∎

For any element $x\in G$, $L_{x}:h\mapsto xh$ for each $h\in G$ is a
permutation on $G$. For any generalized Cayley graph $GC(G,S,\sigma(g))$, we
find that there is a subgroup of $Aut(GC(G,S,\sigma(g)))$.

######  Proposition 2.5.

$L(C_{G}(g))\leq Aut(GC(G,S,\sigma(g)))$.

###### Proof.

For any element $x\in C_{G}(g)$ and $h_{1},h_{2}\in G$,

$\displaystyle((h_{1}^{L_{x}})^{-1})^{\sigma(g)}(h_{2}^{L_{x}})$
$\displaystyle=((xh_{1})^{-1})^{\sigma(g)}xh_{2}$
$\displaystyle=gh_{1}^{-1}x^{-1}g^{-1}xh_{2}$
$\displaystyle=gh_{1}^{-1}g^{-1}h_{2}=(h_{1}^{-1})^{\sigma(g)}h_{2}.$

Thus, $\\{h_{1}^{L_{x}},h_{2}^{L_{x}}\\}\in E(GC(G,S,\sigma(g)))$ if and only
if $\\{h_{1},h_{2}\\}\in E(GC(G,S,\sigma(g)))$, which implies $L_{x}\in
Aut(GC(G,S,\sigma(g)))$. Now we give an explanation for $L(C_{G}(g))$ is a
subgroup. For any elements $x,y\in C_{G}(g)$ and $h\in G$, according to
$h^{L_{x}L_{y}}=(h^{L_{y}})^{L_{x}}=xyh=h^{L_{xy}}$ and $xy\in C_{G}(g)$, it
follows that $L_{x}L_{y}=L_{xy}\in L(C_{G}(g))$. Furthermore, from
$L(x)L(x^{-1})=L(xx^{-1})=id$, we have $L(x)^{-1}=L(x^{-1})\in L(C_{G}(g))$.
Therefore, $L(C_{G}(g))$ is a subgroup of $Aut(GC(G,S,\sigma(g)))$. ∎

For any involutory automorphism $\alpha$ of $G$, let
$\mathrm{Fix}(\alpha)=\\{h\in G|h^{\alpha}=h\\}$ and we have the following
lemma.

######  Lemma 2.6.

$|\omega_{\alpha}(G)|=\frac{|G|}{\mathrm{Fix}(\alpha)}$.

With the help of Lemma 2.6, we obtain the following result.

######  Proposition 2.7.

The complete graph is not generalized Cayley graph of any complete group $G$.

###### Proof.

For any involutory automorphism $\sigma(g)$ of $G$, note that

$\mathrm{Fix}(\sigma(g))=\\{h\in G\mid h^{\sigma(g)}=ghg^{-1}=h\\}=\\{h\in
G\mid h^{-1}gh=g\\}=C_{G}(g),$

hence $|\omega_{\sigma(g)}(G)|=|G:C_{G}(g)|=|C(g)|$. It is clear that $g\in
C(g)$. We claim that $|C(g)|\neq 1$. Otherwise, $C(g)=g$, which means that for
any element $x\in G$, $xgx^{-1}=g$. It follows that $g\in Z(G)$, which
contrary to $G$ is complete group. Thus $|\omega_{\sigma(g)}(G)|=|C(g)|\geq 2$
and for any generalized Cayley subset $S$ of $G$, $|S|\leq|G|-2$ holds.
Therefore, any generalized Cayley graph of $G$ cannot be complete graph. ∎

##  3 Several classes isomorphic generalized Cayley graphs

In this section, we discuss the isomorphism problem of generalized Cayley
graphs of complete groups.

Let $g$ be an involution of $G$ and $\sigma(g)$ an involutory automorphism of
$G$. Define $[g]=\\{[g,h]\mid h\in G\\}$ and call it the set of commutators
induced by $g$. There is relationship between subset $\omega_{\sigma(g)}$ of
$G$ and $[g]$.

######  Observation 3.1.

$\omega_{\sigma(g)}=\\{(h^{-1})^{\sigma(g)}\mid h\in
G\\}=\\{gh^{-1}g^{-1}h\mid h\in G\\}=[g].$

Let $\sigma(g)$ be an involutory automorphism and $S$ a generalized Cayley
subset of $G$ induced by $\sigma(g)$. Then we obtain several classes
isomorphisms between generalized Cayley graphs.

######  Lemma 3.2.

For any element $x\in\Omega_{\sigma(g)}(G)$ and commutator $[g,h]\in[g]$,
$x^{-1}[g,h]x^{-1}=[g,hx^{-1}]$.

###### Proof.

Note that $x\in\Omega_{\sigma(g)}(G)$ implies that
$x^{\sigma(g)}=gxg^{-1}=x^{-1}$, hence $gx=x^{-1}g=x^{-1}g^{-1}$. Then

$x^{-1}[g,h]x^{-1}=x^{-1}g^{-1}h^{-1}ghx^{-1}=gxh^{-1}ghx^{-1}=[g,hx^{-1}].$

∎

######  Theorem 3.3.

For any $x\in\Omega_{\sigma(g)}(G)$, $GC(G,S,\sigma(g))\cong
GC(G,xSx,\sigma(g))$.

###### Proof.

As mentioned in the proof of Lemma 3.2, $x\in\Omega_{\sigma(g)}(G)$ implies
that $x^{\sigma(g)}=x^{-1}$. Since $S^{\sigma(g)}=S^{-1}$, we obtain that

$(xSx)^{\sigma(g)}=x^{\sigma(g)}S^{\sigma(g)}x^{\sigma(g)}=x^{-1}S^{-1}x^{-1}=(xSx)^{-1}.$

If $xSx\cap\omega_{\sigma(g)}(G)\neq\emptyset$, then there exists element
$s\in S$ such that $xsx=[g,h]$ for some $h\in G$. By Lemma 3.2,
$s=x^{-1}[g,h]x^{-1}=[g,hx^{-1}]\in[g]$, which is contrary to
$S\cap\omega_{\sigma(g)}(G)=\emptyset$. Thus, $xSx$ is a generalized Cayley
subset of $G$ induced by $\sigma(g)$. Define the map $\varphi:y\mapsto yx$ for
each $y\in G$. Clearly, $\varphi$ is one to one mapping between vertices of
$GC(G,S,\sigma(g))$ to $GC(G,xSx,\sigma(g))$. For any vertices $y_{1}$ and
$y_{2}$, since

$((y_{1}^{\varphi})^{-1})^{\sigma(g)}y_{2}^{\varphi}=(x^{-1}y_{1}^{-1})^{\sigma(g)}y_{2}x=(x^{-1})^{\sigma(g)}(y_{1}^{-1})^{\sigma(g)}y_{2}x=xgy_{1}^{-1}gy_{2}x=x((y_{1}^{-1})^{\sigma(g)}y_{2})x,$

$\\{y_{1}^{\varphi},y_{2}^{\varphi}\\}\in E(GC(G,xSx,\sigma(g)))$ if and only
if $\\{y_{1},y_{2}\\}\in E(GC(G,S,\sigma(g)))$. Therefore, we conclude that
$GC(G,S,\sigma(g))\cong GC(G,xSx,\sigma(g))$. ∎

######  Theorem 3.4.

For any element $x\in N_{G}(S)$, $GC(G,S,\sigma(g))\cong
GC(G,[g,x]S,\sigma(g))$.

###### Proof.

Note that

$([g,x]S)^{\sigma(g)}=g(g^{-1}x^{-1}gxS)g^{-1}=x^{-1}gxSg=x^{-1}gSxg$

as $xS=Sx$. Recall that $S^{\sigma(g)}=gSg=S^{-1}$, thus

$([g,x]S)^{-1}=(g^{-1}x^{-1}gxS)^{-1}=(g^{-1}x^{-1}gSx)^{-1}=(g^{-1}x^{-1}S^{-1}gx)^{-1}=x^{-1}gSxg.$

It indicates that $([g,x]S)^{\sigma(g)}=([g,x]S)^{-1}$. If
$[g,x]S\cap\omega_{\sigma(g)}(G)\neq\emptyset$, then there exists element
$s\in S$ such that $[g,x]s=[g,b]$ for some $b\in G$. This equality gives that
$s=x^{-1}g^{-1}xb^{-1}gb$. Since $xS=Sx$, there exists $s^{\prime}\in S$ such
that
$s^{\prime}=xsx^{-1}=g^{-1}xb^{-1}gbx^{-1}=[g,bx^{-1}]\in\omega_{\sigma(g)}(G)$,
which is a contradiction. Thus, $[g,x]S$ is a generalized Cayley subset of $G$
induced by $\sigma(g)$. Now we define the map $\varphi:h\mapsto hx$ for each
$h\in G$. For any elements $h_{1}$ and $h_{2}$ in $G$, observe that

$((h_{1}^{\varphi})^{-1})^{\sigma(g)}h_{2}^{\varphi}=gx^{-1}h_{1}^{-1}g^{-1}h_{2}x.$

If $\\{h_{1},h_{2}\\}\in E(GC(G,S,\sigma(g)))$, then
$(h_{1}^{-1})^{\sigma(g)}h_{2}=gh_{1}^{-1}g^{-1}h_{2}\in S$, which is
equivalent to $h_{1}^{-1}gh_{2}\in gS$. Assume that $h_{1}^{-1}gh_{2}=gs$ and
$sx=xs^{\prime}$, where $s,s^{\prime}\in S$. Then

$((h_{1}^{\varphi})^{-1})^{\sigma(g)}h_{2}^{\varphi}=gx^{-1}g^{-1}sx=g^{-1}x^{-1}gxs^{\prime}=[g,x]s^{\prime}\in[g,x]S.$

It follows that $\\{h_{1}^{\varphi},h_{2}^{\varphi})\in
E(GC(G,[g,x]S,\sigma(g)))$. Conversely, if
$\\{h_{1}^{\varphi},h_{2}^{\varphi})\in E(GC(G,[g,x]S,\sigma(g))$, then
$((h_{1}^{\varphi})^{-1})^{\sigma(g)}h_{2}^{\varphi}=gx^{-1}h_{1}^{-1}gh_{2}x\in[g,x]S$.
Combining the fact

$[g,x]S=g^{-1}x^{-1}gxS=gx^{-1}gSx,$

we have $h_{1}^{-1}gh_{2}\in gS$, which yields that
$gh_{1}^{-1}gh_{2}=(h_{1}^{-1})^{\sigma(g)}h_{2}\in S$. Therefore,
$\\{h_{1},h_{2}\\}\in E(GC(G,S,\sigma(g)))$ if and only if
$\\{h_{1}^{\varphi},h_{2}^{\varphi})\in E(GC(G,[g,x]S,\sigma(g)))$. ∎

##  4 Complete group and (restricted) GCI-group

Since the complete group $G$ of odd order does not contain involution, it does
not have involutory automorphism and generalized Cayley graphs. In this
section, we only consider the complete group of even order.

The definitions of restricted GCI-group and GCI-group are presented first.

######  Definition 4.1.

For any two generalized Cayley graphs $X_{i}=GC(G,S_{i},\alpha_{i})$ $(i=1,2)$
of $G$ with $|S_{i}|\leq m$,

  1. (a)

if $\alpha_{1}=\alpha_{2}=id$, $X_{1}\cong X_{2}$ implies there exists
automorphism $\gamma$ such that $S_{2}=S_{1}^{\gamma}$, then we call $G$ a
$m$-$CI$-group;

  2. (b)

if $X_{1}\cong X_{2}$ implies
$\alpha_{2}=\alpha_{1}^{\gamma}=\gamma\alpha_{1}\gamma^{-1}$ and
$S_{2}=g^{\alpha_{2}}S_{1}^{\gamma}g^{-1}$ for some $g\in G$ and automorphism
$\gamma$, then we call $G$ an $m$-$GCI$-group;

  3. (c)

if both $\alpha_{1}$ and $\alpha_{2}$ are involutions, $X_{1}\cong X_{2}$
implies $\alpha_{2}=\alpha_{1}^{\gamma}=\gamma\alpha_{1}\gamma^{-1}$ and
$S_{2}=g^{\alpha_{2}}S_{1}^{\gamma}g^{-1}$ for some $g\in G$ and automorphism
$\gamma$, then we call $G$ a restricted $m$-$GCI$-group.

In particular, if $m=|G|$, we simply call $G$ a $CI$-group, $GCI$-group or a
restricted $GCI$-group, respectively. The graph isomorphism among $\rm{(a)}$
is called $CI$ isomorphism. The graph isomorphisms among $\rm{(b)}$ and
$\rm{(c)}$ are called $GCI$ isomorphisms.

Regard to the $GCI$ isomorphisms of generalized Cayley graphs, the following
lemma holds.

######  Lemma 4.2.

[6] The $GCI$ isomorphism relation is an equivalence relation.

######  Lemma 4.3.

[3] $GC(G,S,\alpha)\cong GC(G,S^{\beta},\alpha^{\beta})$ for any $\beta\in
Aut(G)$, where $\alpha^{\beta}=\beta^{-1}\alpha\beta$.

Observe that if $S$ is a generalized Cayley subset of $G$ induced by the
involutory automorphism $\sigma(g)$ and it satisfies $g\notin S$, then
$e\notin S$ and $S^{\sigma(g)}=gSg=S^{-1}$. It follows that
$gS=S^{-1}g^{-1}=(gS)^{-1}$, and then $gS$ is a Cayley subset of $G$. Given
generalized Cayley graphs $GC(G,S_{1},\sigma(g_{1}))$ and
$GC(G,S_{2},\sigma(g_{2}))$. It is interesting to see the relationship between
the $GCI$ isomorphism of generalized Cayley graphs and the isomorphism of
Cayley graphs.

Let $S_{1}$ and $S_{2}$ be generalized Cayley subsets of $G$ induced by
involutory automorphisms $\sigma(g_{1})$ and $\sigma(g_{2})$ satisfying
$g_{1}\notin S_{1}$ and $g_{2}\notin S_{2}$, respectively. Then the following
conclusion holds.

######  Proposition 4.4.

If the generalized Cayley graph $GC(G,S_{1},\sigma(g_{1}))$ is $GCI$
isomorphic to $GC(G,S_{2},\sigma(g_{2}))$, then $Cay(G,g_{1}S_{1})$ is $CI$
isomorphic to $Cay(G,g_{2}S_{2})$.

###### Proof.

Since $GC(G,S_{1},\sigma(g_{1}))$ is $GCI$ isomorphic to
$GC(G,S_{2},\sigma(g_{2}))$, there exist elements $h$ and $x$ such that
$\sigma(g_{2})=\sigma(g_{1})^{\sigma(h)}=\sigma(hg_{1}h^{-1})$ and

$S_{2}=x^{\sigma(g_{2})}S_{1}^{\sigma(h)}x^{-1}=g_{2}xg_{2}^{-1}hS_{1}h^{-1}x^{-1}.$
(1)

Observe that $\sigma(g_{2})=\sigma(hg_{1}h^{-1})$ implies that for any element
$y\in G$,

$y^{\sigma(g_{2})}=g_{2}yg_{2}^{-1}=y^{\sigma(hg_{1}h^{-1})}=(hg_{1}h^{-1})y(hg_{1}h^{-1})^{-1}.$
(2)

It follows that $g_{2}^{-1}(hg_{1}h^{-1})\in Z(G)$. Since $Z(G)=e$, we have
$g_{2}=hg_{1}h^{-1}$. Combining Equalities (1) and (2), we obtain

$g_{2}S_{2}=xg_{2}^{-1}hS_{1}h^{-1}x^{-1}=xhg_{1}^{-1}S_{1}h^{-1}x^{-1}=xh(g_{1}S_{1})(xh)^{-1}=(g_{1}S_{1})^{\sigma_{xh}}.$

For any vertices $y_{1}$ and $y_{2}$, $\\{y_{1},y_{2}\\}\in
E(Cay(G,g_{1}S_{1}))$ if and only if $y_{1}^{-1}y_{2}\in g_{1}S_{1}$. Since
$\sigma_{xh}\in Aut(G)$, $y_{1}^{-1}y_{2}\in g_{1}S_{1}$ if and only if

$(y_{1}^{-1})^{\sigma_{xh}}y_{2}^{\sigma_{xh}}\in(g_{1}S_{1})^{\sigma_{xh}}=g_{2}S_{2}.$

Thus $Cay(G,g_{1}S_{1})\cong Cay(G,g_{2}S_{2})$ under the inner isomorphism
$\sigma_{xh}$. ∎

For each generalized Cayley subset $S$ induced by $\sigma(g)$, $gS$ is a
Cayley subset. However, the converse may not true, since for any generalized
Cayley subset $S$ and involution $g$ of $G$, $gS$ may not be generalized
Cayley subset. In some special case, the converse implication of Proposition
4.4 holds.

Let $g_{1},g_{2}$ be two conjugate involutions of $G$. Let $S_{1}$ and $S_{2}$
be Cayley subsets satisfying $S_{1}\cap C(g_{1})=\emptyset$ and $S_{2}\cap
C(g_{2})=\emptyset$. Then the following result holds.

######  Proposition 4.5.

If $Cay(G,S_{1})$ is $CI$ isomorphic to $Cay(G,S_{2})$, then the generalized
Cayley graph $GC(G,g_{1}S_{1},\sigma(g_{1}))$ is $GCI$ isomorphic to
$GC(G,g_{2}S_{2},\sigma(g_{2}))$.

###### Proof.

Firstly, we give an explanation for $g_{1}S_{1}$ and $g_{2}S_{2}$ are
generalized Cayley subsets induced by $\sigma(g_{1})$ and $\sigma(g_{2})$
respectively. Note that
$(g_{1}S_{1})^{\sigma(g_{1})}=S_{1}g_{1}=S_{1}^{-1}g_{1}^{-1}=(g_{1}S_{1})^{-1}$.
Since

$g_{1}S_{1}\cap\omega_{\sigma(g_{1})}(G)=g_{1}(S_{1}\cap\\{x^{-1}g_{1}x\mid
x\in G\\})=g_{1}(S_{1}\cap C(g_{1}))=\emptyset,$

Thus, $g_{1}S_{1}$ is generalized Cayley subsets induced by $\sigma(g_{1})$.
With the similar discussion, it can be verified that $g_{2}S_{2}$ is
generalized Cayley subsets induced by $\sigma(g_{2})$. Assume that
$Cay(G,S_{1})$ is $CI$ isomorphic to $Cay(G,S_{2})$ and $g_{2}=gg_{1}g^{-1}$
for some $g\in G$. Then there exists automorphism $\sigma(h)$ such that
$S_{2}=S_{1}^{\sigma(h)}$. Let $x=hg_{1}g^{-1}g_{2}$. Then

$S_{2}=hS_{1}h^{-1}=xg_{2}^{-1}gg_{1}^{-1}S_{1}g_{1}g^{-1}g_{2}x^{-1}.$

It follows that

$\displaystyle g_{2}S_{2}$
$\displaystyle=g_{2}xg_{2}^{-1}gg_{1}^{-1}S_{1}g_{1}g^{-1}g_{2}x^{-1}$
$\displaystyle=x^{\sigma(g_{2})}g(g_{1}S_{1})g^{-1}g_{2}x^{-1}$
$\displaystyle=x^{\sigma(g_{2})}(g_{1}S_{1})^{\sigma(g)}x^{-1}$

Thus, $GC(G,g_{1}S_{1},\sigma(g_{1}))$ is $GCI$ isomorphic to
$GC(G,g_{2}S_{2},\sigma(g_{2}))$. ∎

A corollary follows from Propositions 4.4 and 4.5.

######  Corollary 4.6.

Let $g_{1},g_{2}$ be two conjugate involutions of $G$. Let $S_{1}$ and $S_{2}$
be Cayley subsets of $G$ satisfying $S_{1}\cap C(g_{1})=\emptyset$ and
$S_{2}\cap C(g_{2})=\emptyset$. Then $Cay(G,S_{1})$ is $CI$ isomorphic to
$Cay(G,S_{2})$ if and only if $GC(G,g_{1}S_{1},\sigma(g_{1}))$ is $GCI$
isomorphic to $GC(G,g_{2}S_{2},\sigma(g_{2}))$.

Next we study the restricted GCI-group and GCI-group of complete groups. An
immediate consequence of Lemma 2.4 is as following.

######  Theorem 4.7.

Any complete group $G$ of even order is not $GCI$-group.

###### Proof.

Since the order of $G$ is even, it must contain an involution $g$ and then we
obtain the involutory automorphism $\sigma(g)$ of $G$. By Lemma 2.4,
$g\in\Omega_{\sigma(g)}(G)$. Then we have $GC(G,\\{g\\},\sigma(g))\cong
Cay(G,\\{g\\})\cong\frac{|G|}{2}K_{2}$. But $\sigma(g)$ is not conjugate to
the identity map, so $G$ is not $GCI$ group. ∎

Let $G_{2}$ be the subset containing all involutions of $G$. Then we obtain an
equivalent condition for $G$ to be restricted $GCI$ group.

######  Theorem 4.8.

Let $g$ be an involution of $G$. Then $G$ is restricted $GCI$ group if and
only if $G_{2}=C(g)$ and for any generalized Cayley subsets $S_{1}$ and
$S_{2}$ induced by $\sigma(g)$, $GC(G,S_{1},\sigma(g))\cong
GC(G,S_{2},\sigma(g))$ implies that there exists $\sigma(x)\in Aut(G)$ such
that $gS_{2}=(gS_{1})^{\sigma(x)}$.

###### Proof.

Assume that $G$ is restricted $GCI$-group. For any involution $h$ of $G$,
according to the proof Theorem 4.7, we obtain that
$GC(G,\\{g\\},\sigma(g))\cong GC(G,\\{h\\},\sigma(h))\cong\frac{|G|}{2}K_{2}$.
From the definition of restricted $GCI$-group, it follows that $\sigma(g)$ and
$\sigma(h)$ are conjugate in $Aut(G)$. By Observation 2.2, $g$ and $h$ are
conjugate in $G$. Thus, $G_{2}=C(g)$. If $GC(G,S_{1},\sigma(g))\cong
GC(G,S_{2},\sigma(g))$, then from the definition of restricted $GCI$ group, we
have $\sigma(g)=\sigma(g)^{\sigma(x)}=\sigma(xgx^{-1})$ and
$S_{2}=y^{\sigma(g)}S_{1}^{\sigma(x)}y^{-1}$ for some elements $x,y\in G$. The
latter equality is equivalent to $gS_{2}=ygS_{1}^{\sigma(x)}y^{-1}$. As the
proof Proposition 4.4, $Z(G)=e$ and
$\sigma(g)=\sigma(g)^{\sigma(x)}=\sigma(xgx^{-1})$ implies that
$g=xgx^{-1}=g^{\sigma(x)}$. It follows that

$gS_{2}=y(gS_{1})^{\sigma(x)}y^{-1}=(gS_{1})^{\sigma(y)\sigma(x)}=(gS_{1})^{\sigma(yx)}.$

Conversely, $G_{2}=C(g)$ means that each involution of $G$ is conjugate to
$g$. According to Lemma 4.3, it follows that each generalized Cayley graph is
$GCI$ isomorphic to a generalized Cayley graph induced by $\sigma(g)$.
Moreover, Lemma 4.3 tells us the $GCI$ isomorphism relation is an equivalence
relation. Thus, to show that $G$ is restricted $GCI$ complete group, it
suffices to prove that the isomorphism between the generalized Cayley graphs
induced by $\sigma(g)$ is $GCI$ isomorphism. For any generalized Cayley graphs
$GC(G,S_{1},\sigma(g))$ and $GC(G,S_{2},\sigma(g))$, assume that
$GC(G,S_{1},\sigma(g))\cong GC(G,S_{2},\sigma(g))$. Then there exists
$\sigma(x)\in Aut(G)$ such that $gS_{2}=(gS_{1})^{\sigma(x)}$. Let $y=xg$.
Thus we infer that

$\displaystyle S_{2}$
$\displaystyle=g(gS_{1})^{\sigma(x)}=g(gS_{1})^{\sigma(y)\sigma(g)}=g((gS_{1})^{\sigma(g)})^{\sigma(y)}$
$\displaystyle=g(S_{1}g)^{\sigma(y)}=gyS_{1}gy^{-1}=gxgS_{1}gy^{{}_{1}}=gxS_{1}^{\sigma(g)}y^{-1}$

Observe that $y^{\sigma(g)}=gxgg=gx$. It follows that
$S_{2}=y^{\sigma(g)}S_{1}^{\sigma(g)}y^{-1}$. Clearly,
$\sigma(g)^{\sigma(g)}=\sigma(g)$. Therefore, $G$ is restricted $GCI$ group. ∎

In Lemma 2.4, we state that for any involutory automorphism $\sigma(g)$ of
$G$, $g\in\Omega_{\sigma(g)}(G)$. Especially, if $G$ is restricted
$GCI$-group, then we further obtain the following result.

######  Proposition 4.9.

If $G$ is restricted $GCI$ complete group of even order, then
$\Omega_{\sigma(g)}(G)=\\{g\\}$.

###### Proof.

If there exists element $h\in\Omega_{\sigma(g)}(G)$ and $h\neq g$, then from
Observation 2.3, $gh$ is involution of $G$. Since $G$ is restricted $GCI$
group, by Theorem 4.8, $gh$ and $g$ are conjugate. It follows that there
exists element $x\in G$ such that $gh=x^{-1}gx$, which implies
$xghg=gxg=x^{\sigma(g)}$. Then

$(x^{-1})^{\sigma(g)}x=g^{-1}h^{-1}gx^{-1}x=g^{-1}h^{-1}g=(h^{-1})^{\sigma(g)}=h.$

Thus, $h\in\Omega_{\sigma(g)}(G)\cap\omega_{\sigma(g)}(G)$, which is a
contradiction. Therefore, $\Omega_{\sigma(g)}(G)=\\{g\\}$. ∎

If $G$ is complete group but $4\nmid|G|$, we have the same result as
Proposition 4.13.

######  Proposition 4.10.

If $G$ is complete group of even order and $4\nmid|G|$, then for any
involutory automorphism $\sigma(g)$ of $G$, $\Omega_{\sigma(g)}(G)=\\{g\\}$.

###### Proof.

Assume that there exists element $h\in\Omega_{\sigma(g)}(G)$ and $h\neq g$.
From Lemma 2.4, we know that $\\{g,h\\}$ is a generalized Cayley subset. For
any vertex $x$ in $GC(G,\\{g,h\\},\sigma(g))$, $x\rightarrow gx\rightarrow
xgh\rightarrow gxgh$ is a cycle of length $4$. Thus,
$GC(G,\\{g,h\\},\sigma(g))\cong\frac{|G|}{4}$, which is contrary to
$4\nmid|G|$. Therefore, $\Omega_{\sigma(g)}(G)=\\{g\\}$. ∎

Next is a application of Theorem 4.8. It is known that the symmetric group
$S_{n}(n\neq 6)$ is complete group. There are two basic facts about symmetric
groups:

(1) Without the consideration of order, each permutation of $S_{n}$ can be
decomposed into product of some disjoint cycle;

(2) two elements of $S_{n}$ are conjugate if and only if their cycle form are
the same.

For example, $(12)$ and $(34)$ are elements of $S_{4}$, and they are conjugate
since both them have a cycle of length $2$. But $(12)$ is not conjugate to
$(12)(34)$.

As an application of Theorem 4.8, we determined the restricted $GCI$ group
among symmetric groups $S_{n}$.

######  Corollary 4.11.

The symmetric group $S_{n}(n\neq 6)$ is restricted $GCI$-group if and only if
$n=3$.

###### Proof.

For $n\geq 4$ and $n\neq 6$, $(12)$ and $(12)(34)$ are involutions of the
symmetric group $S_{n}$. Since the cycle form of $(12)$ and $(12)(34)$ are
different, $(12)$ and $(12)(34)$ are not conjugate. By Theorem 4.8,
$S_{n}(n\geq 4~{}\text{and}~{}n\neq 6)$ is not restricted $GCI$-group. Now it
suffices to prove that $S_{3}$ is restricted $GCI$-group. Observe that
$S_{3}=\\{(1),(12),(13),(23),(123),(132)\\}$ and all involutions of it are
conjugate. Choose the involution $\sigma_{(12)}$. Then we have
$\omega_{(12)}(S_{3})=\\{(1),(123),(132)\\}$,
$\Omega_{(12)}(S_{3})=\\{(12)\\}$ and $\mho_{(12)}(S_{3})=\\{(23),(13)\\}$.
For any positive integer $d\leq 3$, the $d$-valent generalized Cayley graph of
$G$ induced by $\sigma_{(12)}$ is unique. By Theorem 4.8, $S_{3}$ is
restricted $GCI$-group. ∎

In reference [9], the author depict the automorphism of $S_{6}$ in detail.
Note that $S_{6}$ can be generated by $A=\\{(12),(13),(14),(15),(16)\\}$.
Define a map $\phi$ on $S_{6}$ as follows:

$\displaystyle(12)^{\phi}=(12)(36)(45),(13)^{\phi}=(16)(24)(35),(14)^{\phi}=(13)(25)(46),$
$\displaystyle(15)^{\phi}=(15)(26)(34),(16)^{\phi}=(14)(23)(56).$

It can be verified that $\phi$ is outer automorphism of $S_{6}$. Let
$x=(12345)$, $\sigma(x)$ is the inner automorphism induced by $x$. Let
$\delta=\sigma(x)\phi$, then $\delta$ is an involutory outer automorphism of
$S_{6}$.

######  Lemma 4.12.

[9] For any element $h\in S_{6}$ , define the map
$\delta_{g}:h^{\delta_{g}}=gh^{\delta}g^{-1}=(h^{\phi})^{\sigma(gx)}$. Then
$\mathrm{Aut}(S_{6})=\\{\sigma(g)\mid g\in S_{6}\\}\cup\\{\delta_{g}\mid g\in
S_{6}\\}$.

Using Lemma 4.12, we prove the next proposition.

######  Proposition 4.13.

$S_{6}$ is not restricted $\mathrm{GCI}$ group.

###### Proof.

Note that both $\sigma(12)$ and $\sigma\left((12)(34)\right)$ are involutory
automorphisms of $S_{6}$, and

$\mathrm{GC}(S_{6},\\{(12)\\},\sigma(12))\cong\mathrm{GC}(S_{6},\\{(12)(34)\\},\sigma\left((12)(34))\right)\cong
360K_{2}.$

Now we aim to prove that $\sigma(12)$ and $\sigma\left((12)(34)\right)$ are
not conjugate in $\mathrm{Aut(S_{6})}$.

Firstly, for any element $g\in S_{6}$,
$\sigma(12)^{\sigma(g)}=\sigma(g)\sigma(12)\left(\sigma(g)\right)^{-1}=\sigma\left(g(12)g^{-1}\right)$.
If $\sigma\left(g(12)g^{-1}\right)=\sigma\left((12)(34)\right)$, then for any
element $h\in S_{6}$,

$h^{\sigma\left(g(12)g^{-1}\right)}=g(12)g^{-1}hg(12)g^{-1}=(12)(34)h(12)(34)=h^{\sigma\left((12)(34)\right)}.$

It indicates that $(12)(34)g(12)g^{-1}\in Z(S_{6})=e$, and then
$(12)(34)=g(12)g^{-1}$. But this equality cannot hold, as $(12)$ is not
conjugate to $(12)(34)$ in $S_{6}$. Thus, for any element $g\in S_{6}$,
$\sigma(12)^{\sigma(g)}\neq\sigma\left((12)(34)\right)$.

We consider the conjugation map for $\sigma(12)$ under the automorphism in
$\\{\delta_{g}\mid g\in S_{6}\\}$. For any automorphism $\delta_{g}$, let
$\gamma=\delta_{(g^{-1})^{\delta}}$. Since $\delta$ is involutory
automorphism, for any element $h\in G$,

$h^{\gamma\delta_{g}}=(h^{\delta_{g}})^{\gamma}=(gh^{\delta}g^{-1})^{\gamma}=(g^{-1})^{\delta}(gh^{\delta}g^{-1})^{\delta}g^{\delta}=(g^{-1})^{\delta}g^{\delta}h(g^{-1})^{\delta}g^{\delta}=h.$

Then we deduce that $(\delta_{g})^{-1}=\delta_{(g^{-1})^{\delta}}$. It follows
that

$\displaystyle h^{\delta_{g}\sigma(12)(\delta_{g})^{-1}}$
$\displaystyle=h^{\delta_{g}\sigma(12)\delta_{(g^{-1})^{\delta}}}$
$\displaystyle=g\left((12)(g^{-1})^{\delta}h^{\delta}g^{\delta}(12)\right)^{\delta}g^{-1}$
$\displaystyle=g(12)^{\delta}g^{-1}hg(12)^{\delta}g^{-1}$
$\displaystyle=h^{\sigma(g(12)^{\delta}g^{-1})}.$

Since $(12)^{\delta}=(12)(36)(45)$, and $(12)(36)(45)$ is not conjugate to
$(12)(34)$ in $S_{6}$,
$g(12)^{\delta}g^{-1}=\left((12)(36)(45)\right)^{\sigma(g)}\neq(12)(34)$.
Thus, $\delta_{g}\sigma(12)(\delta_{g})^{-1}\neq\sigma\left((12)(34)\right)$.

In conclusion, $\sigma(12)$ is not conjugate to $\sigma\left((12)(34)\right)$
in $\mathrm{Aut(S_{6})}$. Therefore, $S_{6}$ is not restricted $\mathrm{GCI}$.
∎

Combining Corollary 4.11 and Proposition 4.13, we give the characterization of
restricted $\mathrm{GCI}$ groups for symmetric groups.

######  Theorem 4.14.

The symmetric group $S_{n}$ is restricted $\mathrm{GCI}$ group if and only if
$n=3$.

To determine the $GCI$ groups in symmetric groups completely, we only need to
consider $S_{6}$.

## References

  * [1] J. A. Bondy, U. S. R. Murty, Graph theory with applications, Macmillan London and Elsevier, New York, (1976).
  * [2] A. Hujdurović, K. Kutnar, D. Marušič, Vertex-transitive generalized Cayley graphs which are not Cayley graphs, European J. Combin. 46 (2015), 45–50.
  * [3] A. Hujdurović, K. Kutnar, P. Petecki, A. Tanana, On automorphisms and structural properties of generalized Cayley graphs, Filomat 31 (2017), 4033–4040.
  * [4] Qianfen Liao, Weijun Liu, GCI-property of some groups, Appl. Math. Comput. 438 (2023).
  * [5] D. Marušič, R. Scapellato, N. Zagaglia Salvi, Generalized Cayley graphs, Discrete Math. 102 (1992), 279–285.
  * [6] X. Yang, W.J. Liu, J. Chen, L.H. Feng, GCI-groups in the alternating groups, Appl. Math. Comput. 303 (2017), 42–47.
  * [7] X. Yang, W.J. Liu, L.H. Feng, Isomorphisms of generalized Cayley graphs, Ars. Math. Contemp. 15 (2018), 407–424.
  * [8] X.M. Zhu, W.J. Liu, X. Yang, The isomorphism of generalized Cayley graphs on finite non-abelian simple groups, Discrete Math. 346 (2023), 1–10.
  * [9] Wu M Y, Tang Q L, Luo X H, Jiang H L. A class of Hopf algebras on permutation groups $S_{6}$. J Mathematics(in Chinese), 2018, 38(5): 921–932.