\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=true]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Saturday, May 06, 2023 19:44:16}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newcommand{\silentsection}{\section}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\NOEXPAND{\silentsection}{\section}
\fi
\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arinjrev}{\ar@{^{(}->}}
\newcommand{\arsurj}{\ar@{->>}}
\newcommand{\arelem}{\ar@{|->}}
\newcommand{\arback}{\ar@{<-}}
\newcommand{\id}{\operatorname{id}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\DeclareMathOperator{\osc}{OSC}
\DeclareMathOperator{\rtb}{R2B}
\DeclareMathOperator{\uosc}{UOSC}
\newcommand{\darij}[1]{\textcolor{olive}{Darij:[#1]}}
\newcommand{\nadia}[1]{\textcolor{orange}{Nadia:[#1]}}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\usetikzlibrary{arrows.meta}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{noncompile}{}{}
\excludecomment{noncompile}
\ihead{Chromatic symmetric functions (talk)}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{Chromatic symmetric functions and broken circuits [talk slides]}
\date{Algebraic and Combinatorial Perspectives in the Mathematical Sciences, 2023-04-28}
\author{Darij Grinberg}
\maketitle

\begin{abstract}
In his 1995 paper introducing the chromatic symmetric function of a graph,
Richard Stanley proved an expression for it as a sign-alternating sum of
p-functions over subsets that contain no broken circuit of the graph. This
(partly expository) talk will generalize this formula to some degree, in that
the exclusion of all broken circuits will be replaced by the exclusion of some
(arbitrarily chosen) set of broken circuits. This generality comes for cheap,
but has a curious application to bipartite graphs and to an isotropic analogue
of hyperplane arrangements. An analogous generalization of the broken-circuit
formula for the characteristic polynomial of a matroid will also be given.

\end{abstract}

\newpage

\section*{***}

Preprint:

\begin{itemize}
\item Darij Grinberg, \textit{Generalized Whitney formulas for broken circuits
in ambigraphs and matroids}, preprint,\newline\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}

(Previously called \textquotedblleft\textit{A note on non-broken-circuit sets
and the chromatic polynomial}\textquotedblright.)
\end{itemize}

Slides of this talk:

\begin{itemize}
\item \url{https://www.cip.ifi.lmu.de/~grinberg/algebra/acpms2023.pdf}
\end{itemize}

\newpage

\begin{itemize}
\item This talk is about a project started back in 2016, still in a somewhat
larval stage.

\item I hope it gives some food for thought even if there is a lack of deep
and striking theorems.
\end{itemize}

\bigskip

\section{Motivation: Hyperplane arrangements}

\begin{itemize}
\item Recall: A \emph{linear hyperplane arrangement} in a vector space $V$ is
a finite set $\mathcal{A}$ of linear hyperplanes in $V$.

(\textquotedblleft Linear\textquotedblright\ means \textquotedblleft passing
through $0$\textquotedblright.)

\item A classical example of such an arrangement:

\item \textbf{Definition.} Let $G$ be a finite graph with vertex set $\left\{
1,2,\ldots,n\right\}  $. Then, its \emph{graphical arrangement} $\mathcal{A}%
_{G}$ (over a field $K$) is the hyperplane arrangement in $K^{n}$ defined by%
\[
\left\{  \left\{  x=\left(  x_{1},x_{2},\ldots,x_{n}\right)  \in K^{n}%
\ \mid\ x_{i}=x_{j}\right\}  \right\}  _{\left\{  i,j\right\}  \text{ is an
edge of }G}.
\]


\item \textbf{Definition.} Let $\mathcal{A}$ be a linear hyperplane
arrangement in a vector space $V$. Then, its \emph{characteristic polynomial}
$\chi_{\mathcal{A}}$ is defined by%
\[
\chi_{\mathcal{A}}=\sum_{\mathcal{B}\subseteq\mathcal{A}}\left(  -1\right)
^{\left\vert \mathcal{B}\right\vert }x^{\dim\left(  \bigcap\mathcal{B}\right)
}\in\mathbb{Z}\left[  x\right]  .
\]
Here, $\bigcap\mathcal{B}$ denotes the intersection of the hyperplanes in
$\mathcal{B}$.

\item For a graphical arrangement, this turns out to recover the
\emph{chromatic polynomial}:

\item \textbf{Definition.} Let $G$ be a finite graph with vertex set $V$. A
\emph{proper coloring} of $G$ means a map $f:V\rightarrow\left\{
1,2,3,\ldots\right\}  $ such that%
\[
f\left(  v\right)  \neq f\left(  w\right)  \text{ for each edge }\left\{
v,w\right\}  \text{ of }G.
\]
The values of such a map are called its \emph{colors}.

The \emph{chromatic polynomial} $\chi_{G}$ of $G$ is the polynomial in
$\mathbb{Z}\left[  x\right]  $ such that%
\begin{align*}
\chi_{G}\left(  q\right)   &  =\left(  \text{\# of proper colorings of
}G\text{ with colors in }\left\{  1,2,\ldots,q\right\}  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \text{for all }q\in\mathbb{N}.
\end{align*}


\item \textbf{Theorem (folklore; see Theorem 2.7 in Stanley's Introduction).}
Let $G$ be a finite graph with vertex set $\left\{  1,2,\ldots,n\right\}  $.
Then, the characteristic polynomial $\chi_{\mathcal{A}_{G}}$ of its graphical
arrangement $\mathcal{A}_{G}$ equals the chromatic polynomial of $G$:%
\[
\chi_{\mathcal{A}_{G}}=\chi_{G}.
\]

\end{itemize}

\newpage

\section{Coisotropic hyperplane arrangements}

\begin{itemize}
\item Now, consider a vector space $V$ (over a field $K$) equipped with a
bilinear form $f:V\times V\rightarrow K$.

\item Assume that this form $f$ is symmetric or alternating.

\item Then, for each vector subspace $W$ of $V$, there is an \emph{orthogonal
space}%
\begin{align*}
W^{\perp}:=  &  \ \left\{  v\in V\ \mid\ f\left(  v,w\right)  =0\text{ for all
}w\in W\right\} \\
=  &  \ \left\{  v\in V\ \mid\ f\left(  w,v\right)  =0\text{ for all }w\in
W\right\}
\end{align*}
(also a subspace of $V$).

\item We say that a vector subspace $W$ of $V$ is \emph{coisotropic} if
$W^{\perp}\subseteq W$.

\item A coisotropic subspace $W$ always has dimension $\geq\dfrac{\dim W}{2}$.

\item A linear hyperplane arrangement $\mathcal{A}$ in $V$ will be called
\emph{coisotropic} if each hyperplane $H\in\mathcal{A}$ is coisotropic.

\item This does not mean that every intersection $\bigcap\mathcal{B}$ for
$\mathcal{B}\subseteq\mathcal{A}$ is coisotropic!

\item \textbf{Definition.} Let $\mathcal{A}$ be a coisotropic linear
hyperplane arrangement in $V$. Then, its \emph{coisotropic characteristic
polynomial} $\chi_{\mathcal{A},\perp}$ is defined by%
\[
\chi_{\mathcal{A},\perp}=\sum_{\substack{\mathcal{B}\subseteq\mathcal{A}%
;\\\bigcap\mathcal{B}\text{ is a coisotropic}\\\text{subspace of }V}}\left(
-1\right)  ^{\left\vert \mathcal{B}\right\vert }x^{\dim\left(  \bigcap
\mathcal{B}\right)  }\in\mathbb{Z}\left[  x\right]  .
\]


\item We have an analogue of the graphical arrangement:

\item \textbf{Definition.} Let $D$ be a \textbf{digraph} (= directed graph)
with vertex set $\left\{  1,2,\ldots,n\right\}  $ and with no loops (i.e., no
arcs of the form $\left( v,v\right) $). Let $V$ be the $K$-vector space
$K^{n}\oplus K^{n}$. A typical vector in $V$ has the form $\left(  x;y\right)
=\left(  x_{1},x_{2},\ldots,x_{n};y_{1},y_{2},\ldots,y_{n}\right)  $.

Define a bilinear form%
\begin{align*}
f:V\times V  &  \rightarrow K,\\
\left(  \left(  x;y\right)  ,\ \left(  x^{\prime};y^{\prime}\right)  \right)
&  \mapsto\sum\limits_{i=1}^{n}x_{i}y_{i}^{\prime}+\sum\limits_{i=1}^{n}%
y_{i}x_{i}^{\prime}.
\end{align*}


Let $\mathcal{A}_{D}^{\perp}$ be the coisotropic hyperplane arrangement%
\[
\left\{  \left\{  \left(  x;y\right)  \in V\ \mid\ x_{i}=y_{j}\right\}
_{\left(  i,j\right)  \text{ is an arc of }D}\right\}  .
\]


Assume that the field $K$ has characteristic $\neq2$.

\item \textbf{Proposition.} In this situation,%
\[
\chi_{\mathcal{A}_{D}^{\perp},\perp}=\sum_{\substack{F\text{ is a set of arcs
of }D;\\F\text{ is }2\text{-step-free}}}\left(  -1\right)  ^{\left\vert
F\right\vert }x^{n+\kappa\left(  F\right)  }.
\]
Here,

\begin{itemize}
\item a set $F$ of arcs of $D$ is said to be $2$\emph{-step-free} if two arcs
of the form $\left(  i,j\right)  $ and $\left(  j,k\right)  $ cannot
simultaneously belong to $F$.

\item the number $\kappa\left(  F\right)  $ is the number of connected
components of the graph whose vertices are $1,2,\ldots,n$ and whose edges are
the undirected versions of the arcs in $F$.
\end{itemize}

\item \textbf{Theorem (suggested by Postnikov 2016).} Assume that this digraph
$D$ is \emph{transitive} -- i.e., if $\left(  i,j\right)  $ and $\left(
j,k\right)  $ are arcs of $D$, then so is $\left(  i,k\right)  $. Then,%
\[
\chi_{\mathcal{A}_{D}^{\perp},\perp}=x^{n}\chi_{\underline{D}}.
\]
Here, $\underline{D}$ denotes the underlying undirected graph of $D$ (that is,
replace all arcs by edges in $D$), and $\chi_{\underline{D}}$ is its chromatic polynomial.

\item Proving this theorem has motivated the following combinatorial considerations.
\end{itemize}

\newpage

\section{Chromatic symmetric functions}

\begin{itemize}
\item \href{https://math.mit.edu/~rstan/pubs/pubfiles/100.pdf}{In 1995,
Richard P. Stanley} generalized chromatic polynomials to \textquotedblleft
chromatic symmetric functions\textquotedblright: a finer invariant of a graph.

\item \textbf{Definition.} If $V$ is a set, then $\mathcal{P}_{2}\left(
V\right)  $ is the set of all $2$-element subsets of $V$.

\item \textbf{Definition.} A \emph{graph} (or \emph{simple graph}) means a
pair $\left(  V,E\right)  $ of a finite set $V$ and a subset $E$ of
$\mathcal{P}_{2}\left(  V\right)  $ (that is, each edge is a $2$-element set
of vertices).

Of course, the elements of $V$ are called \emph{vertices}, and the elements of
$E$ are called \emph{edges} of the graph.

\item \textbf{Definition.} If $G=\left(  V,E\right)  $ is a graph, then

\begin{itemize}
\item a \emph{coloring} of $G$ means a map $f:V\rightarrow\mathbb{N}_{+}$;

\item a \emph{proper coloring} of $G$ means a coloring $f$ of $G$ such that
\[
f\left(  v\right)  \neq f\left(  w\right)  \text{ for each edge }\left\{
v,w\right\}  \in E.
\]

\end{itemize}

Here and in the following, $\mathbb{N}_{+}=\left\{  1,2,3,\ldots\right\}
=\mathbb{N}\setminus\left\{  0\right\}  $.

\item \textbf{Definition.} Let $G=\left(  V,E\right)  $ be a graph. The
\emph{chromatic symmetric function} of $G$ is defined to be the formal power
series%
\[
X_{G}:=\sum_{f\text{ is a proper coloring of }G}\mathbf{x}_{f}%
,\ \ \ \ \ \ \ \ \ \ \text{where }\mathbf{x}_{f}=\prod_{v\in V}x_{f\left(
v\right)  }.
\]
This is a symmetric function in $x_{1},x_{2},x_{3},\ldots$ over $\mathbb{Z}$.

\item \textbf{Remark.} The chromatic polynomial $\chi_{G}$ of $G$ is then
determined by
\[
\chi_{G}\left(  q\right)  =X_{G}\left(  \underbrace{1,1,\ldots,1}_{q\text{
times}},0,0,0,\ldots\right)  \ \ \ \ \ \ \ \ \ \ \text{for all }q\in
\mathbb{N}.
\]


\item \textbf{Theorem (all-subsets Whitney formula;
\href{https://math.mit.edu/~rstan/pubs/pubfiles/100.pdf}{\textbf{Stanley
1995}}).} Let $G=\left(  V,E\right)  $ be a graph. Then,%
\[
X_{G}=\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert F\right\vert
}p_{\lambda\left(  V,F\right)  }.
\]
Here, $\lambda\left(  V,F\right)  $ is the partition whose entries are the
sizes of the connected components of the graph $\left(  V,F\right)  $.

And $p_{\mu}$ is the power-sum symmetric function for the partition $\mu$.

\item This formula has lots of cancellation, but it yields that $X_{G}$ is $p$-integral.

\item \textbf{Corollary (Whitney's original all-subsets formula;
\href{https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-38/issue-8/A-logical-expansion-in-mathematics/bams/1183496087.full}{\textbf{Whitney
1932}}).} Let $G=\left(  V,E\right)  $ be a graph. Then,%
\[
\chi_{G}=\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert F\right\vert
}x^{\operatorname*{conn}\left(  V,F\right)  },
\]
where $\operatorname*{conn}$ means \textquotedblleft number of connected
components\textquotedblright.
\end{itemize}

\newpage

\section{Broken circuits}

\begin{itemize}
\item A way to manage this cancellation was found by
\href{https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-38/issue-8/A-logical-expansion-in-mathematics/bams/1183496087.full}{Whitney
(1932)} and extended to symmetric functions by
\href{https://math.mit.edu/~rstan/pubs/pubfiles/100.pdf}{Stanley (1995)}. We
now recall the definitions.

\item \textbf{Definition.} Let $G=\left(  V,E\right)  $ be a graph. If
$\mathbf{c}$ is a cycle of $G$, then the set of all edges of $\mathbf{c}$ is
called a \emph{circuit} of $G$.

\item \textbf{Definition.} Let $G=\left(  V,E\right)  $ be a graph. A
\emph{labeling function} means a map $\ell:E\rightarrow X$ to some totally
ordered set $X$. Its value $\ell\left(  e\right)  $ is called the \emph{label}
of an edge $e$.

\item \textbf{Definition.} Let $G=\left(  V,E\right)  $ be a graph. Fix a
labeling function $\ell:E\rightarrow X$. If $C$ is a circuit of $G$, and if
$C$ contains a unique edge $e$ of highest label (among all edges in $C$), then
the set $C\setminus\left\{  e\right\}  $ is called a \emph{broken circuit} of
$G$.

\item \textbf{Note.} If this $e$ is not unique, then $C$ generates no broken circuit.

\item \textbf{Theorem (broken-circuits Whitney formula;
\href{https://math.mit.edu/~rstan/pubs/pubfiles/100.pdf}{\textbf{Stanley
1995}}).} Let $G=\left(  V,E\right)  $ be a graph. Let $\ell:E\rightarrow X$
be a labeling function. Then,%
\[
X_{G}=\sum_{\substack{F\subseteq E;\\F\text{ contains no broken}%
\\\text{circuit of }G\text{ as a subset}}}\left(  -1\right)  ^{\left\vert
F\right\vert }p_{\lambda\left(  V,F\right)  }.
\]


\item Note that each $\left(  V,F\right)  $ in this sum is a forest if $\ell$
is injective.

\item \textbf{Corollary (Whitney's original broken-circuits formula).} Let
$G=\left(  V,E\right)  $ be a graph. Let $\ell:E\rightarrow X$ be an injective
labeling function. Then,%
\[
\chi_{G}=\sum_{\substack{F\subseteq E;\\F\text{ contains no broken}%
\\\text{circuit of }G\text{ as a subset}}}\left(  -1\right)  ^{\left\vert
F\right\vert }x^{\left\vert V\right\vert -\left\vert F\right\vert }.
\]

\end{itemize}

\newpage

\section{Relaxing Whitney's formula}

\begin{itemize}
\item For each of $X_{G}$ and $\chi_{G}$, we have seen two formulas: one sum
over all subsets of $E$, and one that excludes all subsets that contain any
broken circuit.

\item Everything inbetween also works!

\item \textbf{Theorem (relaxed Whitney formula; explicitly
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}, but essentially
\href{https://doi.org/10.37236/4356}{\textbf{Dohmen/Trinks 2014}}).} Let
$G=\left(  V,E\right)  $ be a graph. Let $\ell:E\rightarrow X$ be a labeling
function. Let $\mathfrak{K}$ be some set of broken circuits of $G$ (not
necessarily containing all of them). Then,%
\[
X_{G}=\sum_{\substack{F\subseteq E;\\F\text{ is }\mathfrak{K}\text{-free}%
}}\left(  -1\right)  ^{\left\vert F\right\vert }p_{\lambda\left(  V,F\right)
}.
\]
Here (and in the following), \textquotedblleft is $\mathfrak{K}$%
-free\textquotedblright\ means \textquotedblleft contains no $K\in
\mathfrak{K}$ as a subset\textquotedblright.

\item \textit{Proof idea.} For any $F\subseteq E$, we have%
\[
p_{\lambda\left(  V,F\right)  }=\sum_{\substack{f:V\rightarrow\mathbb{N}%
_{+}\text{ is a map;}\\f\text{ is constant on each}\\\text{connected component
of }\left(  V,F\right)  }}\mathbf{x}_{f}.
\]


Thus,%
\[
\sum_{\substack{F\subseteq E;\\F\text{ is }\mathfrak{K}\text{-free}}}\left(
-1\right)  ^{\left\vert F\right\vert }p_{\lambda\left(  V,F\right)  }%
=\sum_{f:V\rightarrow\mathbb{N}_{+}\text{ is a map}}\left(  \sum
_{\substack{F\subseteq E;\\F\text{ is }\mathfrak{K}\text{-free;}\\f\text{ is
constant on each}\\\text{connected component of }\left(  V,F\right)  }}\left(
-1\right)  ^{\left\vert F\right\vert }\right)  \mathbf{x}_{f}.
\]


It remains to argue that the inner sum is $1$ whenever $f$ is a proper
coloring of $G$, and $0$ otherwise.

The former is trivial; the latter follows by a sign-reversing involution (pick
an edge $\left\{  s,t\right\}  \in E$ with $f\left(  s\right)  =f\left(
t\right)  $ that has maximum possible label; toggle it in/out of $F$).

\item Both Whitney formulas for $X_{G}$ follow.

\item \textbf{Corollary (relaxed Whitney formula; explicitly
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}, but essentially
\href{https://doi.org/10.37236/4356}{\textbf{Dohmen/Trinks 2014}}).} Let
$G=\left(  V,E\right)  $ be a graph. Let $\ell:E\rightarrow X$ be a labeling
function. Let $\mathfrak{K}$ be some set of broken circuits of $G$ (not
necessarily containing all of them). Then,%
\[
\chi_{G}=\sum_{\substack{F\subseteq E;\\F\text{ is }\mathfrak{K}\text{-free}%
}}\left(  -1\right)  ^{\left\vert F\right\vert }x^{\operatorname*{conn}\left(
V,F\right)  }.
\]


\item \textit{Proof idea.} Apply the previous theorem to $\left(
1,1,\ldots,1,0,0,0,\ldots\right)  $.

\item Both Whitney formulas for $\chi_{G}$ follow.

\item Even a somewhat more general result holds:

\item \textbf{Theorem (generalized Whitney formula; explicitly
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}, but essentially
\href{https://doi.org/10.37236/4356}{\textbf{Dohmen/Trinks 2014}}).} Let
$G=\left(  V,E\right)  $ be a graph. Let $\ell:E\rightarrow X$ be a labeling
function. Let $\mathfrak{K}$ be some set of broken circuits of $G$ (not
necessarily containing all of them). Let $a_{K}$ be an element of the base
ring for every $K\in\mathfrak{K}$. Then,%
\[
X_{G}=\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert F\right\vert }\left(
\prod_{\substack{K\in\mathfrak{K};\\K\subseteq F}}a_{K}\right)  p_{\lambda
\left(  V,F\right)  }.
\]


\item \textit{Proof.} Essentially the same argument.
\end{itemize}

\newpage

\section{Application to transitive digraphs}

\begin{itemize}
\item The freedom to exclude some (rather than all) broken circuits has some
applications. In particular, we can prove what we need for the hyperplane
arrangement equality.

\item \textbf{Definition.} A \emph{digraph} (= \emph{directed graph}) means a
pair $\left(  V,A\right)  $ of a finite set $V$ (the set of \emph{vertices})
and a subset $A$ of $V\times V$ (the set of \emph{arcs}). Thus, each arc is an
ordered pair of vertices.

\item \textbf{Definition.} A digraph $\left(  V,A\right)  $ is said to be

\begin{itemize}
\item \emph{loopless} if $\left(  v,v\right)  \notin A$ for all $v\in V$;

\item \emph{transitive} if $\left(  u,v\right)  \in A$ and $\left(
v,w\right)  \in A$ imply $\left(  u,w\right)  \in A$;

\item $2$\emph{-step-free} if $\left(  u,v\right)  \in A$ and $\left(
v,w\right)  \in A$ never happen together.
\end{itemize}

\item \textbf{Definition.} If $D$ is a loopless digraph, then $\underline{D}$
shall mean the underlying undirected graph (i.e., replace each arc by an edge).

\item \textbf{Examples.} Here are three loopless digraphs:%
\[%
\begin{tabular}
[c]{|c|c|c|}\hline
$%
%TCIMACRO{\TeXButton{tikz multidigraph with 4 vertices}{\begin{tikzpicture}%
%[scale=2]
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0,1) {$1$};
%\node(2) at (1,0) {$2$};
%\node(3) at (-1,0) {$3$};
%\node(4) at (0,-1) {$4$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
%\path[-{Latex[width=3mm]}] (1) edge (3);
%\path[-{Latex[width=3mm]}] (1) edge (2);
%\path[-{Latex[width=3mm]}] (4) edge (3);
%\path[-{Latex[width=3mm]}] (4) edge (2);
%\path[-{Latex[width=3mm]}] (2) edge (3);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0,1) {$1$};
\node(2) at (1,0) {$2$};
\node(3) at (-1,0) {$3$};
\node(4) at (0,-1) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-{Latex[width=3mm]}] (1) edge (3);
\path[-{Latex[width=3mm]}] (1) edge (2);
\path[-{Latex[width=3mm]}] (4) edge (3);
\path[-{Latex[width=3mm]}] (4) edge (2);
\path[-{Latex[width=3mm]}] (2) edge (3);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz multidigraph with 4 vertices}{\begin{tikzpicture}%
%[scale=2]
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0,1) {$1$};
%\node(2) at (1,0) {$2$};
%\node(3) at (-1,0) {$3$};
%\node(4) at (0,-1) {$4$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
%\path[-{Latex[width=3mm]}] (1) edge (3);
%\path[-{Latex[width=3mm]}] (1) edge (4);
%\path[-{Latex[width=3mm]}] (2) edge (3);
%\path[-{Latex[width=3mm]}] (2) edge (4);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0,1) {$1$};
\node(2) at (1,0) {$2$};
\node(3) at (-1,0) {$3$};
\node(4) at (0,-1) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-{Latex[width=3mm]}] (1) edge (3);
\path[-{Latex[width=3mm]}] (1) edge (4);
\path[-{Latex[width=3mm]}] (2) edge (3);
\path[-{Latex[width=3mm]}] (2) edge (4);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikz multidigraph with 4 vertices}{\begin{tikzpicture}%
%[scale=2]
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (0,1) {$1$};
%\node(2) at (1,0) {$2$};
%\node(3) at (-1,0) {$3$};
%\node(4) at (0,-1) {$4$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
%\path[-{Latex[width=3mm]}] (1) edge (2);
%\path[-{Latex[width=3mm]}] (4) edge (3);
%\path[-{Latex[width=3mm]}] (4) edge (2);
%\path[-{Latex[width=3mm]}] (2) edge (3);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0,1) {$1$};
\node(2) at (1,0) {$2$};
\node(3) at (-1,0) {$3$};
\node(4) at (0,-1) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-{Latex[width=3mm]}] (1) edge (2);
\path[-{Latex[width=3mm]}] (4) edge (3);
\path[-{Latex[width=3mm]}] (4) edge (2);
\path[-{Latex[width=3mm]}] (2) edge (3);
\end{scope}
\end{tikzpicture}%
%EndExpansion
$\\
transitive & $2$-step-free & neither\\\hline
\end{tabular}
\]


\item \textbf{Note.} Transitive loopless digraphs have no cycles.

\item \textbf{Theorem
(\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}, suggested by Alex Postnikov).} Let $D=\left(  V,A\right)  $ be a
transitive loopless digraph. Then,%
\[
\chi_{\underline{D}}=\sum_{\substack{F\subseteq A;\\\text{the digraph }\left(
V,F\right)  \text{ is }2\text{-step-free}}}\left(  -1\right)  ^{\left\vert
F\right\vert }x^{\operatorname*{conn}\underline{\left(  V,F\right)  }},
\]
where $\operatorname*{conn}$ means \textquotedblleft number of connected
components\textquotedblright.

\item \textit{Proof idea.} Let $E$ be the edge set of $\underline{D}$. The map%
\begin{align*}
A  &  \rightarrow E,\\
\left(  i,j\right)   &  \mapsto\left\{  i,j\right\}
\end{align*}
is a bijection (since $D$ has no $2$-cycles).

Hence, each triple $\left(  i,j,k\right)  \in V\times V\times V$ with $\left(
i,j\right)  \in A$ and $\left(  j,k\right)  \in A$ yields a $3$-cycle $\left(
i,j,k,i\right)  $ in $\underline{D}$, and thus a circuit%
\[
\left\{  \left\{  i,j\right\}  ,\ \left\{  i,k\right\}  ,\ \left\{
j,k\right\}  \right\}
\]
of $\underline{D}$. Define a labeling function $\ell:E\rightarrow\mathbb{N}$
in such a way that the edge $\left\{  i,k\right\}  $ of this circuit has a
higher label than the other two (this is possible since $D$ has no cycles).
Thus,%
\[
\left\{  \left\{  i,j\right\}  ,\ \left\{  j,k\right\}  \right\}
\]
is a broken circuit of $\underline{D}$. Let $\mathfrak{K}$ be the set of all
such broken circuits.

Argue that the above bijection $A\rightarrow E$ transforms subsets $F\subseteq
A$ for which the digraph $\left(  V,F\right)  $ is $2$-step-free into subsets
$F^{\prime}\subseteq E$ that are $\mathfrak{K}$-free. Now, apply the relaxed
Whitney formula for $\chi_{G}$ to $G=\underline{D}$.

\item Note that $\mathfrak{K}$ is not the set of all broken circuits of
$\underline{D}$, only some of them. We don't want to remove too much!

\item The above theorem can then be used to obtain the $\chi_{\mathcal{A}%
_{D}^{\perp},\perp}=x^{n}\chi_{\underline{D}}$ theorem.
\end{itemize}

\newpage

\section{Ambigraphs}

\begin{itemize}
\item Simple graphs are not the end-all. Chromatic polynomials have also been
defined for

\begin{itemize}
\item \emph{multigraphs} (graphs with multiple edges);

\item \emph{hypergraphs} (\textquotedblleft graphs\textquotedblright\ where an
edge can have more than $2$ endpoints).
\end{itemize}

They still satisfy Whitney formulas (folklore for multigraphs;
\href{https://doi.org/10.1007/BF01196637}{Dohmen 1995} and
\href{https://doi.org/10.37236/4356}{Dohmen/Trinks 2014} for hypergraphs).

\item For a multigraph, parallel edges don't affect $X_{G}$ and $\chi_{G}$ but
make the alternating sums bigger.

\item We ignore loops, as they trivialize everything ($0=0$) but make proofs messier.

\item For a hypergraph, a proper coloring has to ensure that no edge is
monochromatic: i.e., if $f$ is a coloring, and $\left\{  v_{1},v_{2}%
,\ldots,v_{k}\right\}  $ is an edge, then \textbf{at least two} of the values
$f\left(  v_{1}\right)  ,f\left(  v_{2}\right)  ,\ldots,f\left(  v_{k}\right)
$ must be distinct in order for $f$ to be proper.

\item \textbf{Observation (new?):} Hypergraphs aren't the right level of
generality for this.

\item \textbf{Definition.} An \emph{ambigraph} shall mean a triple $\left(
V,E,\varphi\right)  $, where $V$ and $E$ are two finite sets, and where
$\varphi:E\rightarrow\mathcal{P}\left(  \mathcal{P}_{2}\left(  V\right)
\right)  $ is a map (where $\mathcal{P}\left(  S\right)  $ means the set of
all subsets of $S$). Thus, the map $\varphi$ sends each $e\in E$ to a set of
$2$-element subsets of $V$.

Some related terminology:

\begin{itemize}
\item The elements of $V$ are called \emph{vertices}, and the elements of $E$
are called \emph{edgeries}.

\item The \emph{edges} of an edgery $e\in E$ are the elements of
$\varphi\left(  e\right)  $. These edges are \textquotedblleft
real\textquotedblright\ edges, i.e., sets of the form $\left\{  s,t\right\}  $
for $s\neq t$ in $V$.

\item An edgery $e\in E$ is called \emph{singleton} if $e$ has only $1$ edge.
\end{itemize}

Idea: An edgery is a collection of edges (in the simple-graph sense).

\item \textbf{Example.} This here:%
\[%
%TCIMACRO{\TeXButton{tikz G}{\begin{tikzpicture}[scale=2]
%\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
%\node(1) at (-1,0) {$1$};
%\node(2) at (0,1) {$2$};
%\node(3) at (0,-1) {$3$};
%\node(4) at (1,0) {$4$};
%\end{scope}
%\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
%\path[-] (1) edge node[above] {$b$} (2);
%\path[-] (1) edge node[below] {$a$} (3);
%\path[-] (2) edge node[right] {$cd$} (3);
%\path[-] (2) edge node[above] {$a$} (4);
%\path[-] (3) edge node[below] {$bd$} (4);
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (-1,0) {$1$};
\node(2) at (0,1) {$2$};
\node(3) at (0,-1) {$3$};
\node(4) at (1,0) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (1) edge node[above] {$b$} (2);
\path[-] (1) edge node[below] {$a$} (3);
\path[-] (2) edge node[right] {$cd$} (3);
\path[-] (2) edge node[above] {$a$} (4);
\path[-] (3) edge node[below] {$bd$} (4);
\end{scope}
\end{tikzpicture}%
%EndExpansion
\]
shows the ambigraph $\left(  V,E,\varphi\right)  $ with $V=\left\{
1,2,3,4\right\}  $ and $E=\left\{  a,b,c,d\right\}  $ and%
\begin{align*}
\varphi\left(  a\right)   &  =\left\{  \left\{  1,3\right\}  ,\ \left\{
2,4\right\}  \right\}  ,\ \ \ \ \ \ \ \ \ \ \varphi\left(  b\right)  =\left\{
\left\{  1,2\right\}  ,\ \left\{  3,4\right\}  \right\}  ,\\
\varphi\left(  c\right)   &  =\left\{  \left\{  2,3\right\}  \right\}
,\ \ \ \ \ \ \ \ \ \ \varphi\left(  d\right)  =\left\{  \left\{  2,3\right\}
,\ \left\{  3,4\right\}  \right\}  .
\end{align*}
The only singleton edgery here is $c$, whose only edge is $\left\{
2,3\right\}  $.

\item \textbf{Definition.} If $G=\left(  V,E,\varphi\right)  $ is an
ambigraph, then

\begin{itemize}
\item a \emph{coloring} of $G$ means a map $f:V\rightarrow\mathbb{N}_{+}$;

\item a \emph{proper coloring} of $G$ means a coloring $f$ of $G$ such that
\begin{align*}
&  \text{each edgery }e\in E\text{ has at least one}\\
&  \text{edge }\left\{  v,w\right\}  \text{ satisfying }f\left(  v\right)
\neq f\left(  w\right)  .
\end{align*}

\end{itemize}

\item \textbf{Example.} If $G$ is as above, then a proper coloring of $G$ is a
map $f:V\rightarrow\mathbb{N}_{+}$ such that%
\begin{align*}
&  \left(  f\left(  1\right)  \neq f\left(  3\right)  \text{ or }f\left(
2\right)  \neq f\left(  4\right)  \right)  \ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \left(  f\left(  1\right)  \neq f\left(  2\right)  \text{
or }f\left(  3\right)  \neq f\left(  4\right)  \right) \\
&  \text{and}\ \ \ \ \ \ \ \ \ \ f\left(  2\right)  \neq f\left(  3\right)
\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \left(  f\left(  2\right)
\neq f\left(  3\right)  \text{ or }f\left(  3\right)  \neq f\left(  4\right)
\right)  .
\end{align*}
(Note: The last condition is redundant, since $\varphi\left(  c\right)
\subseteq\varphi\left(  d\right)  $.)

\item \textbf{Remark.} If $G$ has an edgery with no edges, then $G$ has no
proper colorings. (This is like having a loop.)

\item Ambigraphs generalize multigraphs (all edgeries are singleton or empty)
and hypergraphs (e.g., an edge $\left\{  a,b,c,d\right\}  $ becomes an edgery
with $6$ edges).

\item \textbf{Definition.} Let $G=\left(  V,E,\varphi\right)  $ be an
ambigraph. The \emph{chromatic symmetric function} of $G$ is defined to be the
formal power series%
\[
X_{G}:=\sum_{f\text{ is a proper coloring of }G}\mathbf{x}_{f}%
,\ \ \ \ \ \ \ \ \ \ \text{where }\mathbf{x}_{f}=\prod_{v\in V}x_{f\left(
v\right)  }.
\]
This is a symmetric function in $x_{1},x_{2},x_{3},\ldots$ over $\mathbb{Z}$.

\item Again, we can define the chromatic polynomial $\chi_{G}$ accordingly:%
\begin{align*}
\chi_{G}\left(  q\right)   &  =X_{G}\left(  \underbrace{1,1,\ldots,1}_{q\text{
ones}},0,0,0,\ldots\right) \\
&  =\left(  \text{\# of proper colorings of }G\text{ with colors in }\left\{
1,2,\ldots,q\right\}  \right)  .
\end{align*}


\item \textbf{Theorem (all-subsets Whitney formula;
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}).} Let $G=\left(  V,E,\varphi\right)  $ be an ambigraph. Then,%
\[
X_{G}=\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert F\right\vert
}p_{\lambda\left(  V,\operatorname*{union}F\right)  }.
\]
Here, $\operatorname*{union}F$ denotes the set $\bigcup\limits_{e\in F}%
\varphi\left(  e\right)  $, which consists of all edges of all edgeries in $F$.

\item We can get rid of some (not all) cancellation in this formula by
introducing broken circuits.
\end{itemize}

\newpage

\section{Whitney formulas for ambigraphs}

\begin{itemize}
\item \textbf{Definition.} Let $G=\left(  V,E,\varphi\right)  $ be an
ambigraph. A \emph{cycle} of $G$ means a list
\[
\left(  v_{1},e_{1},v_{2},e_{2},\ldots,v_{m},e_{m},v_{m+1}\right)
\]
with the following properties:

\begin{itemize}
\item $v_{1},v_{2},\ldots,v_{m+1}\in V$ and $e_{1},e_{2},\ldots,e_{m}\in E$.

\item $m\geq1$.

\item $v_{m+1}=v_{1}$.

\item The vertices $v_{1},v_{2},\ldots,v_{m}$ are pairwise distinct.

\item The edgeries $e_{1},e_{2},\ldots,e_{m}$ are pairwise distinct.

\item $\left\{  v_{i},v_{i+1}\right\}  \in\varphi\left(  e_{i}\right)  $ for
every $i\in\left\{  1,2,\ldots,m\right\}  $.
\end{itemize}

If $\left(  v_{1},e_{1},v_{2},e_{2},\ldots,v_{m},e_{m},v_{m+1}\right)  $ is a
cycle of $G$, then the set $\left\{  e_{1},e_{2},\ldots,e_{m}\right\}  $ is
called a \emph{circuit} of $G$.

\item \textbf{Definition.} Let $G=\left(  V,E,\varphi\right)  $ be an
ambigraph. A \emph{labeling function} means a map $\ell:E\rightarrow X$ for
some totally ordered set $X$. Its value $\ell\left(  e\right)  $ is called the
\emph{label} of an edgery $e$.

\item \textbf{Definition.} Let $G=\left(  V,E,\varphi\right)  $ be an
ambigraph. Fix a labeling function $\ell:E\rightarrow X$. If $C$ is a circuit
of $G$, and if $C$ contains a unique \textbf{singleton} edgery $e$ of highest
label (among all singleton edgeries in $C$), then the set $C\setminus\left\{
e\right\}  $ is called a \emph{broken circuit} of $G$.

\item \textbf{Theorem (broken-circuits Whitney formula for ambigraphs;
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}).} Let $G=\left(  V,E,\varphi\right)  $ be an ambigraph. Let
$\ell:E\rightarrow X$ be a labeling function. Then,%
\[
X_{G}=\sum_{\substack{F\subseteq E;\\F\text{ contains no broken}%
\\\text{circuit of }G\text{ as a subset}}}\left(  -1\right)  ^{\left\vert
F\right\vert }p_{\lambda\left(  V,\operatorname*{union}F\right)  }.
\]


\item Again, we get a formula for $\chi_{G}$ as a corollary. Note that we
cannot simplify $\operatorname*{conn}\left(  V,\operatorname*{union}F\right)
$ this time, since $\left(  V,\operatorname*{union}F\right)  $ needs not be a forest.

\item More generally:

\item \textbf{Theorem (relaxed Whitney formula for ambigraphs;
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}).} Let $G=\left(  V,E,\varphi\right)  $ be an ambigraph. Let
$\ell:E\rightarrow X$ be a labeling function. Let $\mathfrak{K}$ be some set
of broken circuits of $G$ (not necessarily containing all of them). Then,%
\[
X_{G}=\sum_{\substack{F\subseteq E;\\F\text{ is }\mathfrak{K}\text{-free}%
}}\left(  -1\right)  ^{\left\vert F\right\vert }p_{\lambda\left(
V,\operatorname*{union}F\right)  }.
\]


\item \textit{Proof.} Quite similar to the one for graphs.
\end{itemize}

\newpage

\section{Weighted versions}

\begin{itemize}
\item A weighted version of the chromatic symmetric function was defined for
graphs by \href{https://doi.org/10.1016/j.ejc.2020.103143}{Crew and Spirkl in
2020}. We can do the same for ambigraphs:

\item \textbf{Definition.} A \emph{weight function} on a set $V$ means a map
$w:V\rightarrow\mathbb{N}_{+}$.

\item \textbf{Definition.} Let $G=\left(  V,E,\varphi\right)  $ be an
ambigraph. Let $w$ be a weight function on $V$. The \emph{chromatic symmetric
function} of $\left(  G,w\right)  $ is defined to be the formal power series%
\[
X_{G,w}:=\sum_{f\text{ is a proper coloring of }G}\mathbf{x}_{f,w}%
,\ \ \ \ \ \ \ \ \ \ \text{where }\mathbf{x}_{f,w}=\prod_{v\in V}x_{f\left(
v\right)  }^{w\left(  v\right)  }.
\]
This is a symmetric function in $x_{1},x_{2},x_{3},\ldots$ over $\mathbb{Z}$.

\item \textbf{Theorem (weighted relaxed Whitney formula for ambigraphs;
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}).} Let $G=\left(  V,E,\varphi\right)  $ be an ambigraph. Let $w$ be a
weight function on $V$. Let $\ell:E\rightarrow X$ be a labeling function. Let
$\mathfrak{K}$ be some set of broken circuits of $G$ (not necessarily
containing all of them). Then,%
\[
X_{G,w}=\sum_{\substack{F\subseteq E;\\F\text{ is }\mathfrak{K}\text{-free}%
}}\left(  -1\right)  ^{\left\vert F\right\vert }p_{\lambda\left(  \left(
V,\operatorname*{union}F\right)  ,w\right)  }.
\]
Here, $\lambda\left(  H,w\right)  $ (for a graph $H$) means the partition
whose parts are the \textbf{total weights} of the connected components of $H$.

\item \textit{Proof.} Analogous to the unweighted case.

\item The advantage of $X_{G,w}$ (compared to $X_{G}$) is the existence of a
deletion-contraction recurrence. Note:

\begin{itemize}
\item To contract an edgery $e$ means to contract every edge of $e$
simultaneously. Loops are removed if they appear.

\item When an edge is contracted, the weights of its endpoints are added.
\end{itemize}
\end{itemize}

\newpage

\section{Matroids}

\begin{itemize}
\item Some features of graphs are generalized by matroids.

\item In particular, the chromatic polynomial $\chi_{G}$ of a graph $G$ is
generalized by the characteristic polynomial $\widetilde{\chi}_{M}$ of a
matroid $M$.

\item \textbf{Definition.} Let $M$ be a matroid with ground set $E$, rank
function $r_{M}$ and rank $m$. The \emph{characteristic polynomial}
$\widetilde{\chi}_{M}$ of the matroid $M$ is defined to be the polynomial%
\begin{align*}
\widetilde{\chi}_{M}  &  =\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert
F\right\vert }x^{m-r_{M}\left(  F\right)  }\\
&  =\left[  \overline{\varnothing}=\varnothing\right]  \sum_{F\in
\operatorname*{Flats}M}\underbrace{\mu\left(  \overline{\varnothing},F\right)
}_{\substack{\text{M\"{o}bius function of}\\\text{the lattice of flats}%
}}x^{m-r_{M}\left(  F\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(  \text{where }%
\overline{\varnothing}\text{ is the rank-}0\text{ flat, i.e., the set of
loops}\right) \\
&  \in\mathbb{Z}\left[  x\right]  .
\end{align*}


\item There is also a slightly different definition, which has no $\left[
\overline{\varnothing}=\varnothing\right]  $ factor. These agree if $M$ has no loops.

\item Matroids also have circuits (= minimal dependent sets) and therefore,
given a labeling function $\ell:E\rightarrow X$, also have broken circuits (=
circuits minus their highest-label element).

\item \textbf{Theorem (relaxed Whitney formula; explicitly
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}, but essentially
\href{https://doi.org/10.37236/4356}{\textbf{Dohmen/Trinks 2014}}).} Let $M$
be a matroid with ground set $E$ and rank $m$. Let $\ell:E\rightarrow X$ be a
labeling function. Let $\mathfrak{K}$ be some set of broken circuits of $M$
(not necessarily containing all of them). Then,%
\[
\widetilde{\chi}_{M}=\sum_{\substack{F\subseteq E;\\F\text{ is }%
\mathfrak{K}\text{-free}}}\left(  -1\right)  ^{\left\vert F\right\vert
}x^{m-r_{M}\left(  F\right)  }.
\]


\item \textbf{Theorem (generalized Whitney formula; explicitly
\href{https://www.cip.ifi.lmu.de/~grinberg/algebra/chromatic.pdf}{\textbf{G.
2016+}}, but essentially
\href{https://doi.org/10.37236/4356}{\textbf{Dohmen/Trinks 2014}}).} Let $M$
be a matroid with ground set $E$ and rank $m$. Let $\ell:E\rightarrow X$ be a
labeling function. Let $\mathfrak{K}$ be some set of broken circuits of $M$
(not necessarily containing all of them). Let $a_{K}$ be an element of the
base ring for every $K\in\mathfrak{K}$. Then,
\[
\widetilde{\chi}_{M}=\sum_{F\subseteq E}\left(  -1\right)  ^{\left\vert
F\right\vert }\left(  \prod_{\substack{K\in\mathfrak{K};\\K\subseteq F}%
}a_{K}\right)  x^{m-r_{M}\left(  F\right)  }.
\]


\item I am not aware of any generalization of $X_{G}$ to matroids. Are you?
\end{itemize}

\newpage

\section{Questions}

\begin{itemize}
\item I think ambigraphs and coisotropic hyperplane arrangements are worth exploring!

\item \textbf{Question.} What can we say about $\chi_{\mathcal{A}_{D}^{\perp
},\perp}$ for general $D$ ?

\item \textbf{Question.} Are there similar formulas for the Tutte polynomial?

\item \textbf{Question.} Is there a
\href{https://math.mit.edu/~rstan/pubs/pubfiles/100.pdf}{Stanley $\left(
-1\right)  $-color theorem} for ambigraphs?

(The sign of $\left(  -1\right)  ^{\left\vert \operatorname*{V}\left(
G\right)  \right\vert }\chi_{G}\left(  -1\right)  $ is inconsistent, so maybe
not, or it is an alternating sum.)

\item \textbf{Question.} Is there a Tutte polynomial for ambigraphs?

\item \textbf{Question.} Is there a chromatic homology theory (categorifying
$\chi_{G}$) for ambigraphs?
\end{itemize}

\bigskip

\section{I thank}

\begin{itemize}
\item \textbf{Alexander Postnikov} for a crucial suggestion on the hyperplane
arrangement part.

\item \textbf{Richard P. Stanley} for selling me on hyperplane arrangements.

\item \textbf{Kurusch Ebrahimi-Fard} for the invitation.

\item \textbf{you} for your patience.
\end{itemize}


\end{document}