big picture goals of the reu

1. Hoffman bound. For a finite graph $G$, $\chi(G) \ge \left\lceil 1 +\frac{\mu_1(G) }{-\mu_n(G) } \right\rceil$ (Spielman 19.3)

2. If $\mathcal G$ is a bounded-degree Borel pmp graph,

   1. i.e. its vertex set is a standard probability set with measure $\mu$
   2. Theorem 6.8 in HST (2026)

   $$ \chi_\mu^\text{ap}(\mathcal G) \ge \left\lceil 1 +\frac{M(T_{\mathcal G}) }{-m(T_{\mathcal G}) } \right\rceil $$

   • where $T_\mathcal G$ is the adjacency operator for $\mathcal G$

   • $M$ and $m$ are “approximate eigenvalues”

   • $M(T_\mathcal G) = \max$ spectral value, $m(T_\mathcal G) = \min$ spectral value (Courant-Fischer)

     $$ M(T_\mathcal G) = \sup_{ne 0} \frac{\lang T_\mathcal G f, f\rang}{\lang f, f\rang} $$

   • $\chi_\mu^\text{ap}$ is the approximate measurable chromatic number

     • in general: measurable chromatic number ≥ approximate measurable chromatic number
     • approximate measurable can be lower than the “real” chromatic number

3. Another result that may be extendable to infinite graphs: Nikiforov’s bound.

   For a finite graph $G$, $\chi(G)\ge 1+\frac{\mu_1(G)}{\lambda_1(G) - \mu_1(G)}$.

4. Is there a descriptive version?

adjacency operator

<aside> <img src="/icons/pencil_yellow.svg" alt="/icons/pencil_yellow.svg" width="40px" />

Def. Let $\mathcal G$ be bounded-degree with $V(\mathcal G) = \R$ with Lebesgue measure $\mu$.

$$ L^2(\R)=\left\{ f:\R\to \mathbb C \mid

\int_\R |f(x)|^2 \ dx <\infty

\right\} $$

The adjacency operator of $\mathcal G$ is $T_\mathcal G:L^2(\R)\to L^2(\R)$ by

$$ \left(T_\mathcal G (f)\right)(x) = \sum_{y\sim x} f(y)

$$

</aside>

Claim. The image of $L^2(\R)$ under $T_\mathcal G$ is in $L^2(\R)$. Indeed, $T_\mathcal G$ is a bounded operator.

Proof:

Let $d$ bound the degrees of $\mathcal G$, i.e. $\sup_{v\in V} \deg(v) \le d$.

$$ \left| \left(T_\mathcal G (f)\right)(x) \right|^2

\left| \sum_{y\sim x} f(y) \right|^2

\le \deg(x)\cdot \sum_{y\sim x} \left| f(y) \right|^2

\le d\cdot \sum_{y\sim x} \left| f(y) \right|^2 $$

So indeed,

$$ {\|T_\mathcal G (f)\|_2}^2

\int \left| \left(T_\mathcal G (f)\right)(x) \right|^2 \ dx \le

\int d\cdot \sum_{y\sim x} \left| f(y) \right|^2\ dx\\

=d\cdot \int \sum_{y\sim x} \left| f(x) \right|^2\ dx

\le \int d^2\cdot \left| f(x) \right|^2\ dx

= d^2\cdot \int \left| f(x) \right|^2\ dx

=d^2{\|f\|_2}^2 $$

mass transport step in this proof:

want to show: $\forall f\in L^2(\R)$

$$ \int \sum_{y\sim x} \left| f(y) \right|^2\ dx

= (\le ?) \int d\cdot \left| f(x) \right|^2\ dx

$$

let

$$ \varphi(x,y) = |f(x)|^2 $$

be our transport

we know that

$$ \int \sum\limits_{y \sim x} \varphi(x,y) \ dx

\int \sum\limits_{y \sim x} \varphi(y,x) \ dx\\[4pt]

\int \sum\limits_{y \sim x} |f(x)|^2 \ dx

\int \sum\limits_{y \sim x} |f(y)|^2 \ dx $$