text:
\begin{document}

\title[A mapping from unitary to doubly stochastic matrices]{A mapping from the unitary to doubly stochastic matrices and symbols on a finite set}

\author[A.V. Karabegov]{Alexander V. Karabegov}
\address[Alexander V. Karabegov]{Department of Mathematics, Abilene Christian University, ACU Box 28012, 215 Foster Science Building, Abilene, TX 79699-8012}
\email{axk02d@acu.edu}
\begin{abstract}
  We prove that the mapping from the unitary to the doubly stochastic matrices
that maps a unitary matrix $(u_{kl})$ to the doubly stochastic matrix $(|u_{kl}|^2)$ is a submersion for almost all unitary matrices. The proof uses the framework of operator symbols on a finite set.
\end{abstract}
\subjclass{Primary: 53A07; Secondary: 35S05}
\keywords{doubly stochastic matrices, symbols}

\maketitle

\section{Introduction}

Given a unitary matrix $(u_{kl})$, the matrix  $(|u_{kl}|^2)$ is doubly stochastic. The mapping
\[
   \mu: (u_{kl}) \mapsto (|u_{kl}|^2)
\]
from the set $U$ of unitary $(n\times n)$-matrices to the set $P$ of doubly stochastic $(n\times n)$-matrices was studied in a number of papers in mathematical physics (see \cite{TZ} and references therein). The set $U$ is a real $n^2$-dimensional manifold and $P$ is a convex $(n-1)^2$-dimensional polytope, the Birkhoff polytope. It is known that the image $\mu(U)$ is a proper subset of the Birkhoff polytope $P$. Two unitary matrices $u$ and $\tilde u$ are called equivalent if there exist unitary diagonal matrices $\varkappa$ and $\lambda$ such that $\tilde u = \varkappa u \lambda$. The mapping $\mu$ maps equivalent unitary matrices to  the same doubly stochastic matrix. The set of equivalence classes of unitary matrices with nonzero entries is an $(n-1)^2$-dimensional manifold. These dimensional considerations lead to the natural question of whether $\mu$ is a submersion. It was deemed that $\mu$ has to be a submersion almost everywhere on $U$ (see, e.g., \cite{B}). In this paper we give a detailed proof of this result which was announced in \cite{K}.

To each unitary $(n\times n)$-matrix $u$ with nonzero entries we relate an operator $I_u$ on an $n^2$-dimensional vector space $V$ and show that the dimension of the kernel of the tangent mapping $\mu_{*u}$ equals the multiplicity of the eigenvalue 1 in the spectrum of $I_u$. We introduce the notion of a symmetry group $G$ of a unitary matrix $u$. The group $G$ has a unitary representation in the space $V$ which commutes with the operator $I_u$. When the matrix $u$ has a large symmetry group, it is sometimes possible to calculate the spectral decomposition of the operator $I_u$. This allows us to show that the mapping $\mu$ is a submersion for almost all elements of $U$.

\section{Symbols on a finite set}\label{S:symbols}

In this section we introduce a construction of two types of symbols of operators on a finite dimensional vector space. These symbols are analogues of $pq$- and $qp$-symbols in quantum mechanics (see \cite{BS}).

We will model finite dimensional vector spaces as the spaces of functions on finite sets. Given a finite set $J$, denote by $F(J)$ the space of all complex-valued functions on $J$. The standard Hermitian product of functions $\varphi = \varphi_j, \psi = \psi_j \in F(J)$
is given by the formula
\[
    \langle \varphi,\psi\rangle = \sum_{j\in J} \varphi_j \bar \psi_j.
\]
Now let $K$ and $L$ be two $n$-element index sets and $u = (u_{kl}), k\in K,l\in L$, be a unitary matrix. It determines a unitary isomorphism $\U : F(L) \to F(K)$ of the vector spaces $F(K)$ and $F(L)$ endowed with the standard Hermitian products: for $\psi = \psi_l \in F(L)$,
\[
   (\U \psi)_k = \sum_{l\in L} u_{kl} \psi_l.
\]
Denote $M := K\times L$. We define two mappings
\[
C_u,D_u : F(M) \to \End F(K)
\]
such that for $f = f_{kl} \in F(M)$ the matrices $(x_{kk'})$ and $(y_{kk'})$ of the operators $C_uf$ and $D_uf$ in $F(K)$, respectively, are given by the following formulas:
\begin{equation}\label{E:cdsymb}
   x_{kk'} = \sum_{l \in L} u_{kl} f_{kl} \bar u_{k'l} \mbox{ and } y_{kk'} = \sum_{l \in L} u_{kl} f_{k'l} \bar u_{k'l}.
\end{equation}
The mappings $f \mapsto C_uf$ and $f \mapsto D_uf$ can be thought of as two different symbol-to-operator mappings.

Given functions $a=a_k \in F(K)$ and $b = b_l\in F(L)$, denote by $\hat a$ and $\hat b$ the multiplication operators by these functions in $F(K)$ and $F(L)$, respectively. Then $ab = a_kb_l \in F(M), \ \U\hat b \U^* \in \End F(K),$ and it can be checked that
\begin{equation}\label{E:ord}
    C_u(ab) = \hat a \left(\U \hat b \U^*\right) \mbox{ and } D_u(ab) = \left(\U \hat b \U^*\right) \hat a.
\end{equation}
Using the analogy with quantum mechanics, we may think of $F(K)$ and $F(L)$ as of the ``coordinate" and``momentum" representations of an abstract Hermitian vector space, respectively, with the isomorphism $\U$ playing the role of the Fourier transform. The mapping $C_u$ is obtained by the standard ordering of the ``coordinate" operators $\hat a$ and ``momentum" operators $\U\hat b \U^*$, while $D_u$ is obtained via the inverse ordering.

Given a function $f \in F(M)$ and an operator $A \in \End F(K)$, we will say that the function $f$ is a $C$-symbol of the operator $A$ if $A = C_u f$ and that $f$ is a $D$-symbol of $A$ if $A = D_u f$. Thus, $C$- and $D$-symbols correspond to $qp$- and $pq$-symbols, respectively.

Now we will make a critical assumption that all elements $u_{kl}$ of the matrix $u$ are nonzero and introduce a Hermitian product $\langle\cdot,\cdot\rangle_u$ on the space $F(M)$ by the formula
\[
     \langle f,g\rangle_u = \sum_{k\in K, l\in L} f_{kl} \bar g_{kl}|u_{kl}|^2.
\]
The space $\End F(K)$ of operators in $F(K)$ carries the Hilbert-Schmidt Hermitian product $\langle\cdot,\cdot\rangle_{HS}$. If $(x_{kk'})$ and $(y_{kk'})$ are the matrices of operators $X$ and $Y$ in $F(K)$, respectively, then
\[
    \langle X,Y \rangle_{HS} = \tr XY^\ast = \sum_{k, k' \in K} x_{kk'}\bar y_{kk'}.
\]
The following properties of $C$- and $D$-symbols are analogous to the corresponding properties of $pq$- and $qp$-symbols of Hilbert-Schmidt operators in quantum mechanics.
\begin{proposition}\label{P:isom}
   The mappings $C_u, D_u: F(M) \to \End F(K)$ are unitary isomorphisms of the Hermitian vector spaces $(F(M),\langle\cdot,\cdot\rangle_u)$ and $(\End V, \langle\cdot,\cdot\rangle_{HS})$.
\end{proposition}
\begin{proof}
 Given two functions $f,g \in F(M)$, let $(x_{kk'})$ and $(y_{kk'})$ be the matrices of the operators $C_uf$ and $C_ug$, respectively, so that
\[
   x_{kk'} = \sum_{l \in L} u_{kl} f_{kl} \bar u_{k'l} \mbox{ and } y_{kk'} = \sum_{l' \in L} u_{kl'} g_{kl'} \bar u_{k'l'}.
\]
Then, using the unitarity of the matrix $u$, we obtain that
\begin{eqnarray*}
   \langle C_uf, C_ug \rangle_{HS} = \sum_{k,k'\in K} x_{kk'} \bar y_{kk'} =
\sum_{k,k'\in K, l,l'\in L} u_{kl} f_{kl} \bar u_{k'l} \bar u_{kl'} \bar g_{kl'} u_{k'l'}=\\
\sum_{k\in K, l,l'\in L} u_{kl} f_{kl} \bar u_{kl'} \bar g_{kl'} \delta_{ll'}=
\sum_{k\in K,l\in L} f_{kl}\bar g_{kl} |u_{kl}|^2 = \langle f,g\rangle_u,
\end{eqnarray*}
where $\delta_{ll'}$ is the Kronecker symbol. Thus $C_u: F(M) \to \End F(K)$ is an isometric mapping. Since the dimensions of $F(M)$ and $\End F(K)$ are both equal to $n^2$, the mapping $C_u$ is a unitary isomorphism. A similar calculation shows that $D_u: F(M) \to \End F(K)$ is also a unitary isomorphism.
\end{proof}

It follows from Proposition \ref{P:isom} that the mapping $I_u := C_u^{-1}D_u$ that maps the $D$-symbols to the corresponding $C$-symbols is a unitary operator in $(F(M),\langle\cdot,\cdot\rangle_u)$. Using the analogy with quantum mechanics, we will call the operator $I_u$ the Berezin transform. It can be checked that the operator $I_u$ is given by the following formula: for a function $f = f_{kl} \in F(M)$,
\[
     (I_u f)_{kl} = \sum_{k' \in K, l'\in L} \frac{u_{kl'} u_{k'l}}{u_{kl} u_{k'l'}}\, f_{k'l'}\, |u_{k'l'}|^2.
\]
\begin{proposition}\label{P:conjug} Given a function $f \in F(M)$, the operators $C_uf$ and $D_u\bar f$ are Hermitian conjugate.
\end{proposition}
\begin{proof}
  Let $(x_{kk'})$ be the matrix of the operator $C_uf$ in $F(K)$. Using formulas (\ref{E:cdsymb}) we see that the Hermitian conjugate matrix $(\bar x_{k'k})$ is given by the equation
\[
    \bar x_{k'k} = \sum_{l\in L} \bar u_{k'l} \bar f_{k'l} u_{kl}
\]
and therefore coincides with the matrix of the operator $D_u\bar f$.
\end{proof}

This proposition allows to give a characterization of the $C$- and $D$-symbols of the skew-Hermitian operators in $F(K)$ which will be used in Section \ref{S:geom}.

\begin{corollary}\label{C:skew}
  Given functions $f,g \in F(M)$, the operator $C_uf$ is skew-Hermitian if and only if $f = - I_u \bar f$ and the operator $D_ug$ is skew-Hermitian if and only if $I_u g = -\bar g$. If $f = I_u g$, then the operator $C_u f = D_u g$ is skew-Hermitian if and only if $f = - \bar g$.
\end{corollary}
\begin{proof} Proposition \ref{P:conjug} states that
\[
    (C_uf)^*= D_u\bar f.
\]
Now the operator $C_uf$ is skew-Hermitian, i.e., $C_uf = -(C_uf)^*$, if and only if $C_u f = - D_u \bar f$ or, equivalently, $f = -I_u\bar f$. The rest of the corollary is proved similarly.
\end{proof}

Assume that functions $f, g\in F(M)$ are such that $f = I_ug$ or, equivalently, $C_uf = D_ug$. According to Proposition \ref{P:conjug},
\[
D_u\bar f = (C_uf)^* = (D_ug)^* = C_u\bar g,
\]
whence $I_u\bar f = \bar g$. Let $g\in F(M)$ be an eigenfunction of the Berezin transform $I_u$ with the eigenvalue $\theta$. Since $I_u$ is unitary, we have $|\theta| =1$. Equation $I_u g = \theta g$ implies that $I_u(\bar\theta \bar g) = \bar g$, whence $I_u(\bar g) = \theta \bar g$. Thus we have proved the following
\begin{lemma}\label{L:eigen}
The eigenspaces of the Berezin transform $I_u$ are invariant under complex conjugation. In particular, for any eigenvalue $\theta$ of multiplicity $k$ the $\theta$-eigenspace treated as a real vector space is a direct sum of the $k$-dimensional real vector spaces comprised of real and purely imaginary eigenfunctions, respectively.
\end{lemma}
Denote by $E$ the subspace of $F(M)$ of the functions $f$ that can be represented as a sum of the form $f_{kl} = a_k + b_l$. The dimension of $E$ is $2n - 1$.
Formulas (\ref{E:ord}) imply that for functions $a = a_k$ and $b = b_l$ considered as elements of $F(M)$,
\[
     C_u(a) = D_u(a) \mbox{ and } C_u(b) = D_u(b),
\]
which leads to the following statement.
\begin{lemma}\label{L:E}
 For any function $f \in E$ we have $I_uf = f$. Thus the multiplicity of 1 in the spectrum of the Berezin transform $I_u$ is at least $2n-1$.
\end{lemma}

\section{Symmetries of a unitary matrix}

Assume that, as in Section \ref{S:symbols}, $K$ and $L$ are two $n$-element sets, and $u = (u_{kl}),\, k \in K,l\in L,$ is a unitary matrix which defines a unitary isomorphism
\[
    \U: F(L) \to F(K),
\]
where $F(K)$ and $F(L)$ are endowed with the standard Hermitian products. Assume further that $G$ is a group that acts on the left on the sets $K$ and $L$ and has faithful unitary representations $S$ and $T$ in the spaces $F(K)$ and $F(L)$, respectively, such that, given $g\in G, \varphi=\varphi_k \in F(K), \psi = \psi_l \in F(L)$,
\[
     \left(S_g \varphi\right)_k = a_k(g) \varphi_{g^{-1}k} \mbox{ and } \left(T_g \psi\right)_l = b_l(g) \psi_{g^{-1}l},
\]
where $a_k(g) \in F(K)$ and $b_l(g) \in F(L)$ are two unitary functions (i.e., $|a_k(g)| = |b_l(g)| = 1$). Finally we assume that the isomorphism $\U$ intertwines the representations $S$ and $T$: for $g \in G$,
\begin{equation}\label{E:inter}
                 S_g\,  \U = \U\,  T_g.
\end{equation}
If these conditions are satisfied, we say that $G$ is a {\it symmetry group of the matrix} $u$. Condition (\ref{E:inter}) can be expressed in terms of the matrix $u$ as follows:
\begin{equation}\label{E:matrixinter}
     a_k(g)\left( u_{g^{-1}k\, g^{-1}l} \right) \bar b_l(g) = u_{kl}.
\end{equation}
Denote by $R$ the following representation of the group $G$ in $F(M)$: for $g \in G$ and $f = f_{kl} \in F(M)$,
\[
       \left(R_g f\right)_{kl} = f_{g^{-1}k\, g^{-1}l}.
\]
Using formula (\ref{E:matrixinter}) and the fact that the functions $a_k(g)$ and $b_l(g)$ are unitary we obtain the following
\begin{lemma}\label{L:unitary}
  The representation $R$ is a unitary representation of the group $G$ in the Hermitian vector space $(F(M), \langle\cdot,\cdot\rangle_u)$.
\end{lemma}

Denote by $Q$ the representation of the group $G$ in the space $\End F(K)$ by conjugation via the operators of the representation $S$: for $g \in G$ and $X \in \End F(K)$,
\[
     Q_g(X) = S_g X S_g^{-1} = S_g X S_g^*.
\]
The representation $Q$ is a unitary representation of the group $G$ in the Hermitian vector space $(\End F(K),\langle\cdot,\cdot\rangle_{HS})$.

The following equivariance property of the symbol-to-operator mappings $C_u$ and $D_u$ is analogous to the equivariance of the $pq$- and $qp$-symbol mappings with respect to the Heisenberg group.

\begin{proposition}\label{P:equiv}
The mappings $C_u, D_u: F(M) \to \End F(K)$ intertwine the representations $Q$ and $R$: for $g \in G$,
\[
     C_u(R_gf) = S_g(C_u(f))S_g^* \mbox{ and } D_u(R_gf) = S_g(D_u(f))S_g^*.
\]
\end{proposition}
\begin{proof}
  Given $g \in G, \ f \in F(M)$ and $\varphi \in F(K)$, we get with the use of formula (\ref{E:matrixinter}) the following:
\begin{eqnarray*}
 (S C_u(f) \varphi)_k = \sum_{k' \in K, l'\in L} a_k(g) u_{g^{-1}k \,l'} f_{g^{-1}k \,l'} \bar u_{k'l'} \varphi_{k'} = \\
\sum_{\tilde k \in K, l\in L} a_k(g) u_{g^{-1}k \,g^{-1}l} f_{g^{-1}k \,g^{-1}l} \bar u_{g^{-1}\tilde k \,g^{-1}l} \varphi_{g^{-1}\tilde k} = \\
\sum_{\tilde k \in K, l\in L} a_k(g) u_{g^{-1}k \,g^{-1}l}\bar b_l(g) f_{g^{-1}k \,g^{-1}l}b_l(g) \bar u_{g^{-1}\tilde k \,g^{-1}l} \varphi_{g^{-1}\tilde k} = \\
\sum_{\tilde k \in K, l\in L} u_{kl}(R_g f)_{kl}b_l(g) \bar u_{g^{-1}\tilde k \,g^{-1}l} \varphi_{g^{-1}\tilde k} = \\
\sum_{\tilde k \in K, l\in L} u_{kl}(R_gf)_{kl} \left(\overline{ a_{\tilde k}(g)u_{g^{-1}\tilde k\, g^{-1}l}\bar b_l(g)}\right) a_{\tilde k}(g) \varphi_{\sigma(\tilde k)} = \\
\sum_{\tilde k \in K, l\in L} u_{kl}(R_g f)_{kl} \bar u_{\tilde kl}a_{\tilde k}(g) \varphi_{g^{-1}\tilde k} = \left(C_u\left(R_gf\right) S \varphi\right)_k.
\end{eqnarray*}
The proof that the mapping $D_u$ intertwines the representations $Q$ and $R$ is similar.
\end{proof}
Since both $C_u$ and $D_u$ intertwine the representations $Q$ and $R$ of the group $G$, we obtain the following
\begin{corollary}
 The Berezin transform $I_u = C_u^{-1} D_u$ commutes with the representation $R$: for $g\in G$,
\[
               I_u R_g = R_g I_u.
\]
\end{corollary}

\section{Examples of unitary matrices with a large group of symmetries}\label{S:examples}

In this section we will consider two examples of unitary matrices with large symmetry groups. For each of these matrices we will obtain the spectral decomposition of the corresponding Berezin transform and in particular determine the multiplicity of the eigenvalue 1 in their spectra. In Section \ref{S:geom} we will give a geometric interpretation of this multiplicity.

{\it Example 1.} Fix a natural number $n$ and denote by $\e$ the character of the cyclic group $\mathbb{Z}/n\mathbb{Z}$ given by the formula
\[
     \e(k) = \exp\left\{\frac{2\pi i k}{n}\right\}.
\]
Here we denote by $k$ (somewhat loosely) an integer modulo $n$.
The Fourier transform $\F$ on the cyclic group $\mathbb{Z}/n\mathbb{Z}$ is given by the unitary matrix $u = (u_{kl})$ with
\[
     u_{kl} = \frac{1}{\sqrt{n}}\,  \e(kl),
\]
where $k,l \in \mathbb{Z}/n\mathbb{Z}$ (here $K = L = \mathbb{Z}/n\mathbb{Z}$).
The corresponding Berezin transform is given by the following formula:
\begin{equation}\label{E:fourber}
    (I_uf)_{kl} = \frac{1}{n}\sum_{k',l' \in \mathbb{Z}/n\mathbb{Z}}\e(-(k - k')(l-l')) \,  f_{k'l'}.
\end{equation}
For $r \in \mathbb{Z}/n\mathbb{Z}$ denote by $W_r$ the unitary operator of multiplication by the function $\e(rk)$ and by $Z_r$ the shift operator by the element $r$ such that for $\varphi_k \in F(\mathbb{Z}/n\mathbb{Z})$
\[
     (W_r \varphi)_k = \e(rk) \varphi_k \mbox{ and } (Z_r \varphi)_k = \varphi_{k + r}.
\]
 A simple calculation shows that
\begin{equation}\label{E:fmt}
    \F^* W_r \F = Z_{-r} \mbox{ and } \F^* Z_r \F= W_r.
\end{equation}
Formulas (\ref{E:ord}) and (\ref{E:fmt}) imply that
\[
    C_u(\e(rk + sl)) = W_r \F W_s \F^* = W_r Z_s.
\]
Similarly,
\[
    D_u(\e(rk + sl)) = Z_s W_r.
\]
From the Weyl commutation relations
\begin{equation}\label{E:Weyl}
     Z_s W_r = \e(rs) W_r Z_s
\end{equation}
it follows immediately that
\[
    I_u(\e(rk + sl)) = \e(rs)\e(rk + sl).
\]
The functions $\e(rk + sl)$ with $r,s \in \mathbb{Z}/n\mathbb{Z}$ form a complete system of eigenvectors of the operator $I_u$ with the corresponding eigenvalues $\e(rs)$. Observe that $\e(rs) =1$ if and only if $rs = 0$ in $\mathbb{Z}/n\mathbb{Z}$, which implies the following
\begin{lemma}
 The multiplicity of the eigenvalue 1 of the Berezin transform corresponding to the matrix of the Fourier transform on the group $\mathbb{Z}/n\mathbb{Z}$ is equal to the number of pairs $(r,s)$ of integers such that $0 \leq r,s < n$ and $rs = 0 \pmod n$. In particular, this multiplicity equals $2n-1$ if and only if $n$ is a prime.
\end{lemma}

{\it Remark.}  {\small The spectral decomposition of the Berezin transform $I_u$ is easy to obtain because the matrix $u$ of the Fourier transform on the group $\mathbb{Z}/n\mathbb{Z}$ has a large symmetry group. Let $\mathbb{T}$ denote the multiplicative group of complex numbers of modulus 1. The generalized Heisenberg group $ G := (\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}) \ltimes \mathbb{T}$ with the product
\[
    (s_1, t_1, \theta_1) \cdot (s_2, t_2, \theta_2) = (s_1 + s_2, t_1 + t_2, \theta_1\theta_2 \varepsilon(t_1 s_2)),
\]
where $s_i,t_i \in \mathbb{Z}/n\mathbb{Z}$ and $\theta_i \in \mathbb{T}$, is a symmetry group of the matrix $u$. The corresponding representations $S$ and $T$ are given by the formulas
\[
           S_{(s,t,\theta)} = \theta W_s Z_t \mbox{ and } T_{(s,t,\theta)} = \F^* S_{(s,t,\theta)} \F = \theta Z_{-s} W_t = \theta \varepsilon(-st) W_t Z_{-s}.
\]
Given functions $\varphi_k$ and $\psi_l$ on $\mathbb{Z}/n\mathbb{Z}$ and an element $(s,t,\theta) \in G$, we have
\[
   \left(S_{(s,t,\theta)}\varphi\right)_k = \theta \varepsilon(sk)\varphi_{k + t} \mbox{ and } \left(T_{(s,t,\theta)}\psi\right)_l = \theta\varepsilon((l-s)t)\psi_{l-s}.
\]
The corresponding representation $R$ acts upon the space $F(M) = F\left((\mathbb{Z}/n\mathbb{Z})^2\right)$ via shifts: for  $(s,t,\theta) \in G$ and $f = f_{kl} \in F(M)$,
\[
     \left(R_{(s,t,\theta)}f\right)_{kl} = f_{k+t \, l -s}.
\]
Since the Berezin transform (\ref{E:fourber}) commutes with the representation $R$ it is shift-invariant and thus the functions $\e(rk + sl)$ with $r,s \in \mathbb{Z}/n\mathbb{Z}$ are its eigenfunctions.}

{\it Example 2.} Let $n$ be a fixed natural number. Set $K = \{1,2,\cdots,n\}$ and denote by $\mathfrak{S}_n$ the group of permutations of $K$ (the symmetric group). Fix a constant  $\theta$ such that $|\theta|=1$ and $\theta \neq \pm 1$. A simple check shows that the matrix $u = (u_{kl}),\, k,l \in K$, with
\begin{equation}\label{E:example2}
     u_{kl} = \delta_{kl} + \frac{\theta - 1}{n}
\end{equation}
has nonzero elements and is unitary. Denote by $\U \in \End F(K)$ the corresponding unitary operator (we assume that $F(K)$ carries the standard Hermitian structure).
Let $S$ be the unitary representation of the symmetric group $\mathfrak{S}_n$ in the space $F(K)$ by permutations: for $\sigma \in \mathfrak{S}_n$ and $\varphi = \varphi_k \in F(K)$,
\[
       (S_\sigma \varphi)_k = \varphi_{\sigma^{-1}(k)}.
\]
Since the operators $\U$ and $S_\sigma$ commute, the group $\mathfrak{S}_n$ is a symmetry group of the matrix $u$. According to Lemma \ref{L:unitary} the representation $R$ of the group $\mathfrak{S}_n$ in the Hermitian vector space $(F(M), \langle\cdot,\cdot\rangle_u)$
given by the formula
\[
     \left(R_\sigma f\right)_{kl} = f_{\sigma^{-1}(k)\sigma^{-1}(l)}.
\]
is unitary. Here $\sigma\in \mathfrak{S}_n$  and $f = f_{kl} \in F(M)$.

The representation $R$ has the following four isotypic components. Denote by $V_1$ the two-dimensional space of functions from $F(M)$ of the form $f_{kl} = a + b\delta_{kl}$, where $a$ and $b$ are constants. The group $\mathfrak{S}_n$ acts trivially on $V_1$. The space $V_2 \subset F(M)$ of functions of the form $f_{kl} = a_k + b_l + c_k\, \delta_{kl}$ where
\[
     \sum_{i = 1}^n a_i = \sum_{i = 1}^n b_i = \sum_{i = 1}^n c_i =0,
\]
is the isotypic component of multiplicity 3 of the representation $R$ corresponding to the irreducible representation of $\mathfrak{S}_n$ of dimension $n-1$ parametrized by the partition $(n-1,1)$ according to \cite{J}. The space $V_3 \subset F(M)$ of functions $f_{kl}$ such that $f_{kl} = -f_{lk}$ for all $k,l \in K$ and
\begin{equation}\label{E:zero}
     \sum_{l = 1}^n f_{kl} = 0
\end{equation}
is irreducible. It is parametrized by the partition $(n-2,1,1)$ and has the dimension
\[
     \dim V_3 = \frac{n^2 - 3n + 2}{2} = \frac{(n-1)(n-2)}{2}.
\]
Finally, the space $V_4 \subset F(M)$ of functions $f_{kl}$ such that $f_{kl} = f_{lk},\  f_{kk} = 0$ for all $k,l \in K$, and satisfying condition (\ref{E:zero}) is also irreducible. It is parametrized by the partition $(n-2,2)$ and has the dimension
\[
     \dim V_4 = \frac{n^2 - 3n}{2} = \frac{n(n-3)}{2}.
\]
The space $E \subset F(M)$ of functions of the form $f_{kl} = a_k + b_l$ is $\mathfrak{S}_n$-invariant. Therefore, its orthogonal complement $E^\bot$ with respect to the Hermitian product $\langle\cdot,\cdot\rangle_u$ is also $\mathfrak{S}_n$-invariant. The restriction of the representation $R$ onto $E^\bot$ is multiplicity free. It is the following orthogonal sum of irreducible subspaces:
\begin{equation}\label{E:direct}
 E^\bot = \left(V_1 \cap E^\bot\right) \oplus \left(V_2 \cap E^\bot\right) \oplus V_3 \oplus V_4.
\end{equation}
Using the facts that the Berezin transform $I_u$ commutes with the representation $R$ and acts trivially on the space $E$, we will find the spectral decomposition of the operator $I_u$. It is scalar on the direct summands in (\ref{E:direct}).

Given a function $f = f_{kl} \in V_3$, we will calculate the matrices $(x_{kk'})$ and $(y_{kk'})$ of the operators $C_uf$ and $D_uf$, respectively. Observe that $f_{kk} = 0$ for all $k \in K$. Using formulas (\ref{E:cdsymb}) and (\ref{E:zero}), we get
\begin{eqnarray*}
  x_{kk'} = \sum_{l\in L} \left(\delta_{kl} + \frac{\theta - 1}{n}\right) f_{kl}\left(\delta_{k'l} + \frac{\bar\theta - 1}{n}\right) =\\
\sum_{l\in L} \left(\delta_{kl}f_{kl}\delta_{k'l} + \frac{\theta - 1}{n} f_{kl}\delta_{k'l} + \delta_{kl} f_{kl} \frac{\bar\theta - 1}{n} + \left| \frac{\theta - 1}{n} \right|^2 f_{kl}\right) = \\
f_{kk}\delta_{kk'} + \frac{\theta - 1}{n} f_{kk'} + f_{kk}\frac{\bar\theta - 1}{n} = \frac{\theta - 1}{n} f_{kk'}.
\end{eqnarray*}
A similar calculation shows that
\[
   y_{kk'} = \frac{\bar\theta - 1}{n}\, f_{k'k} = - \frac{\bar\theta - 1}{n}\, f_{kk'} = \bar \theta\, \frac{\theta - 1}{n}\, f_{kk'} = \bar\theta\, x_{kk'}.
\]
Thus $D_uf = \bar\theta\, C_uf$, whence $I_u f = \bar\theta f$.

Now assume that $f = f_{kl} \in V_4$. Denote by $(x_{kk'})$ and $(y_{kk'})$ the matrices of the operators $C_uf$ and $D_uf$, respectively. Then similar calculations show that
\[
     x_{kk'} = \frac{\theta - 1}{n}\, f_{kk'} \mbox{ and } y_{kk'} = \frac{\bar\theta - 1}{n}\, f_{kk'} = - \bar\theta\,x_{kk'},
\]
whence $D_uf = -\bar\theta \, C_uf$ and therefore $I_u f = -\bar\theta\, f$.

Tedious but straightforward calculations render the eigenvalues of the operator $I_u$ on the eigenspaces $V_1\cap E^\bot$ and $V_2\cap E^\bot$. The spectral decomposition of the Berezin transform $I_u$ is summarized in the following table.

\medskip

\begin{tabular}{|l|c|c|c|c|c|}\hline
Eigenspace & $E$ & $V_1\cap E^\bot$ & $V_2\cap E^\bot$ & $V_3$ & $V_4$\\
\hline
Dimension & $2n-1$ & 1 & $n-1$ & $\frac{n^2 - 3n + 2}{2}$ & $\frac{n^2 - 3n}{2}$ \\
\hline
Eigenvalue & 1 & $-\theta \frac{\bar\theta + n -1}{\theta + n - 1}$ & $-\frac{\bar\theta + n - 1}{\theta + n - 1}$ & $\bar\theta$ & $-\bar\theta$\\
\hline
\end{tabular}

\medskip

Observe that the condition $\theta \neq \pm 1$ implies that the multiplicity of 1 in the spectrum of the Berezin transform $I_u$ is equal to $2n-1$.

\section{A mapping from the unitary to the doubly stochastic matrices}\label{S:geom}

Let $K$ and $L$ be two $n$-element index sets. Denote by $U$ the set of all unitary matrices $(u_{kl}), k\in K,l\in L$. It is a principal homogeneous space of the group of unitary matrices $(u_{kk'}), k,k'\in K$, and thus is a real $n^2$-dimensional compact manifold. Denote by $U_0$ the set of all unitary matrices from $U$ with nonzero entries. It is an open subset of $U$.

Let $B$ be the affine space of real matrices $(p_{kl}), k\in K,l\in L,$ satisfying the equations
\[
    \sum_{k \in K} p_{kl} =1 \mbox{ and } \sum_{l\in L} p_{kl} =1.
\]
Its dimension is $(n-1)^2$. The set $P$ of matrices from $B$ with nonnegative elements
is an $(n-1)^2$-dimensional convex polytope, the Birkhoff polytope (see \cite{Z}). Its elements are called doubly stochastic matrices. The Birkhoff polytope is the convex hull of the permutation matrices $(\delta_{\sigma(k)l})$, where $\sigma: K \to L$ is a bijection. Its interior consists of the doubly stochastic matrices with nonzero entries.

Two unitary matrices $u = (u_{kl})$ and $\tilde u = (\tilde u_{kl})$ from $U$ are called equivalent if there exist unitary diagonal matrices $\varkappa = (\varkappa_k \delta_{kk'}), k,k' \in K,$ and $\lambda = (\lambda_l \delta_{ll'}), l,l'\in L,$ such that $\tilde u = \varkappa u \lambda$, i.e., $\tilde u_{kl} = \varkappa_k u_{kl} \lambda_l$. We will write $u \sim \tilde u$ for equivalent matrices $u$ and $\tilde u$.

Denote by $\mu: U \to B$ the mapping that maps a unitary matrix $(u_{kl})$ to the doubly stochastic matrix $(|u_{kl}|^2)$. It is known that the image $\mu(U)$ is a proper subset of the Birkhoff polytope $P$ (see \cite{TZ}).

The mapping $\mu$ maps equivalent matrices to the same doubly stochastic matrix. Thus it factors through the singular qoutient space $U/\sim$. The quotient space $U_0/\sim$ is an $(n-1)^2$-dimensional manifold. These observations lead to the natural question of whether the mapping $\mu$ is a submersion. It is obvious that $\mu$ is not a submersion on the complement $U \backslash U_0$ since it is mapped to the boundary of the Birkhoff polytope. In the rest of this paper we will show that for each $n$ there exists a unitary $(n\times n)$-matrix $u$ such that $\mu$ is a submersion at $u$. Since $\mu$ is an algebraic mapping of real affine manifolds, this will imply that $\mu$ is a submersion for almost all elements of $U$.

Let $u = (u_{kl})$ be an arbitrary unitary matrix in $U$ and $\U: F(L) \to F(K)$ be the corresponding unitary isomorphism. We want to give different descriptions of the tangent space $T_u U$. Assume that $u(t) = u_{kl}(t) \in U$ is a family of unitary matrices smoothly depending on a small real parameter $t$ and such that $u(0) = u$. Then $u'(0) = (u'_{kl}(0))$ is a tangent vector in $T_u U$. Here we use that $U$ is a real submanifold in the affine space of complex-valued matrices $(x_{kl})$ with $k\in K$ and $l\in L$.
This way one can obtain all tangent vectors in $T_u U$. Each matrix $u(t)$ determines a unitary isomorphism $\U(t): F(L) \to F(K)$. Since $\U(t)(\U(t))^* = 1$ and $\U(0) = \U$, we get that
\[
           \U'(0)\U^* + \U(\U'(0))^* = 0.
\]
The operator
\begin{equation}\label{E:X}
     X = \U'(0)\U^* = - \U(\U'(0))^*
\end{equation}
in $F(K)$ corresponding to the tangent vector $u'(0)$ is skew-Hermitian. This correspondence identifies the tangent space $T_u U$ with the space of skew-Hermitian operators in $F(K)$.

Now assume that $u\in U_0$.  Corollary \ref{C:skew} allows to identify the space of skew-Hermitian operators in $F(K)$ (and thus the tangent space $T_u U_0$) with the space of $C$-symbols $f \in F(M)$ such that $f = - I_u\bar f$ and also with the space of $D$-symbols $g \in F(M)$ such that $I_ug = - \bar g$.

Formula (\ref{E:X}) implies that the matrix $(x_{kk'}), k,k'\in K,$ of the operator $X$ satisfies the following equations:
\begin{equation}\label{E:xkk}
    x_{kk'} = \sum_{l\in L} u'_{kl}(0) \bar u_{k'l} = - \sum_{l\in L} u_{kl} \bar u'_{k'l}(0).
\end{equation}
Assume that $f=f_{kl}$ and $g = g_{kl}$ are the $C$- and $D$-symbol of the operator $X$, respectively, that is,
\[
     X = C_uf = D_ug.
\]
It follows from formulas (\ref{E:cdsymb}) and (\ref{E:xkk}) that
\begin{equation}\label{E:fandgforX}
     f_{kl} = \frac{u'_{kl}(0)}{u_{kl}} \mbox{ and } g_{kl} = -\frac{\bar u'_{kl}(0)}{\bar u_{kl}}.
\end{equation}
In particular, $f = -\bar g$. Formulas (\ref{E:X}) and (\ref{E:fandgforX}) mean that the
$C$- and $D$-symbols are related to the perturbations of the matrix elements of $u$ while the operators corresponding to these symbols are related to the perturbations of the isomorphism $\U$.

The mapping $\mu$ maps the matrix $u(t) = (u_{kl}(t))$ to the doubly stochastic matrix $p(t) = (p_{kl}(t))$ such that
\[
     p_{kl}(t) = |u_{kl}(t)|^2 = u_{kl}(t)\bar u_{kl}(t).
\]
We set $p = p(0)$. The tangent mapping $\mu_{*u}$ maps the tangent vector $u'(0) \in T_{u}U_0$ to the tangent vector $p'(0) \in T_{p}P_0$. It follows from formulas (\ref{E:fandgforX}) that
\[
    p'_{kl}(0) = u'_{kl}(0)\bar u_{kl} + u_{kl}\bar u'_{kl}(0) = \left(f_{kl} - g_{kl}\right)|u_{kl}|^2.
\]
Thus the tangent vector $u'(0)\in T_u U_0$ lies in the kernel of the tangent mapping $\mu_{*u}$ if and only if the $C$- and $D$-symbols of the corresponding skew-Hermitian operator $X$ coincide, $f = g$, or, equivalently, $I_u g = g$, that is, $g$ is an eigenvector of the operator $I_u$ with the eigenvalue 1.
Since the operator $X$ is skew-Hermitian, according to Corollary \ref{C:skew}, $f = -\bar g$ and therefore the condition that $f = g$ implies that $g = -\bar g$, i.e., that $g$ is purely imaginary. We conclude that the kernel of the tangent mapping $\mu_{*u}$ can be identified with the space of purely imaginary eigenfunctions of the Berezin transform $I_u$ with the eigenvalue 1. Now, Lemma \ref{L:eigen} implies the following

\begin{theorem}\label{T:ker}
  Given a unitary matrix $u \in U_0$, the dimension of the kernel of the tangent mapping $\mu_{*u}$ is equal to the multiplicity of 1 in the spectrum of the Berezin transform $I_u$.
\end{theorem}

Theorem \ref{T:ker} and Example 2 from Section \ref{S:examples} show that the mapping $\mu$ is a submersion at the matrix $u = (u_{kl})$ given by (\ref{E:example2}). Thus, $\mu$ is a submersion almost everywhere on $U$.


TITLE: Bayes rules for 2 causes
QUESTION [1 upvotes]: Let's say I have $y \in \mathbb{R} \rightarrow x \leftarrow z \in \mathbb{R}^k $. I think I model $p(x,y,z) = p(x|y,z)p(z)p(y)$?
From that, I think that bayes rule says that
$$
p(z,y|x) = \frac{p(x|y,z)p(z)p(y)}{p(x)}
$$
Can I also derive that
$$
p(z,y|x) = \frac{p(x|y,z)p(z)p(y|x)p(x)}{p(x)} = p(x|y,z)p(z)p(y|x) \text{?}
$$

REPLY [1 votes]: From your derivation, you are implicitly implying that:
$$p(y)=p(y|x)p(x)$$
which is true unless $p(x,y)=p(y)$, because $p(x,y)=p(y|x)p(x)$
So do you also want to assume $p(x,y)=p(y)$? It is up to you, as you already have some assumption about joint distribution of $x,y,z$


TITLE: Need help with calculating this sum: $\sum_{n=0}^\infty\frac{1}{2^n}\tan\frac{1}{2^n}$
QUESTION [14 upvotes]: I need help with calculating this sum:
$$\sum_{n=0}^\infty\frac{1}{2^n}\tan\frac{1}{2^n}$$

REPLY [1 votes]: i just was reading this book yesterday


TITLE: Estimated time required to apply to matrix
QUESTION [0 upvotes]: I'm completely lost on this question, any help would be appreciated.
Suppose the application of the Gaussian Elimination algorithm on a 50 by 50 matrix is timed at 500 μ seconds. How much time do you estimate would be required to apply the algorithm to a 2000 by 2000 matrix? (Ignore any issues with respect
to the requirement for additional memory.)

REPLY [0 votes]: If you have the Big-O equation of this algorithm, $T(n)=O(n^3)$ (from Wiki), you will estimated the time:
$n_1 = 50, t_1=500=k\cdot n_1^3$
$n_2=2000=40 \cdot n_1 \Rightarrow t_2=k\cdot n_2^3=k \cdot (40n_1)^3=40^3\cdot t_1$


TITLE: A matrix equation equivalence
QUESTION [1 upvotes]: Let $\Omega_{\, m\times m}$ be a real square positive definite symmetric matrix, $u_{m\times 1}$ is a vector, $I_{m\times m}$ is the identity matrix.
Let $x$ be a solution of a matrix equation
$$ u^T(\Omega-x I)^{-1}u=1\tag{1}$$
I have hypothesised that the solution can be found as an eigenvalue problem of a matrix
$$\Lambda := \Omega - uu^T$$
i.e. $x$ satisfies the equation
$$\det\left(\Lambda-x I\right)=0.\tag{2}$$
Is this correct? Does the relation $(2)$ for $x$ indeed follow from $(1)$?
Motivation: I have managed to show the statement for $m=2$ and $m=3$ by diagonalisation of $\Omega$ and then concluded it can hold for higher $m$. It goes as follows... Let $\Omega=ODO^T$ be an orthonormal decomposition ($OO^T=O^TO=I$) with $D=\operatorname{diag}(\lambda_1,\lambda_2,\dots,\lambda_m)$ with $\lambda_1\leq\lambda_2\leq\dots\leq\lambda_m$. Let me denote $u=Ov$, then $(1)$ takes form
$$v^T(D-x I)^{-1}v=1\tag{3}$$
or
$$\sum_{k=1}^m \frac{v_k^2}{\lambda_k-x}=1\tag{4}.$$
For $m=2$ this becomes
$$v_1^2(\lambda_2-x)+v_2^2(\lambda_1-x)=\lambda_1\lambda_2 - x(\lambda_1+\lambda_2)+x^2,$$
which can be rearranged to
$$x^2 - x(\lambda_1+\lambda_2-(v_1^2+v_2^2))-\lambda_1\lambda_2\left(\frac{v_1^2}{\lambda_1}+\frac{v_1^2}{\lambda_1}\right)=0\tag{5}.$$
The relation $(2)$ becomes under decomposition
$$\det\left(D-vv^T-xI\right)=0\tag{6}$$
which is equal to
$$x^2-x\operatorname{Tr}\left(D-vv^T\right)+\det\left(D-vv^T\right)=0$$
which is, after some easy algebraic manipulations, equal to $(5)$. The similar proof holds for $m=3$. Is there, however, a general approach?

REPLY [2 votes]: Yes, it's correct since
$$\begin{eqnarray}
(\Lambda-xI)(\Omega-xI)^{-1}u&=&(\Omega-uu^T-xI)(\Omega-xI)^{-1}u\\
&=&(\Omega-xI)(\Omega-xI)^{-1}u-uu^T(\Omega-xI)^{-1}u\\
&=&u-u\cdot\left(u^T(\Omega-xI)^{-1}u\right)=u-u=0.
\end{eqnarray}$$ Hence $$
0\ne (\Omega-xI)^{-1}u\in \ker (\Lambda-xI)
$$ and $\det (\Lambda-xI)=0$ follows.

Addendum

If $\det(\Lambda -xI)=0$ and $(\Omega-xI)^{-1}$ exists, then $u^T(\Omega-xI)^{-1}u=1$.

Proof: Let $v\ne 0$ be a vector such that
$$
\Lambda v=xv,\quad\  \ \Omega v -(uu^T)v=xv.
$$ This gives
$$
(\Omega-xI)v=(u^Tv)u
$$ and
$$
v=(u^Tv)(\Omega-xI)^{-1}u.
$$ In particular, $u^Tv\ne 0$. By left-multiplying $u^T$ on both sides, it follows
$$
u^Tv = (u^Tv)\cdot u^T(\Omega-xI)^{-1}u.
$$ Since $u^Tv\ne 0$, we have
$$
1=u^T(\Omega-xI)^{-1}u.
$$


text:
\begin{document}

\title{Degenerate and star colorings of graphs on surfaces}

\author{Bojan Mohar\thanks{Supported in part by the ARRS (Slovenia),
   Research Program P1--0297, by an NSERC Discovery Grant and by
   the Canada Research Chair program. On leave from
   Department of Mathematics, IMFM \& FMF, University of Ljubljana,
   Ljubljana, Slovenia}\\
   Department of Mathematics\\Simon Fraser University\\Burnaby, B.C. V5A~1S6\\
   {\tt mohar@sfu.ca}
\and
   Simon \v Spacapan\thanks{Supported in part by the ARRS (Slovenia),
   Research Program P1--0297. The work was written during a post-doctoral
   visit of the second author at the Simon Fraser University, Canada}\\
   University of Maribor\\FME, Smetanova 17\\2000 Maribor, Slovenia\\
   {\tt simon.spacapan@uni-mb.si}
}

\date{\today}

\maketitle

\begin{abstract}
We study the degenerate, the star and the degenerate star chromatic numbers and their relation to the genus
of graphs. As a tool we prove the following strengthening of a result of Fertin et al. \cite{fertin}:
If $G$ is a graph of maximum degree $\Delta$, then $G$ admits a degenerate star coloring using $O(\Delta^{3/2})$ colors.
We use this result to prove that every graph of genus $g$ admits a degenerate star coloring with $O(g^{3/5})$ colors.
It is also shown that these results are sharp up to a logarithmic factor.
\end{abstract}

\bigskip
\noindent
{\bf Key words}: graph coloring, degenerate coloring, acyclic coloring, star coloring,
planar graph, genus

\bigskip\noindent
{\bf AMS Subject Classification (2000)}: 05C15

\section{Concepts}

Let $G=(V,E)$ be a graph. An {\em $n$-coloring} of $G$ is a function

$f:V\rightarrow \mathbb{N}$
such that $|f(V)|\leq n$.
We say that $f$ is a {\em proper} coloring if $f(x)\neq f(y)$ for every edge $xy\in E$.
A {\em color class} $C_i$ of $f$ is the set $f^{-1}(i)$, where $i\in f(V)$.
Two colorings $f$ and $g$ of $G$ are said to be {\em equivalent} if the partitions
of $V$ into color classes of $f$ and $g$ are equal.
Suppose that for each vertex $v\in V(G)$ we assign a \emph{list} $L(v)\subset \mathbb{N}$
of \emph{admissible colors} which can be used to color the vertex $v$.
A \emph{list coloring} of $G$ is a coloring  such that $f(v)\in L(v)$ for each $v\in V$. If for any
choice of lists $L(v),v\in  V$, such that $|L(v)|\geq k$,
there exists a proper list coloring of $G$, then we say that $G$ is {\em $k$-choosable}.
The {\em list chromatic number} of $G$, denoted as $\ch(G)$, is the least $k$, such that $G$ is $k$-choosable.

A proper coloring of $G$, such that the union of any two color classes induces a forest, is called an
{\em acyclic coloring}. The {\em acyclic chromatic number} of $G$, denoted as $\chi_a(G)$, is the least $n$
such that $G$ admits an acyclic $n$-coloring.

The notion of a degenerate coloring is a strengthening of
the notion of an acyclic coloring.
A graph $G$ is {\em k-degenerate} if every
subgraph of $G$ has a vertex of degree less than $k$. A coloring of a graph
such that for every $k\ge1$, the union of any $k$ color classes induces
a $k$-degenerate subgraph is a {\em degenerate coloring}.
The {\em degenerate chromatic number} of $G$, denoted as $\chi_d(G)$, is the least $n$
such that $G$ admits a degenerate $n$-coloring.

\begin{figure}[htb!]
\epsfxsize=4.0truecm
\slika{star-non-degen.eps}
\caption{An example of a star coloring which is not degenerate}
\label{star-non-degen}
\end{figure}

A proper coloring of $G$, with no two-colored $P_4$ is called a {\em star coloring}. This is
equivalent to saying that the union of any two color classes induces a star forest, i.e.
a subgraph whose every component is a star $K_{1,t}$ for some $t\ge 0$. The least
$n$ such that $G$ admits a star coloring with $n$ colors is called the {\em star chromatic number} of $G$,
denoted as $\chi_s(G)$.

If a coloring is both, degenerate and star, then we speak of
a {\em degenerate star coloring}. The corresponding
chromatic number is denoted as $\chi_{sd}$.

A proper list coloring is an acyclic coloring if the union of any two color classes induces a forest. The {\em
acyclic list chromatic number} $\ch_a$ is  the least $n$, such that for any assignment of lists of size $n$, there is an
acyclic list coloring of $G$. The definitions of list versions for all other types of chromatic numbers are
analogous to their non-list versions and we denote the list versions of chromatic numbers
by $\ch_a,\ch_d,$ $\ch_s$ and $\ch_{sd}$.

Clearly, $\chi_a(G)\leq \chi_d(G)\leq \chi_{sd}(G)$ and $\chi_a(G)\leq \chi_s(G)\leq \chi_{sd}(G)$.
However $\chi_d(G)$ and $\chi_s (G)$ are not comparable. To see this, note that
the degenerate chromatic number of a tree is two. However, for any tree $T$ which is not a star,
$\chi_s(T)\geq 3$. In Fig.~\ref{star-non-degen} we give an example of a graph whose star chromatic number is four,
but has no degenerate four-coloring (since its minimum degree is four).

It is well known that the list chromatic number of a graph of genus $g$ is $O(g^{1/2})$ (see e.g., \cite{MT}).
For acyclic colorings, Borodin proved in \cite{borodin} that every planar graph admits
an acyclic 5-coloring and thereby solved a conjecture proposed by Gr\"unbaum \cite{zelenodrevo}.
Alon et al.~\cite{alon1} determine the (asymptotic) dependence on the acyclic chromatic
number for graphs of genus $g$, where $g$ is large.
The corresponding bounds for the acyclic list chromatic number have not appeared in
the literature, but the proof in \cite{alon1} can be rather easily adapted to
give the same bounds for the list chromatic version.

It is also conjectured in \cite{borodin} that every planar graph can be colored with five colors,
so that the union of any $k$-color classes induces a $k$-degenerate graph for $k=1,\ldots,4$.
Rautenbach \cite{rauten} proved the existence of degenerate colorings of planar graphs using eighteen colors.
This result was recently improved to nine colors in \cite{MSZ}.

In  \cite{albert} it was proved that every planar graph admits a star
coloring with twenty colors and  that the star chromatic number of a graph of genus $g$ is $O(g)$.

\begin{table}[bht]
    \begin{center}
        \begin{tabular}{|l||c|c|l|}
            \hline
             & Planar & Upper bound & Lower bound \\
             \hline\hline
              $\ch(G)$ & ~~~~5 & $O(g^{1/2})$ & $\Omega(g^{1/2})$  \\
             \hline
             $\ch_a(G)$ & $\le ~7$ & $O(g^{4/7})$ & $\Omega(g^{4/7}/\log(g)^{1/7})$ \\
             \hline
             $\ch_d(G)$ & $\le ~9$ & $O(g^{3/5})$ & $\Omega(g^{4/7}/\log(g)^{1/7})$ \\
             \hline
             $\ch_s(G)$ & $\le 20$ & $O(g^{3/5})$ & $\Omega(g^{3/5}/\log(g)^{1/5})$ \\
             \hline
             $\ch_{sd}(G)$ & -- & $O(g^{3/5})$ & $\Omega(g^{3/5}/\log(g)^{1/5})$ \\
             \hline
        \end{tabular}
    \end{center}

    \caption{Bounds for chromatic numbers in terms of the genus ($g$)}
    \label{table}
\end{table}

The aim of this paper is to establish upper and lower bounds for the degenerate and the star
list chromatic numbers. We prove that the degenerate star choice number of a graph of
genus $g$ is $O(g^{3/5})$ thereby improving the bound $O(g)$ given in \cite{albert}.
We also prove that our bound is sharp up to a logarithmic factor.
These results in particular solve Problem 3 proposed in \cite[Section~8]{albert}.
The results of this paper and previously known results are collected in Table~\ref{table}.

\section{Probabilistic approach}

In this section we give upper bounds on the degenerate star choice number in terms of
the maximum degree. The proof uses the probabilistic method in a way similar to
that used in \cite{alon} and \cite{fertin} in the case of acyclic and star colorings.
It is based on the Lov\'asz Local Lemma but the proof is more complicated than the
corresponding proofs in \cite{alon} and \cite{fertin}. We refer to \cite{MoRe} for
applications of the probabilistic method to graph colorings.

For $X,Y\subseteq V$ we denote by $E(X,Y)$ the set of edges with one
endvertex in $X$ and the other in $Y$.

\begin{observation}
\label{obs:1}
Let\/ $G$ be a graph with minimum degree $k\geq 2$ and let $f$ be a proper $k$-coloring of\/ $G$.
If\/ $S$ is a non-empty subset of a color class $C_i$ of $f$, then there exist a color class
$C_j$ of $f$, such that $|E(S,C_j)|\geq \frac{k}{k-1}|S|>|S|$.
\end{observation}

\proof
Each vertex in $S$ has degree at least $k$. Therefore,
$$\sum_{j\neq i}|E(S,C_j)|\geq k|S|,$$
which implies the claimed inequalities. \qed

To prove the main result of this section, we will use the Lov\'asz Local Lemma stated below
(c.f. \cite{as} or \cite{MoRe}).

\begin{lemma} \label{local}
Let $A_1, A_2, \ldots, A_n$ be events in an arbitrary probability space. Let
$H=(V,E)$ be a graph whose vertices $V=\{1,2,\ldots,n\}$ correspond to the events $A_1, A_2, \ldots, A_n$
and whose edge-set satisfies the following: for each $i$, the event $A_i$ is mutually
independent of the family of events $\{A_j\,|\,ij\notin E\}$. If there exist real
numbers $0\leq w_i<1$ such that for all $i$
$${\rm Pr}(A_i)\leq w_i\prod_{ij\in E}(1-w_j)$$
then
$${\rm Pr}\big(\wedge_{i=1}^{n} \bar A_i\big)\geq \prod_{i=1}^n(1-w_i)>0\,,$$
so that with positive probability no event $A_i$ occurs.
\end{lemma}

Any graph $H$ satisfying the condition stated in the above lemma is called
a {\em dependency graph} for the events $A_1,\ldots,A_n$.

The following theorem is the main result of this section.
It is proved without an attempt to optimize the constant.

\begin{theorem} \label{main}
For any graph $G$ with maximum degree $\Delta$ there is a degenerate star list coloring
of\/ $G$ whenever the list of each vertex contains at least
$\lceil 1000\Delta^{ 3/2}\rceil$ admissible colors. Moreover, a list coloring exists
such that for every vertex $v$ of degree
at most $\Delta^{1/2}$, all neighbors of $v$ are colored differently.
In particular $\chi_{sd}(G)\leq \lceil 1000\Delta^{3/2}\rceil$.
\end{theorem}

\proof
Let $G$ be a graph with maximum degree $\Delta$ and let $\alpha=\lceil 1000 \Delta^{3/2}\rceil$.
Suppose that for each vertex $v$ of $G$ a list $L(v)$ of admissible colors is given and that
$|L(v)|=\alpha$. Consider the uniform probability space  of all list colorings of $G$.
Then each list coloring of $G$ appears with equal probability.

We will apply the Lov\'asz Local Lemma to show that in this probability space, a coloring of $G$
is a degenerate star list coloring, and has additional properties as stated in the theorem,
with positive probability. For this purpose, we define events of several types and show that if none of them occurs,
then the coloring is a degenerate star list coloring with the required properties.

\begin{figure}[htb!]
\epsfxsize=12.0truecm
\slika{forbid_subgraphs.eps}
\caption{The set of graphs $\mathcal{X}=\{A,B,C,D,E,F,I,J,K,L,M,S,T\}$}
\label{forbid}
\end{figure}

A pair of vertices at distance two having at least
$\Delta^{1/2}$ common neighbors is called a {\em special pair}.
We next define a family $\mathcal{F}$ of subgraphs of $G$. On Fig.~\ref{forbid} we give a set of graphs $\mathcal{X}$
and for each graph $X\in \mathcal{X}$, a coloring $g_X$ (as shown) is given.
Suppose that $R$ is a subgraph of $G$ isomorphic
to $X\in \mathcal{X}-\{S,T\}$
and let $i: V(X)\rightarrow V(R)$ be an isomorphism of these two graphs.
If for every pair $a,b\in V(X)$, having the same color under $g_X$, the pair $i(a),i(b)$ is not a special pair
in $G$, then $R$ is in $\mathcal{F}$. Moreover, $\mathcal{F}$ contains all special pairs
of vertices and all paths $x_1x_2x_3$ such that
$\deg_G(x_2)\leq \Delta^{1/2}$.

Let $f$ be a random list coloring of $G$. For $R\in \mathcal{F}$,
denote by $X_R$ the event that the induced coloring $f_{|R}$ on $R$ is equivalent to
the coloring $g_X$, where $R\in \mathcal{F}, X\in \mathcal{X}$ and $R\cong X$.

We refer to an event $X_R$ as an event of type X.  \\

{\sc Claim 0:} If no event $X_R$ occurs for  $X\in \mathcal{X}$, and $R\in \mathcal{F}$,
then the coloring $f$ of $G$ is a degenerate star coloring such that for every vertex
of degree $\leq\Delta^{1/2}$ all its neighbors are colored by pairwise different colors.\\

{\em Proof:} Let us observe that the definition of the set $\mathcal{F}$ includes
the condition that vertices of the same color do not form a special pair.
However, knowing that events of type S do not occur, we may simply forget about this
condition in the rest of the proof. In particular, if a subgraph $X$ of $G$ is isomorphic
to some $Y\in \mathcal{X}-\{S,T\}$, then its coloring $f_{|X}$ is not equivalent to $g_Y$.

Since no event of type A, B, or T occurs, the coloring $f$ is a star coloring such that any vertex of degree
at most $\Delta^{1/2}$ has its neighbors colored by pairwise different colors. It remains to prove that the coloring is degenerate.
Suppose on the contrary, that there is a subgraph $Q$ of $G$ with minimum degree $k$ colored by $k$ colors.
Since $f$ is a proper coloring, we have $k\geq 2$.
Then there exists a vertex $x\in V(Q)$ of (say) color 1 adjacent to two vertices $y,z$ of color 2 (see Observation \ref{obs:1}).
Furthermore, there is a color class $P$ of $f_{|Q}$, such that $|E(\{y,z\},P)|\geq 3$.
Since events of type B do not occur, the color of $P$ is not 1 or 2. Similarly we see that
$N(y)\cap N(z)\cap P=\emptyset$. As events of type C are excluded, there
are three vertices $u,v,w\in P$, such that $u,v$ are adjacent to $y$ and $w$ is adjacent to $z$.
Let $Y=\{u,v,w\}$. Then there is a color class $P'$ such that $|E(Y,P')|\geq 4$. Since  events of type
B, D, E, and F do not occur, $P'$ is distinct from the color classes 1 and 2. If $|N(Y)\cap P'|\geq 4$ then
(since B and C do not occur) an event of type I, K, L or M happens, a contradiction.
If $|N(Y)\cap P'|\leq 3$, then a similar argument shows that either type J or type E event occurs. This contradiction proves the claim.
\qed

Let $H$ be the graph with vertices $X_R$ ($X\in \mathcal{X}, R\in \mathcal{F}, R\cong X)$,
in which two events $X_{R_1}$ and $Y_{R_2}$ ($X,Y\in \mathcal{X}$) are adjacent if and only
if $R_1\cap R_2\neq \emptyset$. Since every vertex gets its color independently from others,
$X_R$ is mutually independent of the family of events $Y_{R'}$
($Y\in \mathcal{X}, R'\in \mathcal{F}, R'\cong Y, R\cap R'=\emptyset)$.
Therefore, the graph $H$ is a dependency graph for the events $X_R$.

\bigskip
{\sc Claim 1:} Let  $X\in \mathcal{X}, R\in \mathcal{F}$ and  $R\cong X$.
Then for every $Y\in \mathcal{X}-\{S\}$, the number of events of type Y adjacent to $X_R$ in $H$
is at most $100 \Delta^{|Y|-1}$.\\

{\em Proof}:  If  $X_R$ is adjacent to $Y_{R'}$, then there is a vertex $u\in R\cap R'$.
There are $|X||Y|$ possibilities to choose a one-vertex intersection of $R$ and $R'$.
Since $G$ has maximum degree $\Delta$ and $R'$ is connected, there are at most $\Delta^{|R'|-1}$ ways to
choose the other vertices of $R'$. It follows that there are
at most $|X||Y|\Delta^{|Y|-1}$ graphs isomorphic to $Y$ whose intersection with $R$ is nonempty.
The result follows from the fact that $|X|\leq 10$ for all $X\in \mathcal{X}$. \qed

{\sc Claim 2:}  Let  $X\in \mathcal{X}, R\in \mathcal{F}$ and $R\cong X$.
Then the number of events of type J adjacent to $X_R$ in $H$ is at most $90 \Delta^{15/2}$.\\

{\em Proof:} There are $9|R|\leq 90$ possibilities to choose
a one-vertex intersection of $R$ with a graph $R'$ isomorphic to $J$. Let
$i:V(R')\rightarrow V(J)$ be an isomorphism and recall that any pair of vertices
$a,b$ in $R'$ with $g_J(i(a))=g_J(i(b))$ is not a special pair. In particular, a pair of vertices in
the four-cycle of $R'$ is not a special pair. Therefore there are at most
$\Delta^{1/2}$ ways to choose a common neighbor of this pair. Since there is a vertex of $R'$ that
can be chosen in at most $\Delta^{1/2}$ ways, we conclude that there are at most
$\Delta^{1/2}\Delta^7$ ways to chose the graph $R'$, when a one-vertex intersection of $R$ and $R'$ is fixed. \qed

{\sc Claim 3:} Let  $X\in \mathcal{X}, R\in \mathcal{F}$ and  $R\cong X$.
Then the number of events of type S adjacent to $X_R$ in $H$ is at most $10\Delta^{3/2}$.\\

{\em Proof:} For a fixed vertex $u\in R$ there are less than $\Delta^2$ induced paths of length 2
with one endvertex $u$. Each special pair of vertices requires $\Delta^{1/2}$ of these paths.
Thus there are at most $\Delta^2/\Delta^{1/2}$ vertices $v$, such that $u,v$ is a special pair.
It follows that the number of special pairs intersecting $R$ is at most $|R|\Delta^{3/2}\leq 10\Delta^{3/2}$.
\qed

{\sc Claim 4:} Let  $X\in \mathcal{X}, R\in \mathcal{F}$ and  $R\cong X$.
Then the number of events of type T adjacent to $X_R$ in $H$ is at most $30\Delta^{3/2}$.\\

{\em Proof:} If $X_R$ and $T_{R'}$ are adjacent in $H$, then $R$ and $R'$ have nonempty intersection.
There are at most $3|R|$ ways to choose a one-vertex intersection of $R$ and a
path $x_1x_2x_3$. Since $\deg_G(x_2)\leq \Delta^{1/2}$, the other two vertices of $R'$
can be chosen in at most $\Delta^{3/2}$ ways. It follows that there are at most
$3|R|\Delta^{3/2}\leq 30\Delta^{3/2}$ events of type T adjacent to $X_R$ in $H$.
\qed

The following table gives upper bounds ${\rm P}(X_R)$ on probabilities of events $X_R$ of different types $X\in \mathcal{X}$:
 \begin{center}
        \begin{tabular}{|c|c|c|c|c|c|}
            \hline
  		Type & A, S, T &  B, C & D, E, F, M & J & I, K, L  \\
            \hline
            P$(X_R)$ & $\alpha^{-1}$ & $\alpha^{-2}$ & $\alpha^{-4}$ & $\alpha^{-5}$ & $\alpha^{-6}$  \\
            \hline
    \end{tabular}
    \end{center}

Let us define the weights for the Local Lemma \ref{local}.
For each event $X_R$ of type X, let the weight be $w_X=2\, {\rm P}(X_R)$.
Set $\mathcal{T}=\mathcal{X}-\{J,S,T\}$. To be able to apply Lemma \ref{local} it suffices to show that
$$
   {\rm P}(X_R) \leq w_X (1-w_J)^{90\Delta^{15/2}}(1-w_S)^{10\Delta^{3/2}}
   (1-w_T)^{30\Delta^{3/2}}\prod_{Y\in \mathcal{T}} \left( 1-  w_Y \right)^{100\Delta^{|Y|-1}}.
$$
To prove this, observe that $1-nx\leq (1-x)^n$, so it suffices to show that
$$
   \frac 12 \leq (1-90 w_J\Delta^{15/2})(1-10w_S\Delta^{3/2})(1-30 w_T\Delta^{3/2})
   \prod_{Y\in \mathcal{T}} ( 1-  100 w_Y \Delta^{|Y|-1}).
$$
But this is easily seen to be true, since the weights for the events are
$w_J=2\alpha^{-5}\leq 2\cdot 10^{-15}\Delta^{-15/2}$ and
$w_A=w_S=w_T=2\alpha^{-1}\leq 2\cdot 10^{-3}\Delta^{-3/2}$ and
$w_Y\leq 2\cdot 10^{-6} \Delta^{1-|Y|}$ for $Y\in \mathcal{X}-\{J,A,S,T\}$.

To conclude, Lemma \ref{local} applies and shows that there exists a coloring $f$ for which
no event $X_R$ ($X\in \mathcal{X}$, $R\in \mathcal{F}$) occurs.
Finally, Claim 0 shows that $f$ is a coloring whose existence we were to prove.
\qed

\section{Degenerate star colorings for graphs of genus $g$}

An {\em orientation} of a graph $G$ is a function $h:E(G)\rightarrow V(G)$, such that
for each edge $e=xy\in E(G)$, $h(e)\in \{x,y\}$. We call $h(e)$ the {\em head} of $e$
and  the other endvertex of $e$ the {\em tail} of $e$.
Let $G$ be a graph and $h$ an orientation of $G$.
The set of {\em in-neighbors} of $v$ is
$$N^-(v)=\{u\in V(G)\,|\,uv\in E(G),h(uv)=v\}$$
and the set of {\em out-neighbors} of $v$ is
$$N^+(v)=\{u\in V(G)\,|\,uv\in E(G),h(uv)=u\}\,.$$
If $c$ is a coloring of $G$, we define the set of {\em in-colors} $C^-(v)$, and
{\em out-colors} $C^+(v)$ of $v$ as $C^\pm(v) = \{ c(u) \,|\, u\in N^\pm(v)\}.$

The following lemma is a simple, yet effective, tool for recognition of star colorings.
We prove it for the sake of completeness although an equivalent result appears
in \cite{albert} and some other papers.

\begin{lemma} \label{star} A proper coloring of $G$ is a star coloring if and only if the edges of G
can be oriented so that for every vertex $v$

$$|N^-(v)|=|C^-(v)| { ~~and~~} C^-(v) \cap C^+(v) = \emptyset\,.$$
\end{lemma}

\proof
Suppose that $c$ is a star coloring of $G$. Then the union of any two color classes induces
a star forest. Orient the edges with one endvertex in color class $A$ and the other
in color class $B$ so that the tail of each edge is the root of a star induced by $A$ and $B$
(the root of a star, which is not a $K_2$, is the vertex of degree at least two, and
the root of $K_2$ is any vertex of $K_2$).
It is straightforward that so defined orientation satisfies both conditions from the lemma.

Conversely, let $c$ be a proper coloring of $G$ and $h$ an orientation of $G$ with properties as
stated in the lemma. Suppose that $x_1x_2x_3x_4$ is a two-colored path on four vertices and
(without loss of generality) assume that $h(x_2x_3)=x_3$. Since the in-neighbors of
$x_3$ are colored by pairwise different colors, we have $h(x_3x_4)\neq x_3$.
Since $C^-(v) \cap C^+(v) = \emptyset$ we see that $h(x_3x_4)\neq x_4$, a contradiction.
\qed

The following observation will be used in a recursive construction of degenerate colorings.

\begin{observation}
\label{miki}
Let $G$ be a graph and let $c$ be a degenerate coloring of a vertex-deleted
subgraph $G-v$. If the neighbors of $v$ are colored by pairwise distinct
colors and we color $v$ by a color which is different from all of those colors,
then the resulting coloring of $G$ is degenerate.
\end{observation}

We are ready for our main result. Its proof is given without intention to optimize
constants. Let us recall that a surface has {\em Euler genus} $g$ if its Euler
characteristic is equal to $2-g$.

\begin{theorem} \label{genus}
Let $G$ be a simple graph embedded on a surface of Euler genus $g$.
Then $\ch_{sd}(G)\leq \lceil 1000g^{3/5}+100000\rceil.$
\end{theorem}

\proof
Let $\Sigma$ be a surface of Euler genus $g$, and let $G$ be a graph embedded on $\Sigma$.
For a vertex $v\in V(G)$, let $L(v)$ be the list of admissible colors.
We shall prove a stronger statement that $G$ admits a degenerate star list
coloring from lists of size at least $\alpha:=\lceil 1000g^{3/5}+100000\rceil$,
such that every vertex of degree $\leq 12$ has its neighbors colored by pairwise distinct colors.
We will reduce the graph $G$ by using a sequence of edge contractions so that in the resulting
graph $G_0$ the number of vertices of degree at least
$\Delta_0:=\lceil \tfrac{1}{4} g^{2/5}+12\rceil $ is at most $\alpha_0:=\lceil 48 g^{3/5}\rceil$.
We say that a vertex $v$ of $G$ is {\em reducible} if its degree is either at most two,
or its degree is equal to $5-i$ and $v$ is adjacent to a vertex of degree $\leq 9+i$
for some $i\in \{0,1,2\}.$

We define a sequence of graphs $G=G_\ell,G_{\ell-1},\ldots, G_0$ as follows.
We start with $G_\ell = G$, and the precise value of $\ell$ will be determined later.
Suppose that we have the graph $G_t$. If it has no reducible vertices,
then we stop and adjust the indices so that the current graph is $G_0$ and $\ell$ is
the number of reductions used to get $G_0$ from $G$. Otherwise, let $v$ be a reducible
vertex of $G_t$. In order to obtain $G_{t-1}$, we perform the following reduction.
If $v$ has degree at most 1, then delete $v$; if $v$ has degree 2, then delete
$v$ and add an edge between the neighbors of $v$
(if not already present). Otherwise, $v$ is of degree $5-i$ where $i\in \{0,1,2\}$. In this case
contract the edge joining $v$ and a neighbor $u$ of degree at most $9+i$ (and delete possible multiple edges
that appear after the contraction). The new vertex inherits the list $L(u)$ of admissible colors from $u$.

Let the vertex set of $G_0$ be $\{v_1,v_2,\ldots,v_n\}$,
where $\deg(v_i)\leq \deg(v_{i+1})$ for $i=1,\ldots,n-1$.\\

\noindent {\sc Claim 0:} The number of vertices in $G_0$ of degree at least $\Delta_0$ is at most $\alpha_0$. \\

{\em Proof:} Suppose (reductio ad absurdum) that $\deg(v_k)\geq \Delta_0$, where  $k= n-\alpha_0$.
Since $G_0$ is a minor of $G$, it has an embedding in the same surface $\Sigma$ of Euler genus $g$ as $G$ has.
Let $\mathcal{F}$ be the set of faces of this embedding.
Let $c(v_i)=\deg(v_{i})-6$ for $i=1,\ldots,n$ and for each face $f\in \mathcal F$ let $\bar c(f)=2\deg(f)-6$, where
$\deg(f)$ is the length of $f$.
Euler's formula for $\Sigma$ implies (cf., e.g., \cite{MT}) that
$$
  \sum_{i=1}^n   c(v_i)+\sum_{f\in \mathcal F} \bar c(f)\leq 6g-12\,.
$$
Now let $c'(v_i)=\frac 12 \deg(v_{i})$ if $i>k$ and $c'(v_i)=c(v_i)$ otherwise. Then
\begin{eqnarray*}
 \sum_{i=1}^n c'(v_i)+\sum_{f\in \mathcal F} \bar c(f)&=&\sum_{i=1}^n c(v_i)+
 \sum_{i=k+1}^n \left (6-\tfrac 12 \deg(v_i)\right )+\sum_{f\in \mathcal F} \bar c(f) \\
 & \leq& 6g-12+6\cdot 48g^{\frac 35} - 24 g^{\frac 35}\big( \tfrac 14g^\frac25+12\big) < 0\,.
\end{eqnarray*}
Let $c''$ be obtained from $c'$ and $\bar c$ by the following discharging rules,
which preserve the left hand side of the above inequality.
From each face $f\in \mathcal F$ with $\deg(f)\ge4$ send charge $1$ to each vertex
of degree 3 lying on the boundary of $f$. If $\deg(f)\ge4$ and three consecutive vertices
on its boundary have degrees $\deg(v_1)\in\{4,5\}$, $\deg(v_2)=11$, and
$\deg(v_3)\in\{4,5\}$, then $f$ sends charge $1$ to $v_2$ as well. Further, send charge
$1$ from each vertex $x$ of degree $\geq 11$ to each neighbor $y$ of degree 3
such that the edge $xy$ is incident with two faces of length $3$,
and  send $1/2$ to other neighbors of degree 3 and to each neighbor of degree 4 or 5.
Finally, send $1/5$ from each vertex of degree $10$ to each neighbor of degree 5.

Our goal is to show that $c''(x)\ge 0$ for every $x\in V(G_0)\cup \mathcal{F}$.
This will imply that
$$
  \sum_{i=1}^n c'(v_i)+\sum_{f\in \mathcal F} \bar c(f) =
  \sum_{x\in V(G_0)\cup{\mathcal F}} c''(x) \ge 0\, ,
$$
which will in turn contradict the above inequality.

Since $G_0$ has no reducible vertices, a face $f\in \mathcal{F}$ has at most
$\lfloor \tfrac{1}{2}\deg(f)\rfloor$ incident vertices whose degree is 3, or is 11
(and their neighbors on $f$ have degree 4 or 5).
It sends charge $1$ to them. Therefore,
$$
   c''(f) \ge \bar c(f) - \tfrac{1}{2}\deg(f) \ge 0
$$
whenever $\deg(f)\ge4$. Clearly, $c''(f) = \bar c(f) = 0$ if $\deg(f)=3$.

It is easy to see that each vertex $v$ of degree at least 12 sends charge at most
$\tfrac{1}{2}\deg(v)$, so that $c''(v) \ge c'(v) - \tfrac{1}{2}\deg(v) \ge 0$.
It is also clear that for a vertex of degree ten, $c''(v) \ge c'(v) - \tfrac{1}{5}\cdot 10 > 0$.
If $v$ has degree 11, then $c'(v)=5$. The vertex may send charge $\tfrac{1}{2}$ to
all its neighbors (if they all have degrees 4 or 5). This is the only situation where
its charge $c''(v)$ may become negative. However, in such a case $v$ receives
$1$ from each of its neighboring faces (which are of length at least 4 since there
are no reducible vertices). Therefore, $c''(v)\ge0$ holds in every case.
Vertices of degrees between 6 and 9 have not changed their charge. The reader
will verify that vertices of degrees 3, 4, or 5 have $c''(v)\ge0$ as well.

In conclusion, we have $c''(v)\geq 0$ for every $v\in V(G_0)$ and we have
$c''(f)\geq 0$ for every $f\in \mathcal F$. This yields a contradiction. \qed

Let $k=n-\alpha_0$ be as in the above proof, and let $S=\{v_i\,|\,i>k\}$ be the set of
{\em special vertices}.
For each special vertex $v_i$ we choose a color
$f_{v_i}\in L(v_i)$ so that $f_{v_i}\neq f_{v_j}$ whenever $i\neq j$.
This is possible since $|L(v_i)|>|S|=\alpha_0$. Define new lists of admissible colors
for the remaining vertices $v\in V(G)-S$:
$$L'(v)=L(v)-\{f_{v_i}\,|\,i>k\}\,.$$
Note that $|L'(v)|\geq |L(v)|-\alpha_0$ and by Claim 0,  $\deg_{G_0}(v_k)\leq \Delta_0$.
If $\deg_{G_0}(v_k)\leq 144$, then we color the graph induced by vertices $v_1,\ldots,v_k$
by a distance-two list coloring with $144^2$ colors, where the distance-two coloring is
a proper list coloring of $G_0$ such that any two vertices at distance two are colored differently.
If $\deg_{G_0}(v_k) > 144$, then we give the graph induced by vertices
$v_1,\ldots,v_k$ a degenerate star list coloring with $\lceil 1000 \Delta_0^{3/2}\rceil$ colors,
where the color for $v_i$ is taken from the list $L'(v_i)$ (see Theorem \ref{main}).
This is possible since $\max\{144^2, 1000\Delta_0^{3/2}\}\leq |L'(v_i)|$.
Since $\Delta_0>144$, Theorem \ref{main} assures that each vertex of degree at most 12 has
its neighbors colored by different colors. Then we color
each special vertex $v_i$ ($i>k$) with the color $f_{v_i}$, which completes the coloring
of $G_0$. Note that each color used for special vertices has been
used only once altogether, since it has been deleted from the lists. Therefore
the coloring of $G_0$ is a degenerate star coloring,
because the subgraph $G_0-S$ was given a degenerate star coloring.

Now we extend this coloring to a coloring of $G$. Observe that while contracting an edge $uv$
(where $v$ was a reducible vertex in $G_t$) when going from $G_{t+1}$ to $G_{t}$,
all vertices preserve their neighbor set except for the common neighbors of $u$
and $v$ and for the new vertex (which is again denoted by $u$)
obtained after the contraction. Observe that $\deg_{G_t}(u)\leq 12$.

When we go back from $G_t$ to $G_{t+1}$, we add the vertex $v\in V(G_{t+1})-V(G_t)$.
By induction, the coloring of $G_t$ is a degenerate star coloring. Therefore, we can orient
the edges of $G_t$ so that $|N^-(x)|=|C^-(x)| {\rm ~~and~~} C^-(x) \cap C^+(x) = \emptyset$
for each vertex $x\in V(G_t)$.

We color the vertex $v$
by a color in $L'(v)$ so that the neighbors of each vertex $x\in N_{G_{t+1}}(v)$ with $\deg_{G_{t+1}}(x)\leq 12$ receive
pairwise different colors and so that the color of $v$ is different from the colors of its neighbors and the colors in
$C^-(x)$, where $x\in N_{G_{t+1}}(v)$.
We extend the orientation of $G_t$ to an orientation of $G_{t+1}$ by orienting all edges incident to  $v$ towards $v$.
Observe that by doing so $|C^-(x)-\{f_{v_i}\,|\, i>k\}|$ remains bounded by $\Delta_0$
for each $x\in V(G_{t+1})-S$.
Since $|L'(v)| > 4(\Delta_0+1)+12$, there is always an available color.

We claim that so defined coloring of $G_{t+1}$ is a degenerate star coloring with neighbors of each vertex
of degree at most 12 colored by different colors.
Suppose that $G_t$ was obtained from $G_{t+1}$ by contracting the edge $vu$, where
$\deg_{G_{t+1}}(v)=5-i$ and $\deg_{G_{t+1}}(u) \le 9+i$ for some $i\in\{0,1,2\}$.
Then $\deg_{G_{t}}(u)\leq 12$. Therefore $u\in V(G_t)$ has all neighbors colored
by pairwise different colors and hence also
$v\in V(G_{t+1})$ has all neighbors colored by pairwise different colors.
The same is also true if the reduced vertex $v$ is of degree 1 or 2.
It follows from Observation \ref{obs:1} that the coloring of $G_{t+1}$ is degenerate.
We infer from the definition of the coloring (and orientation) that the set of
in-colors and the set of out-colors of each vertex are disjoint and, moreover, the in-neighbors of a vertex
receive pairwise different colors. This shows that the coloring is also a star
coloring and completes the proof. \qed

\section{Lower bounds}

In this section we provide lower bounds which show that the upper bound given
in Theorem \ref{genus} is asymptotically tight up to a polylogarithmic factor.
It is interesting to note that the lower bound construction is also based on
the probabilistic method, although in an essentially different way as in the proof of
Theorem \ref{main} used to establish the upper bound.

Let $\mathcal F$ be a family of connected bipartite graphs, each of order at least three.
A proper coloring of $G$ is {\em $\mathcal F$-free} if it contains no two-colored subgraph
isomorphic to a graph $F\in \mathcal F$. The least $n$ such that $G$ admits an $\mathcal F$-free coloring
with $n$ colors is denoted by $\chi_{\mathcal F}(G)$.

Special cases of the following lemma have  appeared in \cite{alon}, \cite{alon1}, and \cite{albert}.
Here $|G|$ and $||G||$ denote the number of vertices and the number of edges of $G$, respectively.

\begin{lemma} \label{ccc}
Let $\mathcal{F}$ be a family of connected bipartite graphs on at least three vertices and let
$F\in \mathcal{F}$ be a graph with\/ $\Vert F\Vert$ minimum. Let $G=G_{n,p}$ be the random graph on
$n$ vertices where each pair of vertices is connected by an edge, randomly and independently,
with probability $$p=9\Bigl(\frac {\log n}{n}\Bigr)^{1/||F||}\,.$$
Then almost surely (that is, with probability tending to one as $n$ tends to infinity),
$G$ has at most $$9 n^{(2||F||-1)/||F||}(\log n)^{1/||F||} $$
edges and $\chi_{\mathcal F}(G)>\tfrac{1}{2|F|}\,n$.
\end{lemma}

\proof It is a standard observation that the number of edges of a random graph with
edge probability $p$ is almost surely less than $pn^2$ (see, e.g., \cite{as}).
This proves the claim about $||G||$.

Let $A\cup B$ be the bipartition of the vertex set of $F$. Set $a=|A|$ and $b=|B|$ and assume that $a\geq b$.
Suppose that $V_1,\ldots, V_k$ is a partition of the vertex set of $G$ into $k\leq \tfrac{1}{2}n/|F|$ parts.
Then we delete at most $a-1$ vertices in each $V_i$ so that there is a partition of each $V_i$ into
sets $U^i_1,\ldots, U^i_{k}$ of size $a$ or $b$ and so that (in all partitions together)
the number of sets of size $a$ equals (or differs by one) the number of sets of size $b$.
The number of deleted vertices  will be at most $\tfrac{1}{2}(a-1)n/|F| < n/2$ and therefore there
are at least $n/2a$ pairwise disjoint sets $U^j_\ell$
whose size is $a$ or $b$ and each of them is a subset of a member of the partition $V_1,\ldots, V_k$.
Since the number of $a$-sets is essentially the same to the number of $b$-sets
we conclude that there are at least $n/4a$ sets of size $a$ and at least $n/4a$ sets of size $b$.
The probability that the partition $V_1,\ldots, V_k$ is an $\mathcal F$-free coloring
is at most
$$
  (1-p^{||F||})^{(n/4a)^2}< {\rm exp}(-(9^{||F||}/16a^2) n\log n)\le n^{-{81 n/64 }}\,.
$$
The last inequality follows from $||F||\geq a\geq 2$. Since there are less than $n^n$ partitions
of the vertex set of an $n$-vertex graph into at most $n/(2|F|)$ classes
we conclude that the probability that an $\mathcal F$-free coloring with at most $n/(2|F|)$ colors exists
tends to $0$ as $n$ tends to infinity.
\qed

\begin{theorem}
For every large enough $g$, there is a graph $G$ embeddable in an orientable (resp. non-orientable) surface of genus $g$,
such that $\chi_{sd}(G)\geq \chi_s(G)\geq \tfrac{1}{32}g^{3/5}/ (\log g)^{1/5}.$
\end{theorem}

\proof
Let ${\mathcal F}=\{P_4\}$ and let $G$ be a graph of order $n$ with at most
$9 n^{5/3}(\log n)^{1/3}$ edges and $\chi_s(G)\geq n/8$ (see Lemma \ref{ccc}).

It is easy to see that $G$ embeds in an orientable (resp. non-orientable) surface of Euler genus
$g_0=||G||-1\leq \lceil 9 n^{5/3}(\log n)^{1/3}\rceil=:g$ (in fact, every 2-cell embedding of $G$ satisfies this bound).
Since $g>n^{5/3}$, it follows that $\log g>\tfrac{5}{3}\log n$. Substituting this to $$g<9 n^{5/3}(\log n)^{1/3}+1$$
we conclude that $$n>\tfrac{1}{4}g^{3/5}/(\log g)^{1/5}\,$$
(for large enough $g$) and hence the theorem follows from $\chi_s(G)\geq n/8$.
\qed

\bigskip
\noindent
{\em Acknowledgement:} We are grateful to Ken-ichi Kawarabayashi for some preliminary
discussions concerning the star chromatic number.

config: arxiv


TITLE: Translation operator eigenvalues can be real and arbitrary?
QUESTION [4 upvotes]: Consider the translation in space operator in $1D$:
$$D(a)=e^{-ia\hat{p}/\hbar}$$
It is unitary - $D(-a)=D^{\dagger}(a)=D^{-1}(a)$ - which implies that $D(a)$ has eigenvalues on the unit circle like all unitaries do.
$D(a)$ acts on a function $f(x)$ by translating it -
$$D(a)f(x)=f(x-a)$$
Now consider the case of $f(x)=e^{\lambda x}$:
$$D(a)f(x)=e^{\lambda(x-a)}=e^{-\lambda a}e^{\lambda x}=e^{-\lambda a}f(x)$$
So $f$ is an eigenfunction of the translation operator with eigenvalue $e^{-\lambda a}$ which may be arbitrary large or small for sufficient $\lambda$.
It appears we arrived at a contradiction. How is it solved? Is it enough to consider only eigenfunctions that are normalized wavefunctions? Is it possible that $D(a)$ has eigenstates that are not orthogonal to each other?

REPLY [6 votes]: Are you  working on the whole real line? If so, then $e^{\lambda x}$ is not normalizable even in the rigged Hilbert space (i.e. delta function normalizations) sense, so $e^{\lambda x}$ is not in the domain of the translation operator. If you are working with periodic boundary  condition $\psi(x)=\psi(x+L)$ then  $e^{\lambda x}$ is not in the Hilbert space   unless $\lambda= 2\pi i n/L$ for integer $n$. If you are working on a finite interval with boundary consitions such as $\psi(0)=\psi(L)=0$, then $\hat p$ has no eigenvalues because it  not self-adjoint and  $e^{i\hat p a}$ is not unitary.


TITLE: When can we write $f(v)dv=f(E)dE$?
QUESTION [2 upvotes]: In statistical thermodynamics we write
$$f(v)\,dv = f(E)\,dE$$
where $v$ is velocity and $E= \frac12mv^2$  is energy
and $f$ refers to the distribution function
Can someone explain the logic behind?

REPLY [0 votes]: The distribution function has the property:
$f(v) = \frac{dn}{ndv} $
& $f(E) = \frac{dn}{ndE} $
Hence $f(v)dv=f(E)dE=\frac{dn}{n}$


TITLE: Proof of expectation of exponential distribution
QUESTION [0 upvotes]: I need help with understanding the proof of expectation of exponential distribution:
$$\begin{align}
E(X) & = \int_0^\infty x\lambda e^{-\lambda x}dx\\
& = [-xe^{-\lambda x}]_0^\infty + \int_0^\infty e^{-\lambda x}dx\\
& = (0-0) + [-\frac{1}{\lambda} e^{-\lambda x}]_0^\infty\\
& = 0 + \left(0 + \frac{1}{\lambda}\right)\\
& = \frac{1}{\lambda}\\
\end{align}$$
I found myself having problems with substituting the limits into $[-xe^{-\lambda x}]$. It probably doesn't make sense using l'hopital's rule here, but I tried anyway, and ended up with $\dfrac{1}{\lambda}$ instead of $0$.
Could any kind soul please show me how to substitute the limits? Thank you!

REPLY [1 votes]: Applying de l'Hopital you get
$ \frac{-1}{\lambda \cdot e^{\lambda x}} $
which goes to $0$. You need to pay attention to the derivative of the exponential.


TITLE: Symmetries of a Uniform Magnetic Field
QUESTION [6 upvotes]: Simple question.  A system with a uniform electric field everywhere in space has translational invariance in the directions perpendicular to the electric field but no translational invariance parallel to it.  This system also has rotational invariance in the plane perpendicular to the electric field.
What about a uniform magnetic field?  Judging from the Hamiltonian $(\vec{p}-q\vec{A})^2/2m$, it would seem that the symmetries depend on our choice of gauge.  Choosing a different $\vec{A}$ breaks different symmetries.  Is there a most symmetric choice for $\vec{A}$?

REPLY [3 votes]: If your system consists of (a) a uniform electric field along direction $\hat{\mathbf{n}}$, or (b) a uniform magnetic field along direction $\hat{\mathbf{n}}$, then its symmetries are

translation orthogonal to $\hat{\mathbf{n}}$,
translation parallel to $\hat{\mathbf{n}}$, and
rotations about $\hat{\mathbf{n}}$.

Some of these transformations are equivalent to a gauge transformation. However, gauge transformations are still symmetries of the system, as they respect the physics. More specifically, the motion of a charged particle in those fields is preserved by the symmetries listed above, and it is the motion that matters.
This is somewhat clearer if one spells it out explicitly. Consider a particle of charge $q$ under the action of the electric and magnetic fields $\mathbf E=E_0\hat{\mathbf{z}}$ and $\mathbf B=B_0\hat{\mathbf{z}}$. The hamiltonian for the system can always be written as
$$
H=\frac1{2m}\left(\mathbf p-q\mathbf A\right)^2+\varphi,
$$
where the potentials $\mathbf A=\mathbf A(x,y,t)$ and $\varphi=\varphi(z,t)$ must satisfy
$$
\nabla\times\mathbf A=\mathbf B=B_0\hat{\mathbf{z}}
\quad\text{and}\quad
-\frac{\partial\mathbf A}{\partial t}-\nabla \varphi=\mathbf E=E_0\hat{\mathbf{z}}.
$$
Sample potentials that satisfy this are $\varphi_0=E_0z$ and $\mathbf A_0=\tfrac12 B_0(x\hat{\mathbf{y}}-y\hat{\mathbf{x}})$, and all other acceptable potentials can be obtained from these via
$$
\mathbf A=\mathbf A_0+\nabla\chi
\quad\text{and}\quad
\varphi=\varphi_0-\frac{\partial\chi}{\partial t}
$$
for a suitable function $\chi=\chi(x,y,z,t)$, which has no influence at all on the physics.
Suppose now that you transform the system with the transformation above: You translate by a vector $\mathbf a$ and you rotate about $\hat{\mathbf z}$ with a rotation matrix $R$, so you take $\mathbf r \mapsto \mathbf r'=R(\mathbf r+\mathbf a)$ and $\mathbf p\mapsto \mathbf p'=R\mathbf p$. In terms of the new variables, the old hamiltonian is
\begin{align}
H
&=
\frac1{2m}\left(\mathbf p-q\mathbf A(\mathbf r,t)\right)^2+\varphi(\mathbf r,t)
\\&=
\frac1{2m}\left(R^{-1}\mathbf p'-q\mathbf A(R^{-1}\mathbf r'-\mathbf a,t)\right)^2+\varphi(R^{-1}\mathbf r'-\mathbf a,t)
\\&=
\frac1{2m}\left(\mathbf p'-qR\mathbf A(R^{-1}\mathbf r'-\mathbf a,t)\right)^2+\varphi(R^{-1}\mathbf r'-\mathbf a,t),
\end{align}
because $R$ is orthogonal and preserves norms, so $(R\mathbf u)^2=\mathbf u^2$. This can be written in the same way as before
$$
H\mapsto H'=\frac1{2m}\left(\mathbf p'-q\mathbf A'(\mathbf r',t)\right)^2+\varphi'(\mathbf r',t),
$$
for the transformed potentials
$$
\mathbf A'(\mathbf r',t)=R\mathbf A(R^{-1}\mathbf r'-\mathbf a,t)
\quad\text{and}\quad
\varphi'(\mathbf r',t)=\varphi(R^{-1}\mathbf r'-\mathbf a,t).
$$
We now use the fact that the forms of the old potential are constrained to be gauge transforms of a standard set, so
\begin{align}
\mathbf A'(\mathbf r',t)&=R\mathbf A_0(R^{-1}\mathbf r'-\mathbf a,t)+R\nabla\chi(R^{-1}\mathbf r'-\mathbf a,t)
\quad\text{and}\quad\\
\varphi'(\mathbf r',t)&=\varphi_0(R^{-1}\mathbf r'-\mathbf a,t)-\frac{\partial\chi}{\partial t}(R^{-1}\mathbf r'-\mathbf a,t)
,\end{align}
and the fact that we know how the standard set transforms: writing the rotation matrix explicitly as
$$
R=\begin{pmatrix}\cos\theta&\sin\theta & 0\\ -\sin(\theta)&\cos \theta & 0\\0&0&1\end{pmatrix}
$$
we can transform the potentials to
\begin{align}
R\mathbf A_0(R^{-1}\mathbf r'-\mathbf a,t)
&=
\frac{B_0}{2}
\begin{pmatrix}\cos\theta&\sin\theta & 0\\ -\sin(\theta)&\cos \theta & 0\\0&0&1\end{pmatrix}
\begin{pmatrix}
-\sin\theta x'-\cos\theta y'+a_y
\\
\cos\theta x'-\sin\theta y'-a_x
 \\ 0
\end{pmatrix}
\\&=
\frac{B_0}{2}
\begin{pmatrix}
-y'+\cos\theta a_y-\sin\theta a_x
\\
x'-\sin\theta a_y-\cos\theta a_x
\\0
\end{pmatrix}
\\&=
\mathbf A_0(\mathbf r',t)+\mathbf b
\end{align}
and
\begin{align}
\varphi_0(R^{-1}\mathbf r'-\mathbf a,t)=E_0(z'-a_z)=\varphi_0(z',t)-\phi,
\end{align}
where $\mathbf b$ and $\phi$ are constant.
This transformation is now explicitly in the form of a gauge transformation, with $\chi=\mathbf b·\mathbf r-\phi t$. As I explained before, gauge transformations do not change the physics, so this completes the proof.


TITLE: Sequence in an Unbounded Subset of a Metric Space
QUESTION [1 upvotes]: Suppose we have a metric space $(X, d)$ and an unbounded subset $S \subset X$. Let $s_{0} \in X$. How do you show that there is a sequence $s_{n}$ in $S$ so that $d(s_{n}, s_{0}) > n, \forall n \in \mathbb{N}$?

REPLY [0 votes]: A subset $S$ of a metric space $M$ is bounded if there exists a radius $r>0$ such that $S$ is contained in the $r-\text{neighborhood}$ $M_{r}p$ for some $p \in M$. If $S$ is unbounded, then for all neighborhoods $M_n (s_0)$ there is a point $s_n \in S$ such that $s_n \not\in M_n (s_0)$. Then it follows from the definition of $M_n (s_0)$ that $d(s_0, s_n) > n$.


TITLE: Can modular algebra be conducted exactly as algebra typically is?
QUESTION [1 upvotes]: An example for those that might not understand my question:
$[4][x]+[8]=[1]$ in $\mathbb{Z}_9$
My initial reaction is to make this:
$[4][x]=[-7]$
$[x]=[-7]/[4]$
Then I would determine what $[-7]$ and $[-4]$ is in $\mathbb{Z}_9$ and divide those numbers out.

REPLY [3 votes]: In $\Bbb Z_9$, division by $[4]$ is well-defined (because $\gcd(4, 9) = 1$), and it happens to be the same as multiplicaiton by $[7]$.
You can always carry out addition, subtraction and multiplication as "usual" in modular arithmetic (and by extension natural exponents), but division by a class $[r]$ modulo $n$ (and thus also negative integer exponents of $[r]$) is only defined in those $\gcd(r, n) = 1$ cases.


TITLE: prove that the series is not uniformly convergent
QUESTION [1 upvotes]: Show that the following series is not uniformly convergent: $$\sum_{n=1}^{\infty}{\dfrac{n}{2+n^2}\left(\sin(x)\right)^n} \quad
\text{in} \quad [ 0,\frac{\pi}{2})$$
Attempt: One idea I thought of, is to show that the function $$f(x) = \sum_{n=1}^{\infty}{f_n(x)}$$ is not continuous. This is apparent using $x=0$ and $x=\pi/2$ (amongst the few values for which it fails to be continuous).
My question is if this is sufficient? Or would I have to find the sum function for all values of $x$?
Also, we know that $$\left|\dfrac{n}{2+n^2}\left(\sin(x)\right)^n\right| < M_n =\dfrac{n}{2+n^2}$$ and since $\sum{M_n}$ diverges the given series is not uniformly convergent. Is this reasoning valid?

REPLY [1 votes]: Your converse $M$-test argument is not valid $\dots$ if it were it would show that the zero series is not uniformly convergent.
The sum of a uniformly convergent series must be bounded but it's pretty obvious the sum of your series is not bounded on $[0, \pi/2)$ since $\sum\frac{n}{2+n^2} = \infty$, the $\sin$ can be made arbitrarily close to $1$ and everything in sight is non-negative.


TITLE: Can $X \ne \{0\} \implies X^*\ne\{0\}$ be proved without Hahn-Banach theorem?
QUESTION [1 upvotes]: We know that if $X \ne \{0\}$ is a NLS then $X^*\ne\{0\}$ ; is there any way to prove it without using Hahn-Banach theorem ? Thanks in advance

REPLY [3 votes]: Probably this question (and answer) already exist here.  My favorite example is the quotient Banach space
$$
X = l^\infty/c_0
$$
Of course $X \ne 0$.  But it is consistent with ZF that $X^* = 0$.  So you need some principle beyond ZF for your assertion.  Of course, Hahn-Banach is taylor made to do this.


TITLE: Euclidean Algorithm (gcd)
QUESTION [2 upvotes]: Show that if $a$ and $b$ are positive integers, and $d=\gcd(a,b)$ then there exists positive integers $s, t$ such that
$$d = sa − tb.$$
I'm really unsure of how to approach this. I follow the proof of how $d=sa+tb$ but I'm not sure how to change it to suit this. Any help would be much appreciated.

REPLY [1 votes]: You know already that $d=sa+tb$ with $s,t\in \Bbb Z$.
What could possibly go wrong?
If $t<0$ then certainly $s>0$ as otherwise $d=sa+tb\le tb<0$ and we are done by having $d=sa-(-t)b$.
If $t=0$ then $d$ is a multiple of $a$, which implies $d\mid b$, i.e.,  $b=rb$ with $r\in\Bbb N$. This gives us $d=(s+r)a-1\cdot b$.
If $t>0$, then $d=sa+tb = (s+2tb)a-(2a-1)tb$, where as in the first case necessarily $s+2tb>0$.


TITLE: $X$ is locally compact iff $Y$ is locally compact, if there is a perfect map $f: X\to Y$.
QUESTION [1 upvotes]: This question was part of my quiz and I was unable to solve it there and now tried again at home but unable to do it.

Let $(X,T)$ and $(Y,U)$ be topological spaces and let $f: X\to Y$ be perfect map. Prove that $X$ is locally compact iff $Y$ is locally compact.

If $(X,T)$ and $(Y,U)$ are topological spaces  then a function $f: X\to Y$ is a perfect map if it is a closed continuous surjection with the property that for each $y\in  Y$, $f^{-1}(y) $ is compact.
Let $X$ be locally compact then for every $p \in X$ there exists an open set $U$ and a compact subspace $K$ of $X$ such that $p \in U$ and $U\subseteq K$.
Let $y \in Y$ be a point. there exists an set $Y'$ such that $ Y' =f^{-1}(y)$ is compact.
But I am at loss of ideas on how to prove $Y$ to be locally compact using more properties of $f$ being perfect.

REPLY [1 votes]: Hint
If : Let $y\in Y$ and $x\in X$ s.t. $y=f(x)$. Let $O_x$ a neighborhood of $x$ s.t. $\overline{O_x}$ is compact. One can prove that $f(O_x)$ is a neighborhood of $y$ s.t. $\overline{f(O_x)}$ is compact.
Only if Let $x\in X$. Let $O_{f(x)}$ a neighborhood of $f(x)$ s.t. $\overline{f(O_{f(x)})}$ is compact. Use the fact that $f^{-1}(y)$ is compact for all $y\in O_{f(x)}$ to conclude that $\overline{O_{f(x)}}$ is compact.