Complexes of Graphs with Bounded Matching Size

NEW

Problem: For positive integers $n,k$, let $NM_k(n)$ be the simplicial complex whose vertices are the edges of $K_n$, and whose faces are graphs $G\subseteq K_n$ with matching number $\nu(G)<k$. The natural action of $S_n$ on $[n]$ induces an action on

$$V_{n,k}:=\widetilde H_{3k-4}(NM_k(n);\mathbb C).$$

The question asks for the complex $S_n$-module $V_{n,k}$. If $k\ge2$ and $n<2k$, then $NM_k(n)$ is a simplex, so $V_{n,k}=0$. For $k=1$, $V_{n,1}\cong \mathbf 1$ in degree $-1$.

Result: For $n\ge 2k$, the character of $V_{n,k}$ is as follows. For $\sigma\in S_n$, let $\mathcal O_\sigma$ be the set of orbits of the cyclic group $\langle\sigma\rangle$ acting on the edge set $\binom{[n]}2$. For $A\subseteq\mathcal O_\sigma$, write

$$E(A):=\bigcup_{O\in A}O\subseteq \binom{[n]}2.$$

Then

$$\boxed{ \chi_{V_{n,k}}(\sigma) = (-1)^{k-1} \sum_{\substack{A\subseteq\mathcal O_\sigma\\ \nu(E(A))<k}} (-1)^{|A|}. }$$

Equivalently, summing over all $\sigma$-invariant graphs $G\subseteq K_n$ with $\nu(G)<k$,

$$\chi_{V_{n,k}}(\sigma) = (-1)^{k-1} \sum_{\substack{G\in NM_k(n)\\ \sigma G=G}} (-1)^{o_\sigma(G)},$$

where $o_\sigma(G)$ is the number of $\langle\sigma\rangle$-orbits on $E(G)$.

This determines the $S_n$-module completely. Explicitly, the multiplicity of the Specht module $S^\lambda$ is

$$m_\lambda = \sum_{\mu\vdash n} \frac{\chi^\lambda(\mu)}{z_\mu}\, \chi_{V_{n,k}}(\sigma_\mu),$$

where $\sigma_\mu$ has cycle type $\mu$, $z_\mu=\prod_i i^{m_i}m_i!$, and $\chi^\lambda$ is the irreducible character of $S_n$.

Proof: Linusson–Shareshian–Welker prove that $NM_k(n)$ has reduced homology concentrated in degree $3k-4$. Hence the equivariant Euler–Poincaré principle gives

$$\sum_i(-1)^i\operatorname{tr}(\sigma\mid \widetilde C_i(NM_k(n))) = (-1)^{3k-4}\chi_{V_{n,k}}(\sigma).$$

A face $F$ contributes to the trace only if $\sigma F=F$. If $F$ is a union of $m$ edge-orbits of lengths $\ell_1,\dots,\ell_m$, then the orientation sign of $\sigma$ on $F$ is

$$\prod_{j=1}^m(-1)^{\ell_j-1}=(-1)^{|F|-m}.$$

Since $\dim F=|F|-1$, its signed chain contribution is

$$(-1)^{|F|-1}(-1)^{|F|-m}=-(-1)^m.$$

Thus

$$\sum_i(-1)^i\operatorname{tr}(\sigma\mid \widetilde C_i) = -\sum_{\substack{F\in NM_k(n)\\ \sigma F=F}}(-1)^{o_\sigma(F)}.$$

Multiplying by $(-1)^{3k-4}$ gives

$$\chi_{V_{n,k}}(\sigma) = (-1)^{3k-3} \sum_{\substack{F\in NM_k(n)\\ \sigma F=F}}(-1)^{o_\sigma(F)} = (-1)^{k-1} \sum_{\substack{F\in NM_k(n)\\ \sigma F=F}}(-1)^{o_\sigma(F)}.$$

This is the stated formula. Since complex characters determine complex $S_n$-modules, the multiplicity formula gives the full module structure.

Citation: Uses the homology concentration theorem of Linusson–Shareshian–Welker, “Complexes of graphs with bounded matching size,” arXiv:math/0410345, Theorem 1.1. The character formula follows from equivariant Euler–Poincaré.