\documentclass[11pt]{amsart}
\usepackage{latexsym,amssymb,amsmath,amsthm,graphicx,listings}
\newtheorem{thm}{Theorem} \setlength{\parindent}{0cm}   \def\V{\mathcal{V}}
\newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \def\G{\mathcal{G}} 

\title{Barycentric characteristic numbers}        \author{Oliver Knill}
\date{October 2, 2015, ${\rm http://arxiv.org/find/math/1/au:+Knill\_O/0/1/0/all/0/1}$}
\address{Department of Mathematics \\ Harvard University \\ Cambridge, MA, 02138, USA }
\subjclass{05C10, 57M15, 68R10, 53A55}
\keywords{Graph theory, discrete geometry and topology, valuations}

\begin{document}
\maketitle

If $\G$ is the category of {\bf finite simple graphs} $G=(V,E)$, 
the linear space $\V$ of {\bf valuations} on $\G$ has a basis
given by the {\bf f-numbers} $v_k(G)$ counting complete subgraphs $K_{k+1}$ in $G$. 
The {\bf barycentric refinement} $G_1$ of $G \in \G$ is the graph with $K_l$ subgraphs as vertex set
where new vertices $a \neq b$ are connected if $a \subset b$ or $b \subset a$. Under refinement, 
the clique data transform as $\vec{v} \to A \vec{v}$ with the upper triangular matrix $A_{ij} = i! S(j,i)$ 
with {\bf Stirling numbers} $S(j,i)$. 
The eigenvectors $\chi_k$ of $A^T$ with eigenvalues $k!$ form an other basis in $\V$. The $\chi_k$ 
are normalized so that the first nonzero entry is $>0$ and all entries are in $\Z$ 
with no common prime factor.
$\chi_1$ is the {\bf Euler characteristic} $\sum_{k=0}^{\infty} (-1)^k v_k$, the homotopy and 
so cohomology invariant on $\G$. 
Half of the $\chi_k$ will be zero {\bf Dehn-Sommerville-Klee invariants} 
like half the {\bf Betti numbers} are redundant under {\bf Poincar\'e duality}.
On the set $\G_d \subset \G$ with clique number $d$, the valuations $\V$
have dimension $d+1$ by {\bf discrete Hadwiger}. A basis is the eigensystem 
$\vec{\chi}$ of the upper left $(d+1) \times (d+1)$ sub-matrix $A_d$ of $A$. 
The functional $\chi_{d+1}(G)$ is {\bf volume}, counting the {\bf facets} of $G$.
For $x \in V$, define $V_{-1}(x)=1$ and $V_k(x)$ as the number of complete subgraphs 
$K_{k+1}$ of the unit sphere $S(x)$, the graph generated by the neighbors of $x$. 
The {\bf fundamental theorem} of graph theory is the formula
$\sum_{x \in V} V_{k-1}(x) = (k+1) v_k(G)$. For $k=1$, it is the {\bf Euler's handshake}.
For a valuation $X(G) = \sum_{l=0}^\infty a(l)v_l(G)$, define 
{\bf curvature} $K_X(x)=\sum_{l=0}^\infty a(l)V_{l-1}(x)/(l+1)$. 
Generalizing the fundamental theorem:

\begin{thm}[{\bf Gauss-Bonnet-Chern-Levitt}]
$\sum_{x \in V} K_X(x) = X(G)$.
\end{thm}

{\bf Example.} For an icosahedron with $\vec{v}=(12,30,20)$ and $\vec{v}(S(x))=(5,5)$, we have 
$a_1=(1,-1,1)$, $K_1(x)=1-5/2+5/3=1/6$, $\chi_1=2$, 
$a_2=(0,2,-3)$,  $K_2(x)=10/2-15/3=0$, $\chi_2=0$, 
$a_3=(0,0,1)$,  $K_3(x)=5/3$, $\chi_3=20$.  \\

Let $\Omega(G)$ be the set of {\bf colorings} of $G$, locally injective function $f$ on $V(G)$. 
The {\bf unit ball} $B(x)$ at $x$ is the graph generated by the union of $\{x\}$ and
the {\bf unit sphere} $S(x)=\{ y \in V \; | \; (x,y) \in E \;\}$ which
is the {\bf boundary} $\delta B(x)$. For $f \in \Omega$ and $X \in \V$
define the {\bf index} $i_{X,f}(x) = X(B^-(x))-X(S^-(x))$,
where $B^-(x) = S^-(x) \cup \{x\} = \{ y \in B(x) \; | \; f(y) \leq f(x) \}$
and $S^-(x) = \{f(y)< f(x)\}$. It is local and a {\bf divisor}.
Inductive attaching vertices gives:

\begin{thm}[{\bf Poincar\'e-Hopf}]
$\sum_{x \in V} i_{X,f}(x) = X(G)$.
\end{thm}

Let $P$ be a {\bf Borel probability measure} on $\Omega(G) = \R^{v_0(G)}$ and 
$E[\cdot]$ its {\bf expectation}. Let $c(G)$ be the {\bf chromatic number} of $G$. 
Assume either that $P$ is the counting measure on the finite set of colorings of $G$ with 
$c \geq c(G)$ real colors or that $P$ is a product measure on $\Omega$ for which
functions $f \to f(y)$ with $y \in V$ are independent identically distributed
random variables with continuous probability density function. For all $G \in \G$ and 
$X \in \V$:

\begin{thm}[{\bf Banchoff index expectation}]
$E[i_{X,f}(x)] = K_X(x)$. 
\end{thm}

The {\bf empty graph} $\emptyset$ is a $(-1)$-graph and $(-1)$-sphere. Inductively,
a {\bf $d$-graph} is a $G \in \G$ for which the unit spheres are $(d-1)$-spheres.
An {\bf Evako $d$-sphere} is a $d$-graph which when punctured becomes contractible. 
Inductively, $G$ is {\bf contractible} if there exists $x \in V(G)$ such that both $S(x)$ and the graph 
without $x$ are contractible. The graph $K_1$ is contractible.
Given $f \in \Omega$ and $c \notin f(V)$, define the graph $\{ f=c \}$ in the refinement of
$G$ consisting of vertices, where $f-c$ changes sign. In that case, at every vertex $x$, there is a 
$(d-2)$-graph $R_f(x)$ defined as the {\bf level surface} $\{f(y)=f(x)\}$ in $S(x)$.
The next {\bf Sard} result belongs to {\bf discrete multivariable calculus}:

\begin{thm}[{\bf Implicit function theorem}]
For a $d$-graph and $f \in \Omega$ and $c \notin f(V)$, the hyper surface $\{ f=c \}$ is a $(d-1)$-graph.
\end{thm}

The {\bf symmetric index} of $f$ at $x$ is defined as $2 j_{X,f}(x) = i_{X,f}(x)+i_{X,-f}(x)$. 

\begin{thm}[Index formula] For $G \in \G$ and $X \in \V$, then \\
\parbox{1cm}{\hspace{1cm}} $2 j_{X,f}(x)  = X(B(x)) + X(\{x\}) - X(S(x)) - X(R_f(x))$. 
\end{thm}

It allows fast recursive computation of $X$ for most $G$ in $\G_d$ quantified using
{\bf Erd\"os-Renyi} measures. For Euler characteristic, $j_f(x) = (1-\chi(S(x))/2) - X(R_f(x))/2$. 
For $d$-graphs it is $-\chi(R_f(x))/2$ if $d$ is odd and 
$1-\chi(R_f(x))/2$ if $d$ is even.
If $k+d$ is even, we have $\chi_k(B(x))=\chi_k(S(x))$, as curvature
is supported on $\delta G$. Furthermore, we have $\chi_k(\{x\})=0$ if $k>1$.

\begin{thm}[{\bf Dehn-Sommerville-Klee}]
For a $d$-graph and even $d+k$, the functions $K_k$ and $j_{k,f}$ are supported on $\delta G$. 
If $\delta G=\emptyset$, then $\chi_k(G) =0$.
\end{thm}

The proof uses dimension reduction until the
{\bf boundary invariant} $\chi_{d}$ is achieved which is $0$ in ${\rm int}(G)$
giving $j_{k,f}(x) = K_k(x)=0$ there. For $k+d$ odd, $j_{k,f}$
consists of lower dimensional volume and $\chi_k(B(x))-\chi_k(S(x))$ values. 
Nonzero {\bf integer charges} $i_{X,k}(x)$ are
interesting also for even $d+k$. \\

{\bf Illustration}: 
$\chi_2(G)=0$ on 4-graphs shows that a 4-graph {\bf triangulation}
$G$ of a compact 4-manifold with $v$ vertices, $e$ edges, 
$f$ triangles, $t$ tetrahedra, and $p$ pentatopes satisfies $22e+40t=33f+45p$. Examples:
for the 4-crosspolytop $G$, a 4-sphere with $\vec{v}=(10,40,80,80,32)$, we get 
$\vec{\chi}(G)=(2,0,240,0,32)$. For a discrete $G=S^2 \times T^2$, a product graph
constructed using the {\bf Stanley-Reisner ring}, with
$\vec{v}=(1664,23424,77056,92160,36864)$, we get $\vec{\chi}(G)=(0,0,-10496,0,36864)$. 
For a discrete $G=P^2 \times S^2$ with $\vec{v}=(1898, 26424$, $86736, 103680, 41472)$
we get $\vec{\chi}(G)=(2,0,-10896,0,41472)$. 

\end{document}
