<commit_before>\documentclass{article}
\usepackage{amsmath}
\usepackage{cite}
\title{How Combinatorics Improves Tree Enumeration}
\begin{document}
\maketitle

\section{Graph Coloring Counting}

Definition

The chromatic function is a polynomial proved by deletion/contraction
induction.

\section{Inclusion/Exclusion and Whitney's Solution}

\[
\chi(G,n) = \sum_{k=0}^{k=|E|}(-1)^k \text{\# }n\text{ colorings violating at least }
k\text{ edges}
\]

\[
\chi(G,n) = \sum_{A\subseteq E}(-1)^k 
(\text{\# }n\text{ colorings violating at least the edges }A)
\]

\[
\chi(G,n) = \sum_{A\subseteq E}(-1)^k 
n^{|V(G/A)|} = n^{|V(G)|} + (\text{polynomial in } n \text{ of degree } < |V(G)|)
\]
which establishes that $\chi$ is a polynomial function.  

Whitney\cite{WhitLogExpMath} observed that 
many pairs of terms, those for which $A$ contains at least 
one \textbf{broken circuit}, may be cancelled.

If $A$ contains circuit $C$ and $e\in C$, then $k(G/A) = k(G/(A\setminus e))$

So Whitney's idea was to impose a linear order on a subset $\mathcal{B}$
of the $A$'s occurring 
in the sum so that a pairing $\{A,A'\}$ of the members of $\mathcal{B}$ 
is defined for which $\{A,A'\}=\{A'\cup e, A'\}$, $e\not\in A'$ for some $e$
and $k(G/A) = k(G/(A\setminus e))$.  Two benefits result:
\begin{enumerate}
\item Many of the terms may be omitted.
\item The subsets $A$ for the remaining terms all have a simple form with the 
result $k(G/A) = k(G) - |A| $.

\section{Posets, Inclusion/Exclusion and the Mobius Function}

The Mobius function emerges when the principle of inclusion/exclusion is
applied to enumerations on elements of general posets.

(I'll try a tutorial that directly relates the M\"{o}bius defining recurrance to
solving $g(x) = \sum_{z\le x}f(z)$ for $f()$.)

(The resulting mathematical abstraction is Stanley's 
\textbf{Incidence Algebra} of a poset\cite{StanleyEC1}.)

Stanley: ``Hence M\"{o}bius inversion results in a simplification
of Inclusion-Exclusion under appropriate circumstances. However, we shall also see that
the applications of M\"{o}bius inversion are much 
further-reaching than as a generalization of
Inclusion-Exclusion.'' \cite[ch.~3]{StanleyEC1}.

\section{The Broken Circuit Complex}

\section{Activities}

(Goal: Get at the facts about activities being h-vectors of broken-circuit complexes or 
something.)

(Bigger Goal: Extend that to GM activities, based on a computation tree.  Try to find 
the more generalized broken circuit complex, if possible!)



\section{Literature}

New! Doman and Trinks \cite{DohmenTrinksAbsWitBrok}

\end{enumerate}
\bibliographystyle{plain}
\bibliography{../../bib/MathOfElec}
\end{document}
<commit_msg>elec network appl idea for tree based orderings.<commit_after>\documentclass{article}
\usepackage{amsmath}
\usepackage{cite}
\title{How Combinatorics Improves Tree Enumeration}
\begin{document}
\maketitle

\section{Graph Coloring Counting}

Definition

The chromatic function is a polynomial proved by deletion/contraction
induction.

\section{Inclusion/Exclusion and Whitney's Solution}

\[
\chi(G,n) = \sum_{k=0}^{k=|E|}(-1)^k \text{\# }n\text{ colorings violating at least }
k\text{ edges}
\]

\[
\chi(G,n) = \sum_{A\subseteq E}(-1)^k 
(\text{\# }n\text{ colorings violating at least the edges }A)
\]

\[
\chi(G,n) = \sum_{A\subseteq E}(-1)^k 
n^{|V(G/A)|} = n^{|V(G)|} + (\text{polynomial in } n \text{ of degree } < |V(G)|)
\]
which establishes that $\chi$ is a polynomial function.  

Whitney\cite{WhitLogExpMath} observed that 
many pairs of terms, those for which $A$ contains at least 
one \textbf{broken circuit}, may be cancelled.

If $A$ contains circuit $C$ and $e\in C$, then $k(G/A) = k(G/(A\setminus e))$

So Whitney's idea was to impose a linear order on a subset $\mathcal{B}$
of the $A$'s occurring 
in the sum so that a pairing $\{A,A'\}$ of the members of $\mathcal{B}$ 
is defined for which $\{A,A'\}=\{A'\cup e, A'\}$, $e\not\in A'$ for some $e$
and $k(G/A) = k(G/(A\setminus e))$.  Two benefits result:
\begin{enumerate}
\item Many of the terms may be omitted.
\item The subsets $A$ for the remaining terms all have a simple form with the 
result $k(G/A) = k(G) - |A| $.

\section{Posets, Inclusion/Exclusion and the Mobius Function}

The Mobius function emerges when the principle of inclusion/exclusion is
applied to enumerations on elements of general posets.

(I'll try a tutorial that directly relates the M\"{o}bius defining recurrance to
solving $g(x) = \sum_{z\le x}f(z)$ for $f()$.)

(The resulting mathematical abstraction is Stanley's 
\textbf{Incidence Algebra} of a poset\cite{StanleyEC1}.)

Stanley: ``Hence M\"{o}bius inversion results in a simplification
of Inclusion-Exclusion under appropriate circumstances. However, we shall also see that
the applications of M\"{o}bius inversion are much 
further-reaching than as a generalization of
Inclusion-Exclusion.'' \cite[ch.~3]{StanleyEC1}.

\section{The Broken Circuit Complex}

\section{Activities}

(Goal: Get at the facts about activities being h-vectors of broken-circuit complexes or 
something.)

(Bigger Goal: Extend that to GM activities, based on a computation tree.  Try to find 
the more generalized broken circuit complex, if possible!)

\section{Applications}

Why are general computation tree orders better?  Suppose an electrical network has resistors
A, B, and C.  Properties of $N/A$ may depend more on $B$ than $C$, while properties of
$N\setminus A$ may depend more on $C$ than $B$. EG: $N=(A \text{ ser } B) \text{ par } C$.
$N/A = B \text{ par } C$, but $N\setminus A = C$.  If $g(B) >> g(C)$, 
$g(N/A) = g(B) + g(C) \approx g(B)$
but $g(N\setminus A) = g(C)$ 



\section{Literature}

New! Doman and Trinks \cite{DohmenTrinksAbsWitBrok}

\end{enumerate}
\bibliographystyle{plain}
\bibliography{../../bib/MathOfElec}
\end{document}

{'fraction_non_alphanumeric': 0.13949088407292742, 'fraction_numerical': 0.002407980736154111, 'mean_word_length': 4.369344413665743, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2621388', 'n_tokens_mistral': 2069, 'n_tokens_neox': 1944, 'n_words': 712}