\(\DeclarePairedDelimiterX{\Set}[2]{\{}{\}}{#1 \nonscript\;\delimsize\vert\nonscript\; #2}\) \( \DeclarePairedDelimiter{\set}{\{}{\}}\) \( \DeclarePairedDelimiter{\parens}{\left(}{\right)}\) \(\DeclarePairedDelimiterX{\innerproduct}[1]{\langle}{\rangle}{#1}\) \(\newcommand{\ip}[1]{\innerproduct{#1}}\) \(\newcommand{\bmat}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\barray}[1]{\left[\hspace{2.0pt}\begin{matrix}#1\end{matrix}\hspace{2.0pt}\right]}\) \(\newcommand{\mat}[1]{\begin{matrix}#1\end{matrix}}\) \(\newcommand{\pmat}[1]{\begin{pmatrix}#1\end{pmatrix}}\) \(\newcommand{\mathword}[1]{\mathop{\textup{#1}}}\)
Needs:
Ordered Undirected Graphs
Chordal Graphs
Needed by:
None.
Links:
Sheet PDF
Graph PDF

Filled Graphs

Why

We want to talk about optimally eliminating variables in a system of linear equations.1

Definition

An ordered undirected graph is filled or monotone transitive if all higher neighborhoods induce complete subgraphs. An ordering $\sigma $ of an undirected graph $(V, E)$ is a perfect elimination ordering if the ordered undirected graph $((V, E), \sigma )$ is filled.

Let $G = ((V, E), \sigma )$ be an ordered undirected graph. $G$ is filled if, for all $v \in V$, $w, z \in \adjp(v) \implies \set{w, z} \in E$. Equivalently stated, $G$ is filled if, for all $i < j < k$, $\set{\sigma (i), \sigma (j)} \in E$ and $\set{\sigma (i), \sigma (k)} \in E$ imply $\set{\sigma (j), \sigma (k)} \in E$.

Chordality

If $(V, E, \sigma )$ is a filled graph, then $(V, E)$ is chordal.
Take the vertex with the lowest index on a cycle of length greater than three. Take

  1. Future editions will expand. For example, this sheet is needed for perfect elimination orderings. ↩︎
Copyright © 2023 The Bourbaki Authors — All rights reserved — Version 13a6779cc About Show the old page view