Introduction
Let G = ( V , E ) G=(V,E) G = ( V , E ) G G G
M ( G ) = k [ u e : e ∈ E ] / ( u e u f : e ∩ f ≠ ∅ ) . \mathcal{M}(G)=\mathbb{k}[u_e:e\in E]/(u_eu_f:e\cap f\ne\varnothing). M ( G ) = k [ u e : e ∈ E ] / ( u e u f : e ∩ f = ∅ ) . In this algebra, we define the signed incidence sums
θ v = ∑ e = ( v , w ) u e − ∑ e = ( w , v ) u e for all v ∈ V , \theta_v=\sum_{e=(v,w)}u_e-\sum_{e=(w,v)}u_e \qquad\text{for all }v\in V, θ v = e = ( v , w ) ∑ u e − e = ( w , v ) ∑ u e for all v ∈ V , where an orientation of G G G D ( G ) \mathcal{D}(G) D ( G ) θ v \theta_v θ v Dunkl matching algebra . The goal of the present note is to understand this algebra D ( G ) \mathcal{D}(G) D ( G )
The homogeneous parts D ( G ) k \mathcal{D}(G)_k D ( G ) k D ( G ) \mathcal{D}(G) D ( G ) k [ x v ∣ v ∈ V ] \mathbf{k}[x_v \mid v \in V] k [ x v ∣ v ∈ V ] M M M
p M = p M ( x ) = ∏ ( i , j ) ∈ M ( x i − x j ) ∈ k [ x v ∣ v ∈ V ] . p_M=p_M(x)=\prod_{(i,j)\in M}(x_i-x_j)\in\mathbf{k}[x_v\mid v\in V]. p M = p M ( x ) = ( i , j ) ∈ M ∏ ( x i − x j ) ∈ k [ x v ∣ v ∈ V ] . For any k ≥ 0 k\ge0 k ≥ 0
P k ( G ) : = span k { p M : M is a k -matching of G } of k [ x v ∣ v ∈ V ] . P_k(G):=\operatorname{span}_{\mathbf{k}}\{p_M:M\text{ is a }k\text{-matching of }G\}\text{ of }\mathbf{k}[x_v\mid v\in V]. P k ( G ) := span k { p M : M is a k -matching of G } of k [ x v ∣ v ∈ V ] . The main results we shall show are the following:
dim D ( G ) k = dim P k ( G ) ; \dim\mathcal{D}(G)_k=\dim P_k(G); dim D ( G ) k = dim P k ( G ) ; see Theorem 3.2 . More precisely, the proof gives a canonical perfect pairing between D ( G ) k \mathcal{D}(G)_k D ( G ) k P k ( G ) P_k(G) P k ( G ) Remark 3.3 ); thus, P k ( G ) P_k(G) P k ( G ) D ( G ) k \mathcal{D}(G)_k D ( G ) k D ( G ) \mathcal{D}(G) D ( G ) ∏ ( i , j ) ∈ M ( x i − x j ) \prod_{(i,j)\in M}(x_i-x_j) ∏ ( i , j ) ∈ M ( x i − x j )
P k ( K n ) ≅ S ( n − k , k ) . P_k(K_n)\cong S^{(n-k,k)}. P k ( K n ) ≅ S ( n − k , k ) . Here S ( n − k , k ) S^{(n-k,k)} S ( n − k , k ) ( n − k , k ) (n-k,k) ( n − k , k ) D ( K n ) \mathcal{D}(K_n) D ( K n ) n n n Theorem 4.1 . In characteristic zero, we also obtain the presentation
D ( K n ) ≅ k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) ; \mathcal{D}(K_n)\cong\mathbf{k}[z_1,\ldots,z_n]/(z_1+\cdots+z_n,z_1^2,\ldots,z_n^2); D ( K n ) ≅ k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) ; see Theorem 4.4 .
k -linked ⟹ k -saturated ⟹ k -connected ; k\text{-linked}\Longrightarrow k\text{-saturated}\Longrightarrow k\text{-connected}; k -linked ⟹ k -saturated ⟹ k -connected ; see Propositions 5.4 and 5.11 . In degree 2 2 2
P 2 ( G ) = P 2 ( K n ) ⟺ G is 2 -connected P_2(G)=P_2(K_n)\Longleftrightarrow G\text{ is }2\text{-connected} P 2 ( G ) = P 2 ( K n ) ⟺ G is 2 -connected for n ≥ 4 n\ge4 n ≥ 4 Theorem 5.9 . We also show that if G ‾ \overline{G} G G G G Theorem 5.12 .
The matching generating polynomial and the Dunkl Hilbert series of G G G D ( G ) \mathcal{D}(G) D ( G ) P 3 P_3 P 3 K 3 K_3 K 3 1 + 2 t 1+2t 1 + 2 t 1 + 2 t 1+2t 1 + 2 t 1 + 3 t 1+3t 1 + 3 t
D ( G ) = M ( G ) ⟺ G is a forest ; \mathcal{D}(G)=\mathcal{M}(G)\Longleftrightarrow G\text{ is a forest}; D ( G ) = M ( G ) ⟺ G is a forest ; see Proposition 5.15 . For a unicyclic graph with unique cycle C C C F = G − V ( C ) F = G - V(C) F = G − V ( C )
0 ⟶ M ( F ) ( − 1 ) ⟶ M ( G ) ⟶ ⨁ k ≥ 0 P k ( G ) ⟶ 0. 0 \longrightarrow\mathcal{M}(F)(-1) \longrightarrow\mathcal{M}(G) \longrightarrow\bigoplus_{k \ge0} P_k(G) \longrightarrow0. 0 ⟶ M ( F ) ( − 1 ) ⟶ M ( G ) ⟶ k ≥ 0 ⨁ P k ( G ) ⟶ 0. and hence (using the notation m G \mathbf{m}_G m G G G G
Hilb ( D ( G ) , t ) = m G ( t ) − t m F ( t ) ; \operatorname{Hilb}(\mathcal{D}(G),t) = \mathbf{m}_G(t) - t\mathbf{m}_F(t); Hilb ( D ( G ) , t ) = m G ( t ) − t m F ( t ) ; see Theorem 5.16 . Minimal pairs with the same matching generating polynomial but different Dunkl Hilbert series occur on 4 vertices in general, on 5 vertices among connected graphs, and on 6 vertices among 2-connected graphs; see Proposition 5.17 and Remark 5.18 .
Finally, we survey a related construction in the larger square-zero edge algebra [24 ] , where distinct incident edge generators are allowed to multiply. For each nontrivial vertex cut δ ( S ) \delta(S) δ ( S )
η S : = ∏ e ∈ δ ( S ) u e \eta_S := \prod_{e \in\delta(S)} u_e η S := e ∈ δ ( S ) ∏ u e and impose the relations η S = 0 \eta_S = 0 η S = 0 S S S u F u_F u F F F F G G G Propositions A.1 and A.2 ; these results are not new, so we provide no proofs.
Motivation. This work is inspired by the Fomin–Kirillov approach to Schubert calculus, see [10 , 2 , 18 ] . However in our set-up the adjective “Dunkl” is motivational only. Unlike the Fomin–Kirillov algebra [10 ] , our matching algebra is commutative and kills every product of two incident edge generators.
Recall that the Fomin–Kirillov quadratic algebra E n \mathcal{E}_n E n [ i j ] = − [ j i ] [ij] = -[ji] [ ij ] = − [ j i ] [ i j ] 2 = 0 [ij]^2 = 0 [ ij ] 2 = 0
ϑ i = ∑ j ≠ i [ i j ] \vartheta_i = \sum_{j \ne i} [ij] ϑ i = j = i ∑ [ ij ] are known as the Dunkl elements. A fundamental feature of the construction is that these elements commute, and the commutative subalgebra which they generate provides an algebraic model for the cohomology ring of the complete flag variety; see [10 ] . This point of view has subsequently led to variants for other Coxeter groups, quantum cohomology, K K K
Blasiak, Liu, and Mészáros [7 Definition 2.3] have introduced restrictions of this algebra to a graph. For a graph G G G [ n ] [n] [ n ] E G \mathcal{E}_G E G E n \mathcal{E}_n E n [ i j ] [ij] [ ij ] { i , j } \{i,j\} { i , j } G G G
Our construction may be viewed as a quotient of this picture. Give the generator corresponding to an unoriented edge { i , j } \{i,j\} { i , j } u i j = − u j i u_{ij}=-u_{ji} u ij = − u j i
u i j u k ℓ with { i , j } ∩ { k , ℓ } ≠ ∅ , u_{ij}u_{k\ell}\qquad\text{with}\qquad\{i,j\}\cap\{k,\ell\}\ne\varnothing, u ij u k ℓ with { i , j } ∩ { k , ℓ } = ∅ , and kills the generators corresponding to nonedges of G G G M ( G ) \mathcal{M}(G) M ( G ) ϑ i \vartheta_i ϑ i θ i \theta_i θ i D ( G ) D(G) D ( G ) E n ↠ M ( K n ) E_n\twoheadrightarrow\mathcal{M}(K_n) E n ↠ M ( K n ) E G ↠ M ( G ) E_G\twoheadrightarrow\mathcal{M}(G) E G ↠ M ( G ) M ( G ) \mathcal{M}(G) M ( G ) M ( K n ) \mathcal{M}(K_n) M ( K n ) G G G
This truncation changes the nature of the problem considerably. The flag-variety and Bruhat-order connections of the classical setting are replaced by the incidence structure of a graph, while the linear forms x i − x j x_i-x_j x i − x j A A A
Related work. Subalgebras generated by vertices in the commutative algebra generated by edges have been considered in e.g., [24 , 25 ] . Moreover, in the case of complete graphs they also have a geometric interpretation, see [26 ] . Products of arbitrary subfamilies of a vector configuration have a rich theory related to Tutte polynomials; see Berget [5 ] and the zonotopal literature [1 , 15 ] . Our restriction to vertex-disjoint subfamilies is not matroidal: it remembers the incidence of edges at vertices. It also differs from graph Specht modules and their relationship with matching polytopes studied by Liu [21 ] . The construction lies naturally between these two subjects.
Several nearby constructions attach graded objects to matchings but use a different algebraic mechanism. Numata [23 ] studies an Artinian Gorenstein algebra obtained by apolarity from a weighted matching generating function and proves a strong Lefschetz property. Li [19 ] proves strong equivariant log-concavity for the graded permutation representation on the matchings of an arbitrary graph. For perfect matchings of complete graphs, Filmus and Lindzey [11 ] develop harmonic polynomial models involving Specht polynomials and matching-inclusion matrices. Bedratyuk’s graph algebra [4 ] , whose basis is indexed by all simple graphs on a fixed vertex set, also carries Boolean up/down operators and two-row Specht modules. Bergeron, Chan, Soltani, and Zabrocki [3 ] study a construction deceptively parallel to our P k ( K n ) P_k(K_n) P k ( K n ) ξ j − ξ i \xi_j-\xi_i ξ j − ξ i k k k dim P k ( K n ) \dim P_k(K_n) dim P k ( K n ) Remark 4.3 . None of these constructions is the incidence-generated subalgebra D ( G ) ⊆ M ( G ) \mathcal{D}(G)\subseteq\mathcal{M}(G) D ( G ) ⊆ M ( G )
There is one direct overlap at the level of the abstract complete-graph presentation. Jonsson Kling, Lundqvist, Mohammadi, Orth, and Sáenz-de-Cabezón [17 ] study the more general almost complete intersections
k [ z 1 , … , z n ] / ( z 1 2 , … , z n 2 , ( z 1 + ⋯ + z n ) q ) . \mathsf{k}[z_1,\ldots,z_n]/(z_1^2,\ldots,z_n^2,(z_1+\cdots+z_n)^q). k [ z 1 , … , z n ] / ( z 1 2 , … , z n 2 , ( z 1 + ⋯ + z n ) q ) . The quotient occurring in our characteristic-zero presentation of D ( K n ) \mathcal{D}(K_n) D ( K n ) q = 1 q=1 q = 1
AI use statement. The bulk of this paper was written by GPT-5.6 based on old notes (which contained more questions than proofs) and some tactical prompting; in particular, GPT-5.6 contributed all the proofs in § 5 . We have read and verified the entire text and edited it for clarity and style.
Acknowledgments. We thank Per Alexandersson for inspiring conversations early on in the project.
Notations. Throughout, k \mathsf{k} k k \mathsf{k} k
The matching algebra
Let G = ( V , E ) G=(V,E) G = ( V , E ) e , f e,f e , f e ∩ f ≠ ∅ e\cap f\ne\varnothing e ∩ f = ∅ e = f e=f e = f e e e f f f incident if e ∩ f ≠ ∅ e\cap f\ne\varnothing e ∩ f = ∅
Definition 2.1. The matching algebra of G G G k \mathsf{k} k
M ( G ) : = k [ u e : e ∈ E ] / ( u e u f : e ∩ f ≠ ∅ ) . \mathcal{M}(G):=\mathsf{k}[u_e:e\in E]/(u_eu_f:e\cap f\ne\varnothing). M ( G ) := k [ u e : e ∈ E ] / ( u e u f : e ∩ f = ∅ ) . That is, M ( G ) \mathcal{M}(G) M ( G ) k [ u e : e ∈ E ] \mathsf{k}[u_e:e\in E] k [ u e : e ∈ E ] u e u f u_eu_f u e u f e e e f f f e = f e=f e = f u e u_e u e
For a matching M ⊆ E M\subseteq E M ⊆ E G G G
u M : = ∏ e ∈ M u e ∈ M ( G ) , in particular u ∅ : = 1. u_M:=\prod_{e\in M}u_e\in\mathcal{M}(G),\qquad\text{in particular }u_{\varnothing}:=1. u M := e ∈ M ∏ u e ∈ M ( G ) , in particular u ∅ := 1. Proposition 2.2. The elements u M u_M u M M M M G G G k \mathsf{k} k M ( G ) \mathcal{M}(G) M ( G ) M ( G ) \mathcal{M}(G) M ( G )
Hilb ( M ( G ) , t ) = ∑ k ≥ 0 m k ( G ) t k , \operatorname{Hilb}(\mathcal{M}(G),t)=\sum_{k\ge0}m_k(G)t^k, Hilb ( M ( G ) , t ) = k ≥ 0 ∑ m k ( G ) t k , where m k ( G ) m_k(G) m k ( G ) k k k G G G
Proof. The defining ideal ( u e u f : e ∩ f ≠ ∅ ) (u_eu_f:e\cap f\ne\varnothing) ( u e u f : e ∩ f = ∅ ) u e 1 u e 2 ⋯ u e k u_{e_1}u_{e_2}\cdots u_{e_k} u e 1 u e 2 ⋯ u e k e 1 , e 2 , … , e k e_1,e_2,\ldots,e_k e 1 , e 2 , … , e k u M u_M u M M M M G G G u M u_M u M M ( G ) \mathcal{M}(G) M ( G )
Thus, for the complete graph K n K_n K n
Hilb ( M ( K n ) , t ) = ∑ 0 ≤ k ≤ n / 2 n ! 2 k k ! ( n − 2 k ) ! t k \operatorname{Hilb}(\mathcal{M}(K_n),t)=\sum_{0\le k\le n/2}\frac{n!}{2^k k!(n-2k)!}t^k Hilb ( M ( K n ) , t ) = 0 ≤ k ≤ n /2 ∑ 2 k k ! ( n − 2 k )! n ! t k and the complete bipartite graph K a , b K_{a,b} K a , b
Hilb ( M ( K a , b ) , t ) = ∑ k ≥ 0 k ! ( a k ) ( b k ) t k . \operatorname{Hilb}(\mathcal{M}(K_{a,b}),t)=\sum_{k\ge0}k!\binom{a}{k}\binom{b}{k}t^k. Hilb ( M ( K a , b ) , t ) = k ≥ 0 ∑ k ! ( k a ) ( k b ) t k . In particular, dim M ( K n ) \dim\mathcal{M}(K_n) dim M ( K n ) S n S_n S n
Equivalently, if Δ ( G ) \Delta(G) Δ ( G ) G G G L ( G ) L(G) L ( G ) M ( G ) \mathcal{M}(G) M ( G ) k [ Δ ( G ) ] \mathbb{k}[\Delta(G)] k [ Δ ( G )] u e 2 u_e^2 u e 2 M ( G ) \mathcal{M}(G) M ( G ) [6 ] and Jonsson [16 Chapter 5] . Ferrarello and Fröberg [9 ] explicitly relate the Hilbert series of the ordinary Stanley–Reisner ring of a matching complex to graph-subgraph polynomials.
More directly, Dao and Nair [8 ] associate to an arbitrary simplicial complex Δ \Delta Δ
A ( Δ ) : = k [ x 1 , … , x m ] / ( I Δ , x 1 2 , … , x m 2 ) , A(\Delta):=\mathbb{k}[x_1,\ldots,x_m]/(I_\Delta,x_1^2,\ldots,x_m^2), A ( Δ ) := k [ x 1 , … , x m ] / ( I Δ , x 1 2 , … , x m 2 ) , and study its Lefschetz properties. Thus our matching algebra is exactly M ( G ) = A ( Δ ( G ) ) \mathcal{M}(G)=A(\Delta(G)) M ( G ) = A ( Δ ( G )) [22 ] . What we shall study (starting in the next section) is a certain subalgebra D ( G ) D(G) D ( G ) M ( G ) \mathcal{M}(G) M ( G )
Example 2.3. Let G = P 4 G=P_4 G = P 4 1 − 2 − 3 − 4 1-2-3-4 1 − 2 − 3 − 4
M ( P 4 ) = k [ u 12 , u 23 , u 34 ] / ( u 12 2 , u 23 2 , u 34 2 , u 12 u 23 , u 23 u 34 ) . \mathcal{M}(P_4)=\mathbb{k}[u_{12},u_{23},u_{34}]/(u_{12}^2,u_{23}^2,u_{34}^2,u_{12}u_{23},u_{23}u_{34}). M ( P 4 ) = k [ u 12 , u 23 , u 34 ] / ( u 12 2 , u 23 2 , u 34 2 , u 12 u 23 , u 23 u 34 ) . Thus 1 , u 12 , u 23 , u 34 , u 12 u 34 1,\ u_{12},\ u_{23},\ u_{34},\ u_{12}u_{34} 1 , u 12 , u 23 , u 34 , u 12 u 34 M ( P 4 ) \mathcal{M}(P_4) M ( P 4 ) u 12 u 34 u_{12}u_{34} u 12 u 34
Hilb ( M ( P 4 ) , t ) = 1 + 3 t + t 2 , ( u 12 + u 34 ) 2 = 2 u 12 u 34 . \operatorname{Hilb}(\mathcal{M}(P_4),t)=1+3t+t^2,\qquad(u_{12}+u_{34})^2=2u_{12}u_{34}. Hilb ( M ( P 4 ) , t ) = 1 + 3 t + t 2 , ( u 12 + u 34 ) 2 = 2 u 12 u 34 . By contrast, for the triangle K 3 K_3 K 3 M ( K 3 ) \mathcal{M}(K_3) M ( K 3 ) 1 , u 12 , u 13 , u 23 1,u_{12},u_{13},u_{23} 1 , u 12 , u 13 , u 23
Signed incidence sums and the Dunkl matching algebra
Fix an orientation of G G G incidence coefficients ε t , e \varepsilon_{t,e} ε t , e e ∈ E e \in E e ∈ E t ∈ V t \in V t ∈ V e e e v v v w w w
ε v , e = 1 , ε w , e = − 1 , \varepsilon_{v,e}=1,\qquad\varepsilon_{w,e}=-1, ε v , e = 1 , ε w , e = − 1 , and let all other incidence coefficients ε t , e \varepsilon_{t,e} ε t , e t ∈ V ∖ { v , w } t \in V \setminus\{v,w\} t ∈ V ∖ { v , w }
Definition 3.1. For v ∈ V v \in V v ∈ V signed incidence sum
θ v : = ∑ e ∈ E ε v , e u e ∈ M ( G ) . \theta_v:=\sum_{e\in E}\varepsilon_{v,e}u_e\in\mathcal{M}(G). θ v := e ∈ E ∑ ε v , e u e ∈ M ( G ) . The Dunkl matching algebra is the graded subalgebra D ( G ) \mathcal{D}(G) D ( G ) M ( G ) \mathcal{M}(G) M ( G )
D ( G ) : = k [ θ v : v ∈ V ] ⊆ M ( G ) . \mathcal{D}(G):=\mathbb{k}[\theta_v:v\in V]\subseteq\mathcal{M}(G). D ( G ) := k [ θ v : v ∈ V ] ⊆ M ( G ) . Reversing the orientation of an edge amounts to replacing the corresponding generator u e u_e u e − u e -u_e − u e D ( G ) \mathcal{D}(G) D ( G )
θ v 2 = 0 , ∑ v ∈ C θ v = 0 (1) \theta_v^2=0,\qquad\sum_{v\in C}\theta_v=0 \tag*{(1)} θ v 2 = 0 , v ∈ C ∑ θ v = 0 (1) for every vertex v v v C C C
Consider the polynomial ring k [ x v ∣ v ∈ V ] \mathbb{k}[x_v\mid v\in V] k [ x v ∣ v ∈ V ] e e e e = ( i , j ) e=(i,j) e = ( i , j ) p e : = x i − x j p_e:=x_i-x_j p e := x i − x j M M M G G G
p M : = ∏ e ∈ M p e = ∏ e = ( i , j ) ∈ M ( x i − x j ) , so in particular p ∅ : = 1. (2) p_M:=\prod_{e\in M}p_e=\prod_{e=(i,j)\in M}(x_i-x_j),
\qquad\text{so in particular }p_{\varnothing}:=1. \tag*{(2)} p M := e ∈ M ∏ p e = e = ( i , j ) ∈ M ∏ ( x i − x j ) , so in particular p ∅ := 1. (2) Reversing the orientation of an edge changes the corresponding p e p_e p e p M p_M p M
For each integer k ≥ 0 k\geq0 k ≥ 0 Match k ( G ) \operatorname{Match}_k(G) Match k ( G ) k k k G G G k k k k k k
P k ( G ) : = span { p M : M ∈ Match k ( G ) } (3) P_k(G):=\operatorname{span}\{p_M:M\in\operatorname{Match}_k(G)\} \tag*{(3)} P k ( G ) := span { p M : M ∈ Match k ( G )} (3) of k [ x v ∣ v ∈ V ] \mathbb{k}[x_v\mid v\in V] k [ x v ∣ v ∈ V ]
Consider the k \mathbb{k} k k V \mathbb{k}^V k V V V V e v e_v e v S k ( k V ) S^k(\mathbb{k}^V) S k ( k V ) k k k
μ k : S k ( k V ) ⟶ M ( G ) k , e v 1 ⋯ e v k ⟼ θ v 1 ⋯ θ v k , \mu_k:S^k(\mathbb{k}^V)\longrightarrow\mathcal{M}(G)_k,\qquad
e_{v_1}\cdots e_{v_k}\longmapsto\theta_{v_1}\cdots\theta_{v_k}, μ k : S k ( k V ) ⟶ M ( G ) k , e v 1 ⋯ e v k ⟼ θ v 1 ⋯ θ v k , whose image is precisely the k k k D ( G ) k \mathcal{D}(G)_k D ( G ) k D ( G ) \mathcal{D}(G) D ( G )
Theorem 3.2 (Dunkl-polynomial duality). For every k ≥ 0 k\geq0 k ≥ 0
dim D ( G ) k = dim P k ( G ) . (4) \dim\mathcal{D}(G)_k=\dim P_k(G). \tag*{(4)} dim D ( G ) k = dim P k ( G ) . (4) Moreover, for α = ( α v ) v ∈ V ∈ N V \alpha=(\alpha_v)_{v\in V}\in\mathbb{N}^V α = ( α v ) v ∈ V ∈ N V with ∣ α ∣ = k |\alpha|=k ∣ α ∣ = k write
e α : = ∏ v ∈ V e v α v ∈ S k ( k V ) , x α : = ∏ v ∈ V x v α v ∈ k [ x v ∣ v ∈ V ] . e^\alpha:=\prod_{v\in V}e_v^{\alpha_v}\in S^k(\mathbb{k}^V),
\qquad
x^\alpha:=\prod_{v\in V}x_v^{\alpha_v}\in\mathbb{k}[x_v\mid v\in V]. e α := v ∈ V ∏ e v α v ∈ S k ( k V ) , x α := v ∈ V ∏ x v α v ∈ k [ x v ∣ v ∈ V ] . The elements e α e^{\alpha} e α S k ( k V ) S^{k}(\mathbb{k}^{V}) S k ( k V ) ( e α ) ∗ (e^{\alpha})^{*} ( e α ) ∗
ι k : S k ( k V ) ∗ ⟶ k [ x v : v ∈ V ] k , ( e α ) ∗ ⟼ x α . \iota_{k}: S^{k}(\mathbb{k}^{V})^{*} \longrightarrow\mathbb{k}[x_{v}:v\in V]_{k}, \qquad(e^{\alpha})^{*} \longmapsto x^{\alpha}. ι k : S k ( k V ) ∗ ⟶ k [ x v : v ∈ V ] k , ( e α ) ∗ ⟼ x α . Then, for every M ∈ Match k ( G ) M\in\operatorname{Match}_{k}(G) M ∈ Match k ( G )
ι k ( μ k ∗ ( u M ∗ ) ) = p M , (5) \iota_{k}\left(\mu_{k}^{*}(u_{M}^{*})\right)=p_{M}, \tag*{(5)} ι k ( μ k ∗ ( u M ∗ ) ) = p M , (5) where u M ∗ ∈ ( M ( G ) k ) ∗ u_{M}^{*}\in(\mathcal{M}(G)_{k})^{*} u M ∗ ∈ ( M ( G ) k ) ∗ u M u_{M} u M k k k M ( G ) k \mathcal{M}(G)_{k} M ( G ) k u M u_{M} u M
Proof. Fix a k k k M M M (5) . Observe that the map ι k \iota_{k} ι k f ∈ S k ( k V ) ∗ f\in S^{k}(\mathbb{k}^{V})^{*} f ∈ S k ( k V ) ∗ ∑ ∣ α ∣ = k f ( e α ) x α \sum_{|\alpha|=k}f(e^{\alpha})x^{\alpha} ∑ ∣ α ∣ = k f ( e α ) x α (5) , it suffices to show that
( μ k ∗ ( u M ∗ ) ) ( e α ) = [ x α ] p M for every α ∈ N V satisfying ∣ α ∣ = k . (6) \left(\mu_{k}^{*}(u_{M}^{*})\right)(e^{\alpha})=[x^{\alpha}]p_{M}\qquad\text{for every }\alpha\in\mathbb{N}^{V}\text{ satisfying }|\alpha|=k. \tag*{(6)} ( μ k ∗ ( u M ∗ ) ) ( e α ) = [ x α ] p M for every α ∈ N V satisfying ∣ α ∣ = k . (6) So let us fix a family α = ( α v ) v ∈ V ∈ N V \alpha=(\alpha_{v})_{v\in V}\in\mathbb{N}^{V} α = ( α v ) v ∈ V ∈ N V ∣ α ∣ = k |\alpha|=k ∣ α ∣ = k
( μ k ∗ ( u M ∗ ) ) ( e α ) = u M ∗ ( μ k ( e α ) ) = u M ∗ ( ∏ v ∈ V θ v α v ) = [ u M ] ∏ v ∈ V θ v α v . \left(\mu_{k}^{*}(u_{M}^{*})\right)(e^{\alpha})=u_{M}^{*}\left(\mu_{k}(e^{\alpha})\right)=u_{M}^{*}\left(\prod_{v\in V}\theta_{v}^{\alpha_{v}}\right)=[u_{M}]\prod_{v\in V}\theta_{v}^{\alpha_{v}}. ( μ k ∗ ( u M ∗ ) ) ( e α ) = u M ∗ ( μ k ( e α ) ) = u M ∗ ( v ∈ V ∏ θ v α v ) = [ u M ] v ∈ V ∏ θ v α v . (where [ u M ] r [u_{M}]r [ u M ] r u M u_{M} u M r ∈ M ( G ) r\in\mathcal{M}(G) r ∈ M ( G ) (6) , we must show that this scalar is exactly the coefficient [ x α ] p M [x^{\alpha}]p_{M} [ x α ] p M
First suppose that α v ≥ 2 \alpha_{v}\ge2 α v ≥ 2 v v v ∏ v ∈ V θ v α v = 0 \prod_{v\in V}\theta_{v}^{\alpha_{v}}=0 ∏ v ∈ V θ v α v = 0 θ v 2 = 0 \theta_{v}^{2}=0 θ v 2 = 0 (1) . Hence the left-hand side of (6) is zero. On the other hand, p M p_{M} p M x v x_{v} x v M M M [ x α ] p M = 0 [x^{\alpha}]p_{M}=0 [ x α ] p M = 0 (6) holds in this case because both of its sides vanish.
It remains to consider the case when α v ≤ 1 \alpha_{v}\le1 α v ≤ 1 v v v
S : = { v ∈ V : α v = 1 } , S:=\{v\in V:\alpha_{v}=1\}, S := { v ∈ V : α v = 1 } , so that ∣ S ∣ = ∣ α ∣ = k |S|=|\alpha|=k ∣ S ∣ = ∣ α ∣ = k
∏ v ∈ V θ v α v = ∏ v ∈ S θ v = ∏ e ∈ E ( ∑ v ∈ e ε v , e u e ) . (7) \prod_{v\in V}\theta_{v}^{\alpha_{v}}=\prod_{v\in S}\theta_{v}=\prod_{e\in E}\left(\sum_{v\in e}\varepsilon_{v,e}u_{e}\right). \tag*{(7)} v ∈ V ∏ θ v α v = v ∈ S ∏ θ v = e ∈ E ∏ ( v ∈ e ∑ ε v , e u e ) . (7) The coefficient of u M u_{M} u M M M M S S S M M M S S S k k k M M M k = ∣ S ∣ k=|S| k = ∣ S ∣
Assume this condition holds. Then there is a unique way to obtain u M u_{M} u M (7) : for each e ∈ M e\in M e ∈ M u e u_{e} u e v ∈ e ∩ S v\in e\cap S v ∈ e ∩ S u M u_{M} u M (7) is therefore
∏ e ∈ M ; v is the unique element of e ∩ S ε v , e . (8) \prod_{\substack{e\in M;\\ v\text{ is the unique element of }e\cap S}}\varepsilon_{v,e}. \tag*{(8)} e ∈ M ; v is the unique element of e ∩ S ∏ ε v , e . (8) But the coefficient of x v x_{v} x v p e p_{e} p e ε v , e \varepsilon_{v,e} ε v , e (8) is the coefficient of x α = ∏ v ∈ S x v x^{\alpha}=\prod_{v\in S}x_{v} x α = ∏ v ∈ S x v
p M = ∏ e ∈ M p e . p_{M}=\prod_{e\in M}p_{e}. p M = e ∈ M ∏ p e . Thus (6) holds in the α v ≤ 1 \alpha_v \le1 α v ≤ 1 M M M S S S (6) also holds if this condition is violated, since both sides vanish in this case. Hence (6) always holds.
Forget that we fixed α \alpha α (6) , which in turn completes the proof of (5) .
Now forget that we fixed M M M u M ∗ u_M^* u M ∗ M ( G ) k ∗ \mathcal{M}(G)_k^* M ( G ) k ∗ p M p_M p M P k ( G ) P_k(G) P k ( G ) (5) entails
ι k ( im μ k ∗ ) = P k ( G ) , \iota_k(\operatorname{im}\mu_k^*)=P_k(G), ι k ( im μ k ∗ ) = P k ( G ) , so that P k ( G ) = ι k ( im μ k ∗ ) ≅ im μ k ∗ P_k(G)=\iota_k(\operatorname{im}\mu_k^*)\cong\operatorname{im}\mu_k^* P k ( G ) = ι k ( im μ k ∗ ) ≅ im μ k ∗ ι k \iota_k ι k
dim P k ( G ) = dim im μ k ∗ = rank μ k ∗ = rank μ k = dim im μ k = dim D ( G ) k , \dim P_k(G)=\dim\operatorname{im}\mu_k^*=\operatorname{rank}\mu_k^*=\operatorname{rank}\mu_k=\dim\operatorname{im}\mu_k=\dim\mathcal{D}(G)_k, dim P k ( G ) = dim im μ k ∗ = rank μ k ∗ = rank μ k = dim im μ k = dim D ( G ) k , as claimed. □
Thus θ 1 + θ 2 + θ 3 = 0 \theta_1+\theta_2+\theta_3=0 θ 1 + θ 2 + θ 3 = 0 θ i \theta_i θ i K 3 K_3 K 3
D ( K 3 ) = k ⊕ span { θ 1 , θ 2 } , Hilb ( D ( K 3 ) , t ) = 1 + 2 t , \mathcal{D}(K_3)=\mathbb{k}\oplus\operatorname{span}\{\theta_1,\theta_2\},\qquad\operatorname{Hilb}(\mathcal{D}(K_3),t)=1+2t, D ( K 3 ) = k ⊕ span { θ 1 , θ 2 } , Hilb ( D ( K 3 ) , t ) = 1 + 2 t , so here D ( K 3 ) \mathcal{D}(K_3) D ( K 3 ) M ( K 3 ) \mathcal{M}(K_3) M ( K 3 )
The first nontrivial degree-2 example is K 4 K_4 K 4
m 1 = u 12 u 34 , m 2 = u 13 u 24 , m 3 = u 14 u 23 . m_1=u_{12}u_{34},\qquad m_2=u_{13}u_{24},\qquad m_3=u_{14}u_{23}. m 1 = u 12 u 34 , m 2 = u 13 u 24 , m 3 = u 14 u 23 . These are the three degree-2 basis elements of M ( K 4 ) \mathcal{M}(K_4) M ( K 4 )
θ 1 θ 2 = m 2 + m 3 , θ 1 θ 3 = m 1 − m 3 , θ 2 θ 3 = − m 1 − m 2 . \theta_1\theta_2=m_2+m_3,\qquad\theta_1\theta_3=m_1-m_3,\qquad\theta_2\theta_3=-m_1-m_2. θ 1 θ 2 = m 2 + m 3 , θ 1 θ 3 = m 1 − m 3 , θ 2 θ 3 = − m 1 − m 2 . The three displayed vectors have one linear relation and span a 2-dimensional space; since θ 4 = − ( θ 1 + θ 2 + θ 3 ) \theta_4=-(\theta_1+\theta_2+\theta_3) θ 4 = − ( θ 1 + θ 2 + θ 3 ) θ i 2 = 0 \theta_i^2=0 θ i 2 = 0 D ( K 4 ) 2 \mathcal{D}(K_4)_2 D ( K 4 ) 2
Hilb ( D ( K 4 ) , t ) = 1 + 3 t + 2 t 2 . \operatorname{Hilb}(\mathcal{D}(K_4),t)=1+3t+2t^2. Hilb ( D ( K 4 ) , t ) = 1 + 3 t + 2 t 2 . This is the smallest example in which the matching algebra has more degree-2 basis elements than the Dunkl matching algebra has degree-2 dimensions.
Proposition 3.5. The following properties hold.
If G = G 1 ⊔ G 2 G=G_1\sqcup G_2 G = G 1 ⊔ G 2 D ( G ) ≅ D ( G 1 ) ⊗ D ( G 2 ) \mathcal{D}(G)\cong\mathcal{D}(G_1)\otimes\mathcal{D}(G_2) D ( G ) ≅ D ( G 1 ) ⊗ D ( G 2 )
We have D ( G ) k = 0 \mathcal{D}(G)_k=0 D ( G ) k = 0 k > ν ( G ) k>\nu(G) k > ν ( G ) ν ( G ) \nu(G) ν ( G ) G G G G G G
We have dim D ( G ) 1 = ∣ V ∣ − c ( G ) \dim\mathcal{D}(G)_1=|V|-c(G) dim D ( G ) 1 = ∣ V ∣ − c ( G ) c ( G ) c(G) c ( G ) G G G
If H H H G G G
P k ( H ) ⊆ P k ( G ) , dim D ( H ) k ≤ dim D ( G ) k . P_k(H)\subseteq P_k(G),\qquad\dim\mathcal{D}(H)_k\leq\dim\mathcal{D}(G)_k. P k ( H ) ⊆ P k ( G ) , dim D ( H ) k ≤ dim D ( G ) k . Proof. The first assertion follows from the disjoint sets of variables and incidence sums. The second follows from (4) . For the third, observe that P 1 ( G ) P_1(G) P 1 ( G ) x i − x j x_i-x_j x i − x j G G G ∣ V ∣ − c ( G ) |V|-c(G) ∣ V ∣ − c ( G ) k \mathbb{k} k D ( G ) → D ( H ) \mathcal{D}(G)\to\mathcal{D}(H) D ( G ) → D ( H ) u e u_e u e e ∉ E ( H ) e\notin E(H) e ∈ / E ( H ) 0 0 0
Remark 3.6 (Dependence on the characteristic). Although Theorem 3.2 holds over every field, the Hilbert series of D ( G ) \mathcal{D}(G) D ( G ) G = C 5 □ K 2 G=C_5\square K_2 G = C 5 □ K 2 a 0 , … , a 4 , b 0 , … , b 4 a_0,\ldots,a_4,b_0,\ldots,b_4 a 0 , … , a 4 , b 0 , … , b 4
a i a i + 1 , b i b i + 1 , a i b i ( i ∈ Z / 5 Z ) . a_i a_{i+1},\qquad b_i b_{i+1},\qquad a_i b_i\qquad(i\in\mathbb{Z}/5\mathbb{Z}). a i a i + 1 , b i b i + 1 , a i b i ( i ∈ Z /5 Z ) . Then
Hilb ( D ( G ) , t ) = 1 + 9 t + 35 t 2 + 75 t 3 + α k t 4 + 11 t 5 (10) \operatorname{Hilb}(\mathcal{D}(G),t)=1+9t+35t^2+75t^3+\alpha_k t^4+11t^5 \tag*{(10)} Hilb ( D ( G ) , t ) = 1 + 9 t + 35 t 2 + 75 t 3 + α k t 4 + 11 t 5 (10) where α k = 79 \alpha_k=79 α k = 79 char k = 2 \operatorname{char}\mathbb{k}=2 char k = 2 α k = 80 \alpha_k=80 α k = 80 D ( G ) → M ( G ) \mathcal{D}(G)\to\mathcal{M}(G) D ( G ) → M ( G )
Complete graphs and two-row Specht modules
We now specialize to the complete graph K n K_n K n [ n ] [n] [ n ] S n S_n S n k [ x 1 , … , x n ] \mathbf{k}[x_1,\ldots,x_n] k [ x 1 , … , x n ]
σ ( x i ) = x σ ( i ) ( σ ∈ S n ) . \sigma(x_i)=x_{\sigma(i)} \qquad(\sigma\in S_n). σ ( x i ) = x σ ( i ) ( σ ∈ S n ) . Since S n S_n S n k k k K n K_n K n P k ( K n ) P_k(K_n) P k ( K n ) σ ( p M ) = ± p σ ( M ) \sigma(p_M)=\pm p_{\sigma(M)} σ ( p M ) = ± p σ ( M ) P k ( K n ) P_k(K_n) P k ( K n ) S n S_n S n
To identify this representation, let us recall the polynomial realization of the Specht modules. Let λ ⊢ n \lambda\vdash n λ ⊢ n T T T λ \lambda λ 1 , 2 , … , n 1,2,\ldots,n 1 , 2 , … , n T T T i 1 , … , i r i_1,\ldots,i_r i 1 , … , i r
∏ 1 ≤ a < b ≤ r ( x i a − x i b ) . \prod_{1\leq a<b\leq r}(x_{i_a}-x_{i_b}). 1 ≤ a < b ≤ r ∏ ( x i a − x i b ) . The Specht polynomial of T T T T T T
Δ T : = ∏ column C of T ; i 1 , … , i r are the entries of C ∏ 1 ≤ a < b ≤ r ( x i a − x i b ) . \Delta_T:=\prod_{\substack{\text{column }C\text{ of }T;\\ i_1,\ldots,i_r\text{ are the entries of }C}}\ \prod_{1\leq a<b\leq r}(x_{i_a}-x_{i_b}). Δ T := column C of T ; i 1 , … , i r are the entries of C ∏ 1 ≤ a < b ≤ r ∏ ( x i a − x i b ) . The span of the Specht polynomials Δ T \Delta_T Δ T T T T λ \lambda λ S λ S^\lambda S λ [27 Satz 1] or [13 Theorem 5.6.1] .
Now let λ = ( n − k , k ) \lambda=(n-k,k) λ = ( n − k , k ) 0 ≤ k ≤ ⌊ n / 2 ⌋ 0\leq k\leq\lfloor n/2\rfloor 0 ≤ k ≤ ⌊ n /2 ⌋ k k k T T T ( n − k , k ) (n-k,k) ( n − k , k ) k k k M ( T ) M(T) M ( T ) K n K_n K n
Δ T = ± p M ( T ) . \Delta_T=\pm p_{M(T)}. Δ T = ± p M ( T ) . Conversely, every k k k K n K_n K n ( n − k , k ) (n-k,k) ( n − k , k ) P k ( K n ) P_k(K_n) P k ( K n ) p M p_M p M ( n − k , k ) (n-k,k) ( n − k , k )
Theorem 4.1. For every k k k 0 ≤ k ≤ ⌊ n / 2 ⌋ 0\leq k\leq\lfloor n/2\rfloor 0 ≤ k ≤ ⌊ n /2 ⌋ S n S_n S n
P k ( K n ) ≅ S ( n − k , k ) . P_k(K_n)\cong S^{(n-k,k)}. P k ( K n ) ≅ S ( n − k , k ) . Consequently,
Hilb ( D ( K n ) , t ) = ∑ 0 ≤ k ≤ n / 2 ( ( n k ) − ( n k − 1 ) ) t k . \operatorname{Hilb}(D(K_n),t)=\sum_{0\leq k\leq n/2}\left(\binom{n}{k}-\binom{n}{k-1}\right)t^k. Hilb ( D ( K n ) , t ) = 0 ≤ k ≤ n /2 ∑ ( ( k n ) − ( k − 1 n ) ) t k . Proof. The S n S_n S n dim S ( n − k , k ) \dim S^{(n-k,k)} dim S ( n − k , k ) S λ S^\lambda S λ f λ f^\lambda f λ λ \lambda λ
dim S ( n − k , k ) = f ( n − k , k ) = ( n k ) − ( n k − 1 ) = n − 2 k + 1 n − k + 1 ( n k ) . \dim S^{(n-k,k)}=f^{(n-k,k)}=\binom{n}{k}-\binom{n}{k-1}=\frac{n-2k+1}{n-k+1}\binom{n}{k}. dim S ( n − k , k ) = f ( n − k , k ) = ( k n ) − ( k − 1 n ) = n − k + 1 n − 2 k + 1 ( k n ) . Together with (4) , this yields the displayed Hilbert series. □ \square □
To drive this point home, let us compare the span of the Δ M \Delta_M Δ M k k k M M M K n K_n K n E Q H n , k EQH_{n,k} E Q H n , k
W = span { ξ i − ξ j : 1 ≤ i , j ≤ n } , W = \operatorname{span}\{\xi_i-\xi_j: 1 \le i,j \le n\}, W = span { ξ i − ξ j : 1 ≤ i , j ≤ n } , the standard ( n − 1 ) (n-1) ( n − 1 ) S n S_n S n k k k M M M Δ M \Delta_M Δ M ⋀ k W ⊆ ⋀ k k n \bigwedge^k W \subseteq\bigwedge^k \mathbf{k}^n ⋀ k W ⊆ ⋀ k k n k k k ξ j r − ξ i r \xi_{j_r}-\xi_{i_r} ξ j r − ξ i r Δ M \Delta_M Δ M W W W k k k Δ M \Delta_M Δ M S n S_n S n Δ M \Delta_M Δ M Δ N \Delta_N Δ N k k k N N N S n S_n S n
⋀ k W ≅ S ( n − k , 1 k ) \bigwedge^k W \cong S^{(n-k,1^k)} ⋀ k W ≅ S ( n − k , 1 k ) is irreducible in characteristic zero, it follows that
span { Δ M : M ∈ Match k ( K n ) } = ⋀ k W ≅ S ( n − k , 1 k ) . (12) \operatorname{span}\{\Delta_M : M \in\operatorname{Match}_k(K_n)\} = \bigwedge^k W \cong S^{(n-k,1^k)}. \tag*{(12)} span { Δ M : M ∈ Match k ( K n )} = ⋀ k W ≅ S ( n − k , 1 k ) . (12) Thus the complete commutative matching family { p M : M ∈ Match k ( K n ) } \{p_M : M \in\operatorname{Match}_k(K_n)\} { p M : M ∈ Match k ( K n )} S ( n − k , k ) S^{(n-k,k)} S ( n − k , k ) { Δ M : M ∈ Match k ( K n ) } \{\Delta_M : M \in\operatorname{Match}_k(K_n)\} { Δ M : M ∈ Match k ( K n )} S ( n − k , 1 k ) S^{(n-k,1^k)} S ( n − k , 1 k )
( n k ) − ( n k − 1 ) and ( n − 1 k ) , \binom{n}{k}-\binom{n}{k-1}
\qquad\text{and}\qquad
\binom{n-1}{k}, ( k n ) − ( k − 1 n ) and ( k n − 1 ) , which agree only for k = 0 , 1 k=0,1 k = 0 , 1
Already for n = 4 n=4 n = 4 k = 2 k=2 k = 2
p 12 p 34 − p 13 p 24 + p 14 p 23 = 0 p_{12}p_{34}-p_{13}p_{24}+p_{14}p_{23}=0 p 12 p 34 − p 13 p 24 + p 14 p 23 = 0 in commuting variables. The three corresponding exterior products are linearly independent (they span ⋀ 2 W \bigwedge^2 W ⋀ 2 W 3 3 3
Theorem 4.4. Assume that the field k \mathbf{k} k
D ( K n ) ≅ k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) , z i ⟼ θ i . \mathcal{D}(K_n) \cong\mathbf{k}[z_1,\ldots,z_n]/(z_1+\cdots+z_n,z_1^2,\ldots,z_n^2), \qquad z_i \longmapsto\theta_i. D ( K n ) ≅ k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) , z i ⟼ θ i . As an abstract commutative algebra, the quotient in Theorem 4.4 is the case q = 1 q=1 q = 1
k [ z 1 , … , z n ] / ( z 1 2 , … , z n 2 , ( z 1 + ⋯ + z n ) q ) \mathbf{k}[z_1,\ldots,z_n]/(z_1^2,\ldots,z_n^2,(z_1+\cdots+z_n)^q) k [ z 1 , … , z n ] / ( z 1 2 , … , z n 2 , ( z 1 + ⋯ + z n ) q ) studied in detail by Jonsson Kling et al. [17 ] ; among other things, they determine Gröbner bases and Hilbert series for the general family and give another proof of the strong Lefschetz property of the squarefree algebra. We nevertheless include the short Boolean-lattice argument needed for the present case.
Proof. The relations in the ideal ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) (z_1+\cdots+z_n,z_1^2,\ldots,z_n^2) ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) θ 1 , … , θ n \theta_1,\ldots,\theta_n θ 1 , … , θ n (1) , so there is a surjective k \mathbf{k} k
Φ : k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) ⟶ D ( K n ) \Phi:\mathbf{k}[z_1,\ldots,z_n]/(z_1+\cdots+z_n,z_1^2,\ldots,z_n^2)\longrightarrow\mathcal{D}(K_n) Φ : k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) ⟶ D ( K n ) that sends each z i z_i z i θ i \theta_i θ i Φ \Phi Φ
A : = k [ z 1 , … , z n ] / ( z 1 2 , … , z n 2 ) and L : = z 1 + ⋯ + z n ∈ A . A := \mathbf{k}[z_1,\ldots,z_n]/(z_1^2,\ldots,z_n^2) \qquad\text{and}\qquad L := z_1+\cdots+z_n \in A. A := k [ z 1 , … , z n ] / ( z 1 2 , … , z n 2 ) and L := z 1 + ⋯ + z n ∈ A . Note that the k \mathbf{k} k A A A 2 n 2^n 2 n
z S : = ∏ i ∈ S z i for all S ⊆ [ n ] . z_S := \prod_{i\in S} z_i \qquad\text{for all } S\subseteq[n]. z S := i ∈ S ∏ z i for all S ⊆ [ n ] . We must compute the Hilbert function of A / ( L ) A/(L) A / ( L ) dim ( A / ( L ) ) k \dim(A/(L))_k dim ( A / ( L ) ) k k k k [28 ] and [17 §3.1] . We give the elementary argument here for the sake of completeness. We claim that multiplication by L L L k \mathbf{k} k
U r : A r ⟶ A r + 1 , f ⟼ L f U_r : A_r \longrightarrow A_{r+1}, \qquad f \longmapsto Lf U r : A r ⟶ A r + 1 , f ⟼ L f — has maximal rank in every degree (i.e., is injective for r < n / 2 r<n/2 r < n /2 r ≥ n / 2 r\ge n/2 r ≥ n /2 R \mathbb{R} R U r U_r U r 0 0 0 1 1 1 R \mathbb{R} R
The maps U r : A r → A r + 1 U_r:A_r\to A_{r+1} U r : A r → A r + 1 r r r k \mathbf{k} k U : A → A U:A\to A U : A → A up-operator since it raises degrees by 1. Define the down-operator D : A → A D:A\to A D : A → A k \mathbf{k} k
D ( z S ) : = ∑ i ∈ S z S ∖ { i } for each S ⊆ [ n ] . D(z_S) := \sum_{i\in S} z_{S\setminus\{i\}} \qquad\text{for each } S\subseteq[n]. D ( z S ) := i ∈ S ∑ z S ∖ { i } for each S ⊆ [ n ] . This operator decreases degrees by 1; that is, D ( A r ) ⊆ A r − 1 D(A_r)\subseteq A_{r-1} D ( A r ) ⊆ A r − 1 r r r
Give the R \mathbb{R} R A A A z S z_S z S D D D U U U A r A_r A r
D U − U D = ( n − 2 r ) id A r . (13) DU-UD=(n-2r)\operatorname{id}_{A_r}. \tag*{(13)} D U − U D = ( n − 2 r ) id A r . (13) Indeed, for ∣ S ∣ = r |S|=r ∣ S ∣ = r z S ∖ { i } ∪ { j } z_{S\setminus\{i\}\cup\{j\}} z S ∖ { i } ∪ { j } D U ( z S ) DU(z_S) D U ( z S ) U D ( z S ) UD(z_S) U D ( z S ) z S z_S z S n − r n-r n − r r r r
If r < n / 2 r<n/2 r < n /2 0 ≠ f ∈ A r 0\ne f\in A_r 0 = f ∈ A r
∥ U f ∥ 2 = ⟨ U f , U f ⟩ = ⟨ D U f , f ⟩ (since D and U are adjoint) = ⟨ U D f + ( n − 2 r ) f , f ⟩ (since D U = U D + ( n − 2 r ) id A r by (13)) = ⟨ U D f , f ⟩ + ( n − 2 r ) ∥ f ∥ 2 = ∥ D f ∥ 2 + ( n − 2 r ) ∥ f ∥ 2 (again since D and U are adjoint) > 0 (by positive definiteness and since n − 2 r > 0 ), \begin{aligned}
\lVert Uf\rVert^2 &= \langle Uf,Uf\rangle= \langle DUf,f\rangle&&\text{(since }D\text{ and }U\text{ are adjoint)}\\
&= \langle UDf+(n-2r)f,f\rangle&&\text{(since }DU=UD+(n-2r)\operatorname{id}_{A_r}\text{ by (13))}\\
&= \langle UDf,f\rangle+(n-2r)\lVert f\rVert^2\\
&= \lVert Df\rVert^2 +(n-2r)\lVert f\rVert^2 &&\text{(again since }D\text{ and }U\text{ are adjoint)}\\
&>0 &&\text{(by positive definiteness and since }n-2r>0\text{),}
\end{aligned} ∥ U f ∥ 2 = ⟨ U f , U f ⟩ = ⟨ D U f , f ⟩ = ⟨ U D f + ( n − 2 r ) f , f ⟩ = ⟨ U D f , f ⟩ + ( n − 2 r ) ∥ f ∥ 2 = ∥ D f ∥ 2 + ( n − 2 r ) ∥ f ∥ 2 > 0 (since D and U are adjoint) (since D U = U D + ( n − 2 r ) id A r by (13)) (again since D and U are adjoint) (by positive definiteness and since n − 2 r > 0 ), whence U f ≠ 0 Uf\ne0 U f = 0 U r U_r U r A A A r < n / 2 r<n/2 r < n /2 U r U_r U r D r + 1 : A r + 1 → A r D_{r+1}:A_{r+1}\to A_r D r + 1 : A r + 1 → A r D D D A r + 1 A_{r+1} A r + 1 U r U_r U r r < n / 2 r<n/2 r < n /2 D r + 1 D_{r+1} D r + 1 r < n / 2 r<n/2 r < n /2 z S ↔ z [ n ] ∖ S z_S \leftrightarrow z_{[n]\setminus S} z S ↔ z [ n ] ∖ S D r + 1 D_{r+1} D r + 1 U n − r − 1 U_{n-r-1} U n − r − 1 U n − r − 1 = X r ∘ D r + 1 ∘ X r + 1 − 1 U_{n-r-1}=X_r\circ D_{r+1}\circ X_{r+1}^{-1} U n − r − 1 = X r ∘ D r + 1 ∘ X r + 1 − 1 X k X_k X k A k → A n − k A_k\to A_{n-k} A k → A n − k z S z_S z S z [ n ] ∖ S z_{[n]\setminus S} z [ n ] ∖ S D r + 1 D_{r+1} D r + 1 U n − r − 1 U_{n-r-1} U n − r − 1 r < n / 2 r<n/2 r < n /2 n − r − 1 n-r-1 n − r − 1 r r r U r U_r U r r > n / 2 − 1 r>n/2-1 r > n /2 − 1 r ≥ n / 2 r\ge n/2 r ≥ n /2
Thus we have shown that U r U_r U r r < n / 2 r<n/2 r < n /2 r ≥ n / 2 r\ge n/2 r ≥ n /2 U r U_r U r
rank U r = min { dim A r , dim A r + 1 } = min { ( n r ) , ( n r + 1 ) } . \operatorname{rank} U_r=\min\{\dim A_r,\dim A_{r+1}\}=\min\left\{\binom{n}{r},\binom{n}{r+1}\right\}. rank U r = min { dim A r , dim A r + 1 } = min { ( r n ) , ( r + 1 n ) } . (since dim A k = ( n k ) \dim A_k=\binom{n}{k} dim A k = ( k n )
For k = 0 k=0 k = 0 dim ( A / ( L ) ) 0 = 1 \dim(A/(L))_0=1 dim ( A / ( L ) ) 0 = 1 k ≥ 1 k\ge1 k ≥ 1 dim A k = ( n k ) \dim A_k=\binom{n}{k} dim A k = ( k n )
rank U k − 1 = min { ( n k − 1 ) , ( n k ) } . \operatorname{rank} U_{k-1}=\min\left\{\binom{n}{k-1},\binom{n}{k}\right\}. rank U k − 1 = min { ( k − 1 n ) , ( k n ) } . But the degree-k k k A / ( L ) A/(L) A / ( L ) U k − 1 : A k − 1 → A k U_{k-1}:A_{k-1}\to A_k U k − 1 : A k − 1 → A k
dim ( A / ( L ) ) k = ( n k ) − rank U k − 1 = ( n k ) − min { ( n k − 1 ) , ( n k ) } = max { ( n k ) − ( n k − 1 ) , 0 } . \begin{aligned}
\dim(A/(L))_k=\binom{n}{k}-\operatorname{rank} U_{k-1}=\binom{n}{k}-\min\left\{\binom{n}{k-1},\binom{n}{k}\right\} \\
&=\max\left\{\binom{n}{k}-\binom{n}{k-1},0\right\}.
\end{aligned} dim ( A / ( L ) ) k = ( k n ) − rank U k − 1 = ( k n ) − min { ( k − 1 n ) , ( k n ) } = max { ( k n ) − ( k − 1 n ) , 0 } . This agrees with dim D ( K n ) k \dim\mathcal{D}(K_n)_k dim D ( K n ) k Theorem 4.1 . The surjection Φ \Phi Φ
Remark 4.5 (The presentation in positive characteristic). The characteristic-zero hypothesis in Theorem 4.4 is crucial. Over an arbitrary field, the same assignment z i ↦ θ i z_i\mapsto\theta_i z i ↦ θ i
Φ : k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) ⟶ D ( K n ) . \Phi:\mathbf{k}[z_1,\ldots,z_n]/(z_1+\cdots+z_n,z_1^2,\ldots,z_n^2)\longrightarrow\mathcal{D}(K_n). Φ : k [ z 1 , … , z n ] / ( z 1 + ⋯ + z n , z 1 2 , … , z n 2 ) ⟶ D ( K n ) . Suppose now that char k = p > 0 \operatorname{char}\mathbf{k}=p>0 char k = p > 0
U r : A r ⟶ A r + 1 U_r:A_r\longrightarrow A_{r+1} U r : A r ⟶ A r + 1 is the inclusion matrix between the r r r ( r + 1 ) (r+1) ( r + 1 ) [ n ] [n] [ n ] [29 ] shows, when r < n / 2 r<n/2 r < n /2 Z \mathbb{Z} Z
1 , 2 , … , r + 1 (with positive multiplicities) . 1,2,\ldots,r+1\qquad\text{(with positive multiplicities)}. 1 , 2 , … , r + 1 (with positive multiplicities) . Hence U r U_r U r k \mathbf{k} k p > r + 1 p>r+1 p > r + 1 U r U_r U r
p > ⌊ n 2 ⌋ . p>\left\lfloor\frac{n}{2}\right\rfloor. p > ⌊ 2 n ⌋ . Since Theorem 4.1 shows that the Hilbert series of D ( K n ) \mathcal{D}(K_n) D ( K n ) Φ \Phi Φ
p > ⌊ n 2 ⌋ ; p > \left\lfloor\frac{n}{2}\right\rfloor; p > ⌊ 2 n ⌋ ; for p ≤ ⌊ n / 2 ⌋ p \le\lfloor n/2\rfloor p ≤ ⌊ n /2 ⌋ D ( K n ) \mathcal{D}(K_n) D ( K n )
Arbitrary graphs
We begin with conventions. For a finite set W W W K W K_W K W W W W K [ n ] = K n K_{[n]}=K_n K [ n ] = K n K n K_n K n K W K_W K W ∣ W ∣ = n |W|=n ∣ W ∣ = n assume that the vertex set V V V G G G [ n ] = { 1 , 2 , … , n } [n]=\{1,2,\ldots,n\} [ n ] = { 1 , 2 , … , n } , but we expect the reader to understand that all our results hold equally well, after relabeling, for graphs on any other n n n
The spaces P k ( G ) P_k(G) P k ( G ) k k k k [ x v ] k \mathbf{k}[x_v]_k k [ x v ] k P k ( G ) ⊆ P k ( K n ) P_k(G)\subseteq P_k(K_n) P k ( G ) ⊆ P k ( K n ) G G G K n K_n K n
Definition 5.1. Let 0 ≤ k ≤ ⌊ n / 2 ⌋ 0\le k\le\lfloor n/2\rfloor 0 ≤ k ≤ ⌊ n /2 ⌋ G G G n n n k k k
P k ( G ) = P k ( K n ) . P_k(G)=P_k(K_n). P k ( G ) = P k ( K n ) . Problem 5.2. Characterize the k k k k k k k ≤ ν ( G ) k\le\nu(G) k ≤ ν ( G )
Note that this question can be restated as a question about the Specht generators Δ T \Delta_T Δ T S ( n − k , k ) S^{(n-k,k)} S ( n − k , k ) k k k G G G [30 ] records the linear dependences among the classical Specht generators of a given Specht module S λ S^\lambda S λ
The elementary Garnir relations
The elementary Garnir relations already give useful information. For any two vertices i i i j j j p i j = x i − x j p_{ij}=x_i-x_j p ij = x i − x j p j i = − p i j p_{ji}=-p_{ij} p j i = − p ij
Lemma 5.3 (Elementary Garnir relations). Let N N N G G G a , b , c , d a,b,c,d a , b , c , d
p N ( p a b + p b c + p c a ) = 0 , (14) p_N(p_{ab}+p_{bc}+p_{ca})=0, \tag*{(14)} p N ( p ab + p b c + p c a ) = 0 , (14) p N ( p a b p c d − p a c p b d + p a d p b c ) = 0. (15) p_N(p_{ab}p_{cd}-p_{ac}p_{bd}+p_{ad}p_{bc})=0. \tag*{(15)} p N ( p ab p c d − p a c p b d + p a d p b c ) = 0. (15) Proof. Both identities follow by expanding p i j = x i − x j p_{ij}=x_i-x_j p ij = x i − x j
When the vertices a , b , c , d a,b,c,d a , b , c , d Lemma 5.3 are distinct and are not incident to any edge of N N N (14) and (15) are linear relations among matching generators of P ∣ N ∣ + 1 ( K n ) P_{|N|+1}(K_n) P ∣ N ∣ + 1 ( K n ) P ∣ N ∣ + 2 ( K n ) P_{|N|+2}(K_n) P ∣ N ∣ + 2 ( K n )
k k k k k k The first general obstruction is connectivity. We say that G G G k k k G G G k k k G − S G-S G − S S ⊂ V S \subset V S ⊂ V ∣ S ∣ < k |S|<k ∣ S ∣ < k G G G 2 2 2
Proposition 5.4 (Connectivity obstruction). Let 1 ≤ k ≤ ⌊ n / 2 ⌋ 1 \le k \le\lfloor n/2 \rfloor 1 ≤ k ≤ ⌊ n /2 ⌋ G G G k k k G G G k k k
Proof. Suppose that S ⊂ V S \subset V S ⊂ V s < k s<k s < k G − S G-S G − S C 1 , … , C m C_1,\ldots,C_m C 1 , … , C m R = k [ x v : v ∈ V ] R=\mathbb{k}[x_v:v\in V] R = k [ x v : v ∈ V ]
J = ( x u − x v : u , v ∈ C i for some i ) . J=(x_u-x_v:u,v\in C_i\text{ for some }i). J = ( x u − x v : u , v ∈ C i for some i ) . The quotient R / J R/J R / J C i C_i C i S S S p u v p_{uv} p uv J J J u u u v v v C i C_i C i
Every k k k G G G s s s S S S C i C_i C i
p M ∈ J k − s for each M ∈ Match k ( G ) . (16) p_M\in J^{k-s}\qquad\text{for each }M\in\operatorname{Match}_k(G). \tag*{(16)} p M ∈ J k − s for each M ∈ Match k ( G ) . (16) Thus P k ( G ) ⊆ J k − s P_k(G)\subseteq J^{k-s} P k ( G ) ⊆ J k − s
On the other hand, choose vertices c 1 ∈ C 1 c_1\in C_1 c 1 ∈ C 1 c 2 ∈ C 2 c_2\in C_2 c 2 ∈ C 2 n ≥ 2 k n\ge2k n ≥ 2 k s < k s<k s < k s ≤ n − s − 2 s\le n-s-2 s ≤ n − s − 2 S S S S S S S ∪ { c 1 , c 2 } S\cup\{c_1,c_2\} S ∪ { c 1 , c 2 } c 1 c 2 c_1c_2 c 1 c 2 s + 1 s+1 s + 1 K n K_n K n x i − x j x_i-x_j x i − x j J J J k k k Q Q Q K n K_n K n p Q ∉ J k − s p_Q\notin J^{k-s} p Q ∈ / J k − s
Choose one vertex c i ∈ C i c_i\in C_i c i ∈ C i
z i : = x c i , y u : = x u − x c i ( u ∈ C i ∖ { c i } ) , z_i:=x_{c_i},\qquad y_u:=x_u-x_{c_i}\quad(u\in C_i\setminus\{c_i\}), z i := x c i , y u := x u − x c i ( u ∈ C i ∖ { c i }) , together with the variables x s x_s x s s ∈ S s\in S s ∈ S
R = k [ z 1 , … , z m , x s ( s ∈ S ) , y u ] , J = ( y u ) . R=\mathbb{k}[z_1,\ldots,z_m,x_s\ (s\in S),y_u],\qquad J=(y_u). R = k [ z 1 , … , z m , x s ( s ∈ S ) , y u ] , J = ( y u ) . Introduce an auxiliary variable t t t k \mathbb{k} k σ t : R → R [ t ] \sigma_t:R\to R[t] σ t : R → R [ t ] z i z_i z i x s x_s x s y u y_u y u t y u ty_u t y u f ∈ J d f\in J^d f ∈ J d σ t ( f ) \sigma_t(f) σ t ( f ) t d t^d t d
For a linear factor p u v = x u − x v p_{uv}=x_u-x_v p uv = x u − x v σ t ( p u v ) \sigma_t(p_{uv}) σ t ( p uv ) t t t u u u v v v C i C_i C i t t t t = 0 t=0 t = 0 z i z_i z i x s x_s x s t t t J J J
The matching Q Q Q s + 1 s+1 s + 1 J J J k − s − 1 k-s-1 k − s − 1 J J J σ t ( p Q ) \sigma_t(p_Q) σ t ( p Q ) t k − s t^{k-s} t k − s
p Q ∉ J k − s . p_Q\notin J^{k-s}. p Q ∈ / J k − s . Thus, P k ( K n ) ⊈ J k − s P_k(K_n)\not\subseteq J^{k-s} P k ( K n ) ⊆ J k − s p Q ∈ P k ( K n ) p_Q\in P_k(K_n) p Q ∈ P k ( K n ) P k ( G ) ⊆ J k − s P_k(G)\subseteq J^{k-s} P k ( G ) ⊆ J k − s P k ( G ) ≠ P k ( K n ) P_k(G)\ne P_k(K_n) P k ( G ) = P k ( K n ) G G G k k k
(The above argument using σ t \sigma_t σ t
For k ≥ 3 k \ge3 k ≥ 3 k k k
Example 5.5. Let G G G 3 3 3
dim P 3 ( G ) ≤ 4 < 5 = ( 6 3 ) − ( 6 2 ) = dim P 3 ( K 6 ) , \dim P_3(G) \le4 < 5 = \binom{6}{3} - \binom{6}{2} = \dim P_3(K_6), dim P 3 ( G ) ≤ 4 < 5 = ( 3 6 ) − ( 2 6 ) = dim P 3 ( K 6 ) , so G G G 3 3 3
2-connectivity implies 2-saturation
In degree 2 the connectivity obstruction is sharp. To prove this, we need some lemmas:
Lemma 5.6 (Two-row branching sequence). Let V V V ∣ V ∣ ≥ 4 |V| \ge4 ∣ V ∣ ≥ 4 v ∈ V v \in V v ∈ V V ′ : = V ∖ { v } V' := V \setminus\{v\} V ′ := V ∖ { v } P 2 ( K V ) P_2(K_V) P 2 ( K V ) x v x_v x v x v x_v x v [ x v ] : P 2 ( K V ) → P 1 ( K V ′ ) [x_v] : P_2(K_V) \to P_1(K_{V'}) [ x v ] : P 2 ( K V ) → P 1 ( K V ′ )
0 ⟶ P 2 ( K V ′ ) ⟶ P 2 ( K V ) → [ x v ] P 1 ( K V ′ ) ⟶ 0 (17) 0 \longrightarrow P_2(K_{V'}) \longrightarrow P_2(K_V) \xrightarrow{[x_v]} P_1(K_{V'}) \longrightarrow0 \tag*{(17)} 0 ⟶ P 2 ( K V ′ ) ⟶ P 2 ( K V ) [ x v ] P 1 ( K V ′ ) ⟶ 0 (17) where the first (nonzero) map is the evident inclusion.
Proof. The first map is injective, and its image lies in the kernel of the last map. The last map is surjective: for distinct c , d ∈ V ′ c,d \in V' c , d ∈ V ′ a ∈ V ′ ∖ { c , d } a \in V' \setminus\{c,d\} a ∈ V ′ ∖ { c , d }
[ x v ] ( p v a p c d ) = p c d . [x_v](p_{va}p_{cd}) = p_{cd}. [ x v ] ( p v a p c d ) = p c d . The dimension formula in Theorem 4.1 gives
dim P 2 ( K V ) − dim P 2 ( K V ′ ) = ∣ V ∣ − 2 = dim P 1 ( K V ′ ) , \dim P_2(K_V) - \dim P_2(K_{V'}) = |V| - 2 = \dim P_1(K_{V'}), dim P 2 ( K V ) − dim P 2 ( K V ′ ) = ∣ V ∣ − 2 = dim P 1 ( K V ′ ) , so that dim P 2 ( K V ) = dim P 2 ( K V ′ ) + dim P 1 ( K V ′ ) \dim P_2(K_V) = \dim P_2(K_{V'}) + \dim P_1(K_{V'}) dim P 2 ( K V ) = dim P 2 ( K V ′ ) + dim P 1 ( K V ′ )
0 ⟶ A → f B → g C ⟶ 0 0 \longrightarrow A \xrightarrow{f} B \xrightarrow{g} C \longrightarrow0 0 ⟶ A f B g C ⟶ 0 is a complex of finite-dimensional vector spaces such that f f f g g g dim B = dim A + dim C \dim B = \dim A + \dim C dim B = dim A + dim C
Lemma 5.7 (A degree-two vertex). Every finite 2-connected graph contains a spanning subgraph that is edge-minimal subject to being 2-connected. Every such edge-minimal subgraph has a vertex of degree 2.
Proof. The first assertion follows simply by deleting edges as long as 2-connectivity is preserved. For the second we use the standard ear characterization of 2-connected graphs; see [20 Theorem 25.4] . Let R 1 , … , R q R_1, \ldots, R_q R 1 , … , R q H H H H H H R q R_q R q R q R_q R q R q R_q R q H H H
:::
Lemma 5.8 (Suppressing a degree-two vertex). Let H H H 2 2 2 ∣ V ( H ) ∣ ≥ 4 |V(H)| \ge4 ∣ V ( H ) ∣ ≥ 4 v ∈ V ( H ) v \in V(H) v ∈ V ( H ) 2 2 2 a , b a,b a , b V ′ : = V ( H ) ∖ { v } V' := V(H) \setminus\{v\} V ′ := V ( H ) ∖ { v }
H + : = ( H − v ) + a b , H − : = H + − a b = ( H − v ) − a b . H^+ := (H-v)+ab,\qquad H^- := H^+ - ab = (H-v)-ab. H + := ( H − v ) + ab , H − := H + − ab = ( H − v ) − ab . Thus H − H^- H − H − v H-v H − v a b ab ab a b ∉ E ( H − v ) ab \notin E(H-v) ab ∈ / E ( H − v ) H − = H − v H^- = H-v H − = H − v H + H^+ H + 2 2 2 H − H^- H −
Proof. First consider H + H^+ H + w ∈ V ′ w \in V' w ∈ V ′ H + − w H^+ - w H + − w H + − w H^+ - w H + − w H − w H-w H − w v v v v v v a , b a,b a , b v v v H − w H-w H − w a a a b b b v v v H H H a − v − b a-v-b a − v − b b − v − a b-v-a b − v − a a b ab ab H + − w H^+ - w H + − w H + − w H^+ - w H + − w H + H^+ H + H + H^+ H + 2 2 2
Now consider H − H^- H − H H H 2 2 2 H − v H-v H − v a b ∉ E ( H − v ) ab \notin E(H-v) ab ∈ / E ( H − v ) a b ∈ E ( H − v ) ab \in E(H-v) ab ∈ E ( H − v ) a b ab ab H − v H-v H − v a b ab ab H − v H-v H − v A A A B B B ( H − v ) − a b (H-v)-ab ( H − v ) − ab a ∈ A a \in A a ∈ A b ∈ B b \in B b ∈ B A ≠ { a } A \ne\{a\} A = { a } H − a H-a H − a A ∖ { a } A \setminus\{a\} A ∖ { a } H − v − a b H-v-ab H − v − ab v v v a v av a v b v bv b v H − a H-a H − a A = { a } A = \{a\} A = { a } B = { b } B = \{b\} B = { b } V ( H ) = { a , b , v } V(H) = \{a,b,v\} V ( H ) = { a , b , v } ∣ V ( H ) ∣ ≥ 4 |V(H)| \ge4 ∣ V ( H ) ∣ ≥ 4 H − H^- H −
For example, if H = C 4 H = C_4 H = C 4 v v v a , b a,b a , b H H H H − v H-v H − v H + H^+ H + H − = H − v H^- = H-v H − = H − v
Theorem 5.9 (Degree-two saturation). Let G G G n ≥ 4 n \ge4 n ≥ 4
P 2 ( G ) = P 2 ( K n ) ⟺ G is 2 -connected . P_2(G) = P_2(K_n) \Longleftrightarrow G\text{ is }2\text{-connected}. P 2 ( G ) = P 2 ( K n ) ⟺ G is 2 -connected . Proof. The forward implication is Proposition 5.4 . Conversely, let G G G 2 2 2 Lemma 5.7 , a spanning edge-minimal 2 2 2 H ⊆ G H \subseteq G H ⊆ G v v v H H H a , b a,b a , b V ′ : = V ∖ { v } V' := V \setminus\{v\} V ′ := V ∖ { v }
H + = ( H − v ) + a b , H − = ( H − v ) − a b . H^+ = (H-v)+ab,\qquad H^- = (H-v)-ab. H + = ( H − v ) + ab , H − = ( H − v ) − ab . By Lemma 5.8 , H + H^+ H + 2 2 2 H − H^- H − ∣ V ′ ∣ = 3 |V'| = 3 ∣ V ′ ∣ = 3 H + = K V ′ H^+ = K_{V'} H + = K V ′ n n n
P 2 ( H + ) = P 2 ( K V ′ ) . P_2(H^+) = P_2(K_{V'}). P 2 ( H + ) = P 2 ( K V ′ ) . We want to prove that P 2 ( G ) = P 2 ( K n ) P_2(G) = P_2(K_n) P 2 ( G ) = P 2 ( K n ) P 2 ( H ) ⊆ P 2 ( G ) ⊆ P 2 ( K V ) = P 2 ( K n ) P_2(H) \subseteq P_2(G) \subseteq P_2(K_V) = P_2(K_n) P 2 ( H ) ⊆ P 2 ( G ) ⊆ P 2 ( K V ) = P 2 ( K n ) P 2 ( H ) = P 2 ( K V ′ ) P_2(H) = P_2(K_{V'}) P 2 ( H ) = P 2 ( K V ′ )
Recall the elementary linear-algebra fact that if
0 ⟶ A ⟶ B ⟶ C ⟶ 0 0 \longrightarrow A \longrightarrow B \longrightarrow C \longrightarrow0 0 ⟶ A ⟶ B ⟶ C ⟶ 0 is a short exact sequence of vector spaces, and if W ⊆ B W \subseteq B W ⊆ B A A A C C C W = B W = B W = B (17) and the subspace P 2 ( H ) P_2(H) P 2 ( H ) P 2 ( K V ) P_2(K_V) P 2 ( K V ) P 2 ( H ) P_2(H) P 2 ( H ) P 2 ( K V ′ ) P_2(K_{V'}) P 2 ( K V ′ ) P 1 ( K V ′ ) P_1(K_{V'}) P 1 ( K V ′ ) [ x v ] [x_v] [ x v ]
We start with the first claim. Since P 2 ( H + ) = P 2 ( K V ′ ) P_2(H^+) = P_2(K_{V'}) P 2 ( H + ) = P 2 ( K V ′ ) p M ∈ P 2 ( H + ) p_M \in P_2(H^+) p M ∈ P 2 ( H + ) P 2 ( H ) P_2(H) P 2 ( H ) M M M H + H^+ H + a b ∉ M ab \notin M ab ∈ / M M M M H H H p M ∈ P 2 ( H ) p_M \in P_2(H) p M ∈ P 2 ( H ) a b ∈ M ab \in M ab ∈ M c d cd c d M M M p M = p a b p c d p_M = p_{ab}p_{cd} p M = p ab p c d (14) gives
p a b p c d = ( p a v + p v b ) p c d = p a v p c d + p v b p c d , p_{ab}p_{cd} = (p_{av} + p_{vb})p_{cd} = p_{av}p_{cd} + p_{vb}p_{cd}, p ab p c d = ( p a v + p v b ) p c d = p a v p c d + p v b p c d , and both terms on the right come from 2-matchings of H H H P 2 ( H ) P_2(H) P 2 ( H )
P 2 ( K V ′ ) = P 2 ( H + ) ⊆ P 2 ( H ) . P_2(K_{V'}) = P_2(H^+) \subseteq P_2(H). P 2 ( K V ′ ) = P 2 ( H + ) ⊆ P 2 ( H ) . It remains to prove the surjection claim. For every edge c d cd c d H − H^- H − a , b a,b a , b c d cd c d c d cd c d a v av a v b v bv b v H H H x v x_v x v p c d p_{cd} p c d p c d ∈ [ x v ] P 2 ( H ) p_{cd} \in[x_v]P_2(H) p c d ∈ [ x v ] P 2 ( H )
[ x v ] P 2 ( H ) ⊇ P 1 ( H − ) = P 1 ( K V ′ ) , [x_v]P_2(H) \supseteq P_1(H^-) = P_1(K_{V'}), [ x v ] P 2 ( H ) ⊇ P 1 ( H − ) = P 1 ( K V ′ ) , where the last equality follows from the connectivity of H − H^- H − P 2 ( H ) P_2(H) P 2 ( H ) P 1 ( K V ′ ) P_1(K_{V'}) P 1 ( K V ′ ) [ x v ] [x_v] [ x v ] P 2 ( H ) = P 2 ( K V ) P_2(H) = P_2(K_V) P 2 ( H ) = P 2 ( K V ) P 2 ( G ) = P 2 ( K n ) P_2(G) = P_2(K_n) P 2 ( G ) = P 2 ( K n )
k k k k k k There is also a simple sufficient condition in every degree.
Definition 5.10. A graph G G G k k k a 1 , b 1 , … , a k , b k a_1,b_1,\ldots,a_k,b_k a 1 , b 1 , … , a k , b k Q i Q_i Q i a i a_i a i b i b_i b i 1 ≤ i ≤ k 1 \le i \le k 1 ≤ i ≤ k G G G
Proposition 5.11 (Linkedness criterion). If G G G k k k G G G k k k
Proof. Take an arbitrary k k k M = { { a 1 , b 1 } , … , { a k , b k } } M = \{\{a_1,b_1\},\ldots,\{a_k,b_k\}\} M = {{ a 1 , b 1 } , … , { a k , b k }} K n K_n K n Q i Q_i Q i G G G a i a_i a i b i b_i b i
x a i − x b i = ∑ u v ∈ E ( Q i ) ε u v ( x u − x v ) , ε u v ∈ { ± 1 } . x_{a_i} - x_{b_i} = \sum_{uv \in E(Q_i)} \varepsilon_{uv}(x_u - x_v), \qquad\varepsilon_{uv} \in\{\pm1\}. x a i − x b i = uv ∈ E ( Q i ) ∑ ε uv ( x u − x v ) , ε uv ∈ { ± 1 } . Multiplying these k k k p M p_M p M Q i Q_i Q i k k k G G G p M ∈ P k ( G ) p_M \in P_k(G) p M ∈ P k ( G ) P k ( K n ) ⊆ P k ( G ) P_k(K_n) \subseteq P_k(G) P k ( K n ) ⊆ P k ( G )
Thus, for 1 ≤ k ≤ ⌊ n / 2 ⌋ 1 \le k \le\lfloor n/2 \rfloor 1 ≤ k ≤ ⌊ n /2 ⌋
k -linked ⟹ k -saturated ⟹ k -connected . k\text{-linked} \implies k\text{-saturated} \implies k\text{-connected}. k -linked ⟹ k -saturated ⟹ k -connected . The second implication is an equivalence for k = 1 , 2 k = 1,2 k = 1 , 2 k = 3 k = 3 k = 3
Matching-complement implies k k k
The Garnir relations also settle another useful family of graphs.
Theorem 5.12 (Matching-complement saturation). Let G G G n ≥ 3 n \ge3 n ≥ 3 G ‾ \overline{G} G G G G k k k 0 ≤ k ≤ ⌊ n / 2 ⌋ 0 \le k \le\lfloor n/2 \rfloor 0 ≤ k ≤ ⌊ n /2 ⌋
Proof. Call the edges of G ‾ \overline{G} G p M ∈ P k ( G ) p_M \in P_k(G) p M ∈ P k ( G ) k k k M M M K n K_n K n M M M M M M a b ∈ M ab \in M ab ∈ M
If 2 k < n 2k < n 2 k < n c c c a c ac a c c b cb c b G G G (14) gives
p a b = p a c + p c b . p_{ab}=p_{ac}+p_{cb}. p ab = p a c + p c b . After multiplication by the factors belonging to M ∖ { a b } M \setminus\{ab\} M ∖ { ab } p M p_M p M p N p_N p N p R p_R p R N N N R R R M M M p M ∈ P k ( G ) p_M \in P_k(G) p M ∈ P k ( G )
If 2 k = n 2k = n 2 k = n n ≥ 4 n \ge4 n ≥ 4 k ≥ 2 k \ge2 k ≥ 2 c d ∈ M cd \in M c d ∈ M G ‾ \overline{G} G a c ac a c a d ad a d b c bc b c b d bd b d G G G (15) gives
p a b p c d = p a c p b d − p a d p b c . p_{ab}p_{cd}=p_{ac}p_{bd}-p_{ad}p_{bc}. p ab p c d = p a c p b d − p a d p b c . Multiplying by the remaining factors again decreases the number of forbidden edges (by 1 or by 2). Induction completes the proof. □
Corollary 5.13 (Multipartite saturation). Let r ≥ 2 r \ge2 r ≥ 2
G = K 2 , … , 2 G=K_{2,\ldots,2} G = K 2 , … , 2 be the complete r r r r r r
P k ( G ) = P k ( K 2 r ) for all 0 ≤ k ≤ r , P_k(G)=P_k(K_{2r}) \qquad\text{for all } 0 \le k \le r, P k ( G ) = P k ( K 2 r ) for all 0 ≤ k ≤ r , and therefore
Hilb ( D ( G ) , t ) = ∑ k = 0 r ( ( 2 r k ) − ( 2 r k − 1 ) ) t k . \operatorname{Hilb}(\mathcal{D}(G),t)=\sum_{k=0}^{r}\left(\binom{2r}{k}-\binom{2r}{k-1}\right)t^k. Hilb ( D ( G ) , t ) = k = 0 ∑ r ( ( k 2 r ) − ( k − 1 2 r ) ) t k . Proof. The complement of K 2 , … , 2 K_{2,\ldots,2} K 2 , … , 2 r r r Theorem 5.12 applies. The Hilbert series then follows from Theorem 4.1 . □
For r = 5 r=5 r = 5
Hilb ( D ( G ) , t ) = 1 + 9 t + 35 t 2 + 75 t 3 + 90 t 4 + 42 t 5 . \operatorname{Hilb}(\mathcal{D}(G),t)=1+9t+35t^2+75t^3+90t^4+42t^5. Hilb ( D ( G ) , t ) = 1 + 9 t + 35 t 2 + 75 t 3 + 90 t 4 + 42 t 5 . Matching-equivalent graphs
The matching numbers m k ( G ) m_k(G) m k ( G ) G G G M ( G ) \mathcal{M}(G) M ( G ) D ( G ) \mathcal{D}(G) D ( G )
Proposition 5.15 (Forests). For every graph G G G
D ( G ) = M ( G ) ⟺ G is a forest. \mathcal{D}(G)=\mathcal{M}(G)\quad\Longleftrightarrow\quad G\text{ is a forest.} D ( G ) = M ( G ) ⟺ G is a forest. Consequently, if G G G
Hilb ( D ( G ) , t ) = ∑ k ≥ 0 m k ( G ) t k . \operatorname{Hilb}(\mathcal{D}(G),t)=\sum_{k\geq0}m_k(G)t^k. Hilb ( D ( G ) , t ) = k ≥ 0 ∑ m k ( G ) t k . Proof. The degree-one part D ( G ) 1 \mathcal{D}(G)_1 D ( G ) 1 G G G M ( G ) 1 \mathcal{M}(G)_1 M ( G ) 1 u e u_e u e
dim D ( G ) 1 = ∣ V ∣ − c ( G ) , dim M ( G ) 1 = ∣ E ∣ . \dim\mathcal{D}(G)_1=|V|-c(G),\qquad\dim\mathcal{M}(G)_1=|E|. dim D ( G ) 1 = ∣ V ∣ − c ( G ) , dim M ( G ) 1 = ∣ E ∣. If G G G ∣ E ∣ = ∣ V ∣ − c ( G ) |E|=|V|-c(G) ∣ E ∣ = ∣ V ∣ − c ( G ) M ( G ) 1 \mathcal{M}(G)_1 M ( G ) 1 u e u_e u e D ( G ) \mathcal{D}(G) D ( G ) D ( G ) = M ( G ) \mathcal{D}(G)=\mathcal{M}(G) D ( G ) = M ( G ) ∣ E ∣ = ∣ V ∣ − c ( G ) |E|=|V|-c(G) ∣ E ∣ = ∣ V ∣ − c ( G ) G G G
For brevity, write
m G ( t ) : = ∑ k ≥ 0 m k ( G ) t k . m_G(t):=\sum_{k\geq0}m_k(G)t^k. m G ( t ) := k ≥ 0 ∑ m k ( G ) t k . for the matching generating polynomial of G G G m G ( t ) m_G(t) m G ( t ) G G G unicyclic if it is connected and has exactly one cycle. Equivalently, a unicyclic graph is a graph obtained by adding an edge to a tree. Thus, any unicyclic graph has equally many vertices and edges.
Theorem 5.16 (Unicyclic graphs). Let G G G unicyclic graph, let C C C F : = G − V ( C ) F:=G-V(C) F := G − V ( C ) ϵ e ∈ { ± 1 } \epsilon_e\in\{\pm1\} ϵ e ∈ { ± 1 } e ∈ C e\in C e ∈ C
∑ e ∈ C ϵ e p e = 0 , \sum_{e\in C}\epsilon_e p_e=0, e ∈ C ∑ ϵ e p e = 0 , and put
c C : = ∑ e ∈ C ϵ e u e ∈ M ( G ) . c_C:=\sum_{e\in C}\epsilon_eu_e\in\mathcal{M}(G). c C := e ∈ C ∑ ϵ e u e ∈ M ( G ) . Also set
P ( G ) : = ⨁ k ≥ 0 P k ( G ) , \mathcal{P}(G):=\bigoplus_{k\geq0}P_k(G), P ( G ) := k ≥ 0 ⨁ P k ( G ) , regarded only as a graded vector space, and let
ρ G : M ( G ) ⟶ P ( G ) , u M ⟼ p M \rho_G:\mathcal{M}(G)\longrightarrow\mathcal{P}(G),\qquad u_M\longmapsto p_M ρ G : M ( G ) ⟶ P ( G ) , u M ⟼ p M be the graded linear map defined on the matching basis of M ( G ) \mathcal{M}(G) M ( G )
0 ⟶ M ( F ) ( − 1 ) ⋅ c C ⟶ M ( G ) → ρ G P ( G ) ⟶ 0. (18) 0\longrightarrow\mathcal{M}(F)(-1)\mathbin{\cdot c_C}\longrightarrow\mathcal{M}(G)\xrightarrow{\rho_G}\mathcal{P}(G)\longrightarrow0. \tag*{(18)} 0 ⟶ M ( F ) ( − 1 ) ⋅ c C ⟶ M ( G ) ρ G P ( G ) ⟶ 0. (18) Here M ( F ) ( − 1 ) k = M ( F ) k − 1 \mathcal{M}(F)(-1)_k=\mathcal{M}(F)_{k-1} M ( F ) ( − 1 ) k = M ( F ) k − 1
Consequently, with the convention m − 1 ( F ) = 0 m_{-1}(F)=0 m − 1 ( F ) = 0
dim P k ( G ) = m k ( G ) − m k − 1 ( F ) for all k ≥ 0 , \dim P_k(G)=m_k(G)-m_{k-1}(F)\qquad\text{for all }k\geq0, dim P k ( G ) = m k ( G ) − m k − 1 ( F ) for all k ≥ 0 , or equivalently,
Hilb ( D ( G ) , t ) = m G ( t ) − t m F ( t ) . \operatorname{Hilb}(\mathcal{D}(G),t)=m_G(t)-t m_F(t). Hilb ( D ( G ) , t ) = m G ( t ) − t m F ( t ) . Proof. The first map in (18) is well defined because every edge of F F F C C C
Indeed, for any matching N N N F F F
c C u N = ∑ e ∈ C ϵ e u e u N = ∑ e ∈ C ϵ e u N ∪ { e } . c_Cu_N=\sum_{e\in C}\epsilon_eu_eu_N=\sum_{e\in C}\epsilon_eu_{N\cup\{e\}}. c C u N = e ∈ C ∑ ϵ e u e u N = e ∈ C ∑ ϵ e u N ∪ { e } . Thus, for any z = ∑ N a N u N ∈ M ( F ) z=\sum_N a_Nu_N\in\mathcal{M}(F) z = ∑ N a N u N ∈ M ( F )
c C z = ∑ N ∑ e ∈ C a N ϵ e u N ∪ { e } . c_Cz=\sum_N\sum_{e\in C}a_N\epsilon_eu_{N\cup\{e\}}. c C z = N ∑ e ∈ C ∑ a N ϵ e u N ∪ { e } . and all the matchings N ∪ { e } N\cup\{e\} N ∪ { e } u N ∪ { e } u_{N\cup\{e\}} u N ∪ { e } c C z c_Cz c C z a N ϵ e a_N\epsilon_e a N ϵ e ϵ e ≠ 0 \epsilon_e\ne0 ϵ e = 0 c C z = 0 c_Cz=0 c C z = 0 a N = 0 a_N=0 a N = 0 N N N c C c_C c C M ( F ) \mathcal{M}(F) M ( F )
The map ρ G \rho_G ρ G P ( G ) \mathcal{P}(G) P ( G ) N N N F F F
ρ G ( c C u N ) = p N ∑ e ∈ C ϵ e p e = 0. \rho_G(c_Cu_N)=p_N\sum_{e\in C}\epsilon_ep_e=0. ρ G ( c C u N ) = p N e ∈ C ∑ ϵ e p e = 0. Thus it remains only to prove exactness in the middle.
Choose an orientation of the edges and define a polynomial ring
S : = k [ y e : e ∈ E ( G ) ] . S:=\mathbf{k}[y_e:e\in E(G)]. S := k [ y e : e ∈ E ( G )] . Consider the graded k \mathbf{k} k
φ : S ⟶ k [ x v : v ∈ V ( G ) ] , y e ⟼ p e (that is, y i j ⟼ x i − x j ) . \varphi:S\longrightarrow\mathbf{k}[x_v:v\in V(G)],\qquad y_e\longmapsto p_e\qquad\text{(that is, }y_{ij}\longmapsto x_i-x_j\text{)}. φ : S ⟶ k [ x v : v ∈ V ( G )] , y e ⟼ p e (that is, y ij ⟼ x i − x j ) . The edge differences p e = x i − x j p_e=x_i-x_j p e = x i − x j G G G ∣ V ( G ) ∣ − 1 |V(G)|-1 ∣ V ( G ) ∣ − 1 G G G ∣ E ( G ) ∣ = ∣ V ( G ) ∣ |E(G)|=|V(G)| ∣ E ( G ) ∣ = ∣ V ( G ) ∣ p e = x i − x j p_e=x_i-x_j p e = x i − x j e = ( i , j ) ∈ E ( G ) e=(i,j)\in E(G) e = ( i , j ) ∈ E ( G ) ∑ e ∈ C ϵ e p e = 0 \sum_{e\in C}\epsilon_ep_e=0 ∑ e ∈ C ϵ e p e = 0 φ \varphi φ
ℓ : = ∑ e ∈ C ϵ e y e . \ell:=\sum_{e\in C}\epsilon_ey_e. ℓ := e ∈ C ∑ ϵ e y e . It follows that (19)
ker φ = ( ℓ ) . (19) \ker\varphi=(\ell). \tag*{(19)} ker φ = ( ℓ ) . (19) Indeed, extend ℓ \ell ℓ S 1 S_1 S 1 S / ( ℓ ) S/(\ell) S / ( ℓ )
For each k ≥ 0 k\ge0 k ≥ 0 k \mathbf{k} k U k U_k U k S S S
U k : = span k { y M : M ∈ Match k ( G ) } , where y M : = ∏ e ∈ M y e , U_k:=\operatorname{span}_{\mathbf{k}}\{y_M:M\in\operatorname{Match}_k(G)\},\qquad\text{where }y_M:=\prod_{e\in M}y_e, U k := span k { y M : M ∈ Match k ( G )} , where y M := e ∈ M ∏ y e , and put U : = ⨁ k ≥ 0 U k U:=\bigoplus_{k\ge0}U_k U := ⨁ k ≥ 0 U k u M ↔ y M u_M\leftrightarrow y_M u M ↔ y M M ( G ) \mathcal{M}(G) M ( G ) U U U ρ G \rho_G ρ G φ \varphi φ U U U c C c_C c C M ( G ) \mathcal{M}(G) M ( G ) ℓ \ell ℓ U U U (18) is equivalent to (20)
U ∩ ( ℓ ) = ℓ U ( F ) . (20) U\cap(\ell)=\ell U(F). \tag*{(20)} U ∩ ( ℓ ) = ℓ U ( F ) . (20) where
U ( F ) : = span k { y N : N is a matching of F } . U(F) := \operatorname{span}_{k}\{y_N : N\text{ is a matching of }F\}. U ( F ) := span k { y N : N is a matching of F } . The inclusion ℓ U ( F ) ⊆ U ∩ ( ℓ ) \ell U(F) \subseteq U \cap(\ell) ℓ U ( F ) ⊆ U ∩ ( ℓ )
f = ℓ q ∈ U . f=\ell q\in U. f = ℓ q ∈ U . Every monomial occurring in f f f y M y_M y M M M M G G G e ∈ C e\in C e ∈ C y e y_e y e ℓ \ell ℓ S S S
deg y e ( ℓ q ) = deg y e q + 1 ( q ≠ 0 ) . \deg_{y_e}(\ell q)=\deg_{y_e}q+1\qquad(q\ne0). deg y e ( ℓ q ) = deg y e q + 1 ( q = 0 ) . As deg y e f ≤ 1 \deg_{y_e}f\leq1 deg y e f ≤ 1 f f f deg y e q = 0 \deg_{y_e}q=0 deg y e q = 0 e ∈ C e\in C e ∈ C q q q y e y_e y e e ∈ C e\in C e ∈ C
Write
q = ∑ α c α y α . q=\sum_{\alpha}c_{\alpha}y^{\alpha}. q = α ∑ c α y α . Because the y α y^{\alpha} y α y e y α y_ey^{\alpha} y e y α ( e , α ) (e,\alpha) ( e , α ) e ∈ C e\in C e ∈ C
ℓ q = ∑ e ∈ C ∑ α ϵ e c α y e y α . \ell q=\sum_{e\in C}\sum_{\alpha}\epsilon_ec_{\alpha}y_ey^{\alpha}. ℓ q = e ∈ C ∑ α ∑ ϵ e c α y e y α . Since this polynomial lies in U U U c α ≠ 0 c_{\alpha}\ne0 c α = 0 y α = y N y^{\alpha}=y_N y α = y N N N N G G G N N N C C C N N N v ∈ V ( C ) v\in V(C) v ∈ V ( C ) e e e v v v y e y N y_ey_N y e y N N N N F = G − V ( C ) F=G-V(C) F = G − V ( C ) q ∈ U ( F ) q\in U(F) q ∈ U ( F ) (20) and hence the exact sequence.
Taking degree k k k (18) gives a short exact sequence
0 ⟶ M ( F ) k − 1 ⟶ M ( G ) k ⟶ P k ( G ) ⟶ 0. 0\longrightarrow\mathcal{M}(F)_{k-1}\longrightarrow\mathcal{M}(G)_k\longrightarrow P_k(G)\longrightarrow0. 0 ⟶ M ( F ) k − 1 ⟶ M ( G ) k ⟶ P k ( G ) ⟶ 0. Therefore
dim P k ( G ) = m k ( G ) − m k − 1 ( F ) . \dim P_k(G)=m_k(G)-m_{k-1}(F). dim P k ( G ) = m k ( G ) − m k − 1 ( F ) . Finally, summing over k k k dim D ( G ) k = dim P k ( G ) \dim D(G)_k=\dim P_k(G) dim D ( G ) k = dim P k ( G )
Hilb ( D ( G ) , t ) = m G ( t ) − t m F ( t ) . \operatorname{Hilb}(D(G),t)=m_G(t)-tm_F(t). Hilb ( D ( G ) , t ) = m G ( t ) − t m F ( t ) . Proposition 5.17 (Matching-equivalent counterexamples).
Proposition 5.17. (Matching-equivalent counterexamples).
(a) There are two graphs G G G H H H m k ( G ) = m k ( H ) m_k(G)=m_k(H) m k ( G ) = m k ( H ) k ≥ 0 k\geq0 k ≥ 0 Hilb ( D ( G ) , t ) ≠ Hilb ( D ( H ) , t ) \operatorname{Hilb}(D(G),t)\ne\operatorname{Hilb}(D(H),t) Hilb ( D ( G ) , t ) = Hilb ( D ( H ) , t )
(b) There are two connected graphs G G G H H H m k ( G ) = m k ( H ) m_k(G)=m_k(H) m k ( G ) = m k ( H ) k ≥ 0 k\geq0 k ≥ 0 Hilb ( D ( G ) , t ) ≠ Hilb ( D ( H ) , t ) \operatorname{Hilb}(D(G),t)\ne\operatorname{Hilb}(D(H),t) Hilb ( D ( G ) , t ) = Hilb ( D ( H ) , t ) G G G H H H
(c) There are two 2-connected graphs G G G H H H m k ( G ) = m k ( H ) m_k(G)=m_k(H) m k ( G ) = m k ( H ) k ≥ 0 k\geq0 k ≥ 0 Hilb ( D ( G ) , t ) ≠ Hilb ( D ( H ) , t ) \operatorname{Hilb}(D(G),t)\ne\operatorname{Hilb}(D(H),t) Hilb ( D ( G ) , t ) = Hilb ( D ( H ) , t ) G G G H H H
Proof. (a) Let
G 4 = K 1 , 3 , H 4 = K 3 ⊔ K 1 . G_4 = K_{1,3}, \qquad H_4 = K_3 \sqcup K_1. G 4 = K 1 , 3 , H 4 = K 3 ⊔ K 1 . Both graphs have matching numbers
( m 0 , m 1 , m 2 ) = ( 1 , 3 , 0 ) . (m_0,m_1,m_2)=(1,3,0). ( m 0 , m 1 , m 2 ) = ( 1 , 3 , 0 ) . However, G 4 G_4 G 4 H 4 H_4 H 4 Proposition 3.5 gives
Hilb ( D ( G 4 ) , t ) = 1 + 3 t , Hilb ( D ( H 4 ) , t ) = 1 + 2 t . \operatorname{Hilb}(\mathcal{D}(G_4),t)=1+3t,\qquad\operatorname{Hilb}(\mathcal{D}(H_4),t)=1+2t. Hilb ( D ( G 4 ) , t ) = 1 + 3 t , Hilb ( D ( H 4 ) , t ) = 1 + 2 t . (b) Let G 5 G_5 G 5 { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } 3 − 4 − 5 3-4-5 3 − 4 − 5 H 5 H_5 H 5 1 − 2 − 3 − 4 − 1 1-2-3-4-1 1 − 2 − 3 − 4 − 1 1 − 5 1-5 1 − 5
E ( G 5 ) = { 12 , 23 , 13 , 34 , 45 } , E ( H 5 ) = { 12 , 23 , 34 , 14 , 15 } . E(G_5)=\{12,23,13,34,45\},\qquad E(H_5)=\{12,23,34,14,15\}. E ( G 5 ) = { 12 , 23 , 13 , 34 , 45 } , E ( H 5 ) = { 12 , 23 , 34 , 14 , 15 } . Both graphs are connected, both have degree sequence ( 3 , 2 , 2 , 2 , 1 ) (3,2,2,2,1) ( 3 , 2 , 2 , 2 , 1 )
m G 5 ( t ) = m H 5 ( t ) = 1 + 5 t + 4 t 2 . m_{G_5}(t)=m_{H_5}(t)=1+5t+4t^2. m G 5 ( t ) = m H 5 ( t ) = 1 + 5 t + 4 t 2 . For G 5 G_5 G 5 45 45 45 H 5 H_5 H 5 4 4 4 5 5 5 Theorem 5.16 gives
Hilb ( D ( G 5 ) , t ) = ( 1 + 5 t + 4 t 2 ) − t ( 1 + t ) = 1 + 4 t + 3 t 2 , \operatorname{Hilb}(\mathcal{D}(G_5),t)=(1+5t+4t^2)-t(1+t)=1+4t+3t^2, Hilb ( D ( G 5 ) , t ) = ( 1 + 5 t + 4 t 2 ) − t ( 1 + t ) = 1 + 4 t + 3 t 2 , while
Hilb ( D ( H 5 ) , t ) = ( 1 + 5 t + 4 t 2 ) − t = 1 + 4 t + 4 t 2 . \operatorname{Hilb}(\mathcal{D}(H_5),t)=(1+5t+4t^2)-t=1+4t+4t^2. Hilb ( D ( H 5 ) , t ) = ( 1 + 5 t + 4 t 2 ) − t = 1 + 4 t + 4 t 2 . Thus the two graphs have the same matching data and even the same degree sequence, but different Dunkl Hilbert series.
(c) Given a graph X X X n n n X ∗ X^* X ∗ X X X k k k X ∗ X^* X ∗ ( k − 1 ) (k-1) ( k − 1 ) X X X n − 2 k + 2 n-2k+2 n − 2 k + 2
m k ( X ∗ ) = m k ( X ) + ( n − 2 k + 2 ) m k − 1 ( X ) . (21) m_k(X^*)=m_k(X)+(n-2k+2)m_{k-1}(X). \tag*{(21)} m k ( X ∗ ) = m k ( X ) + ( n − 2 k + 2 ) m k − 1 ( X ) . (21) In particular, coning preserves equality of matching numbers.
Let G 5 , H 5 G_5,H_5 G 5 , H 5 6 6 6 G 5 ∗ , H 5 ∗ G_5^*,H_5^* G 5 ∗ , H 5 ∗ 2 2 2 ( 5 , 4 , 3 , 3 , 3 , 2 ) (5,4,3,3,3,2) ( 5 , 4 , 3 , 3 , 3 , 2 ) (21) have matching numbers
( m 0 , m 1 , m 2 , m 3 ) = ( 1 , 10 , 19 , 4 ) . (m_0,m_1,m_2,m_3)=(1,10,19,4). ( m 0 , m 1 , m 2 , m 3 ) = ( 1 , 10 , 19 , 4 ) . By Theorem 5.9 , both have dim P 1 = 5 \dim P_1=5 dim P 1 = 5 dim P 2 = 9 \dim P_2=9 dim P 2 = 9
The four perfect matchings of G 5 ∗ G_5^* G 5 ∗
p 12 p 34 p 56 , p 12 p 36 p 45 , p 13 p 26 p 45 , p 16 p 23 p 45 . p_{12}p_{34}p_{56},\qquad p_{12}p_{36}p_{45},\qquad p_{13}p_{26}p_{45},\qquad p_{16}p_{23}p_{45}. p 12 p 34 p 56 , p 12 p 36 p 45 , p 13 p 26 p 45 , p 16 p 23 p 45 . The last three satisfy the four-vertex Garnir relation
p 12 p 36 p 45 − p 13 p 26 p 45 + p 16 p 23 p 45 = 0 , p_{12}p_{36}p_{45}-p_{13}p_{26}p_{45}+p_{16}p_{23}p_{45}=0, p 12 p 36 p 45 − p 13 p 26 p 45 + p 16 p 23 p 45 = 0 , while the first polynomial is independent of their span (for instance its x 1 x 3 x 6 x_1x_3x_6 x 1 x 3 x 6 dim P 3 ( G 5 ∗ ) = 3 \dim P_3(G_5^*)=3 dim P 3 ( G 5 ∗ ) = 3
The four perfect matchings of H 5 ∗ H_5^* H 5 ∗
p 12 p 34 p 56 , p 14 p 23 p 56 , p 15 p 23 p 46 , p 15 p 26 p 34 . p_{12}p_{34}p_{56},\quad p_{14}p_{23}p_{56},\quad p_{15}p_{23}p_{46},\quad p_{15}p_{26}p_{34}. p 12 p 34 p 56 , p 14 p 23 p 56 , p 15 p 23 p 46 , p 15 p 26 p 34 . They are independent: the monomials x 1 x 4 x 5 x_1x_4x_5 x 1 x 4 x 5 x 1 x 2 x 5 x_1x_2x_5 x 1 x 2 x 5 x 1 x 3 x 4 x_1x_3x_4 x 1 x 3 x 4 x 1 x 2 x 3 x_1x_2x_3 x 1 x 2 x 3 dim P 3 ( H 5 ∗ ) = 4 \dim P_3(H_5^*)=4 dim P 3 ( H 5 ∗ ) = 4
Hilb ( D ( G 5 ∗ ) , t ) = 1 + 5 t + 9 t 2 + 3 t 3 , Hilb ( D ( H 5 ∗ ) , t ) = 1 + 5 t + 9 t 2 + 4 t 3 . \operatorname{Hilb}(\mathcal{D}(G_5^*),t)=1+5t+9t^2+3t^3,\qquad\operatorname{Hilb}(\mathcal{D}(H_5^*),t)=1+5t+9t^2+4t^3. Hilb ( D ( G 5 ∗ ) , t ) = 1 + 5 t + 9 t 2 + 3 t 3 , Hilb ( D ( H 5 ∗ ) , t ) = 1 + 5 t + 9 t 2 + 4 t 3 . Problems
Problem 5.19. Describe the kernel
I G = ker ( k [ z v : v ∈ V ] ( ∑ v ∈ C z v : C a component ) ⟶ D ( G ) ) . I_G=\ker\left(\frac{\mathbb{k}[z_v:v\in V]}{\left(\sum_{v\in C}z_v:C\text{ a component}\right)}\longrightarrow\mathcal{D}(G)\right). I G = ker ( ( ∑ v ∈ C z v : C a component ) k [ z v : v ∈ V ] ⟶ D ( G ) ) . It contains z v 2 z_v^2 z v 2 v v v
Problem 5.20. Find deletion recurrences for dim P k ( G ) \dim P_k(G) dim P k ( G ) (say, for k = Q k=\mathbb{Q} k = Q ). Since matchings depend on vertex-disjointness, vertex deletion and deletion of the closed edge neighborhood are more natural here than ordinary matroid deletion–contraction.
The results on saturation proved above leave a gap for k ≥ 3 k\geq3 k ≥ 3
k -linked ⟹ k -saturated ⟹ k -connected . k\text{-linked}\Longrightarrow k\text{-saturated}\Longrightarrow k\text{-connected}. k -linked ⟹ k -saturated ⟹ k -connected . That is, we have a necessary combinatorial condition and a sufficient combinatorial condition for a graph to be k k k k ≤ 2 k\leq2 k ≤ 2
Problem 5.21. Is there such a condition, or is it too much to ask for?
Log-concavity conjectures
Throughout this section, assume that k \mathbb{k} k G = ( V , E ) G=(V,E) G = ( V , E )
H G ( t ) : = Hilb ( D ( G ) , t ) = ∑ k = 0 ν ( G ) h k ( G ) t k , r ( G ) : = ∣ V ∣ − c ( G ) , H_G(t):=\operatorname{Hilb}(\mathcal{D}(G),t)=\sum_{k=0}^{\nu(G)}h_k(G)t^k,\qquad r(G):=|V|-c(G), H G ( t ) := Hilb ( D ( G ) , t ) = k = 0 ∑ ν ( G ) h k ( G ) t k , r ( G ) := ∣ V ∣ − c ( G ) , where ν ( G ) \nu(G) ν ( G ) G G G c ( G ) c(G) c ( G ) h k ( G ) = 0 h_k(G)=0 h k ( G ) = 0 k > ν ( G ) k>\nu(G) k > ν ( G ) Theorem 3.2 , we have h k ( G ) = dim P k ( G ) h_k(G)=\dim P_k(G) h k ( G ) = dim P k ( G ) k ≥ 0 k\geq0 k ≥ 0 h 0 ( G ) = 1 h_0(G)=1 h 0 ( G ) = 1 h 1 ( G ) = r ( G ) h_1(G)=r(G) h 1 ( G ) = r ( G ) h k ( G ) > 0 h_k(G)>0 h k ( G ) > 0 0 ≤ k ≤ ν ( G ) 0\leq k\leq\nu(G) 0 ≤ k ≤ ν ( G ) k k k p M ∈ P k ( G ) p_M\in P_k(G) p M ∈ P k ( G )
Conjecture 6.1 (Log-concavity). For every finite simple graph G G G D ( G ) \mathcal{D}(G) D ( G )
h k ( G ) 2 ≥ h k − 1 ( G ) h k + 1 ( G ) for 1 ≤ k < ν ( G ) . h_k(G)^2 \ge h_{k-1}(G)h_{k+1}(G) \qquad\text{for } 1 \le k < \nu(G). h k ( G ) 2 ≥ h k − 1 ( G ) h k + 1 ( G ) for 1 ≤ k < ν ( G ) . Since the Hilbert function has no internal zeros, this conjecture would also imply its unimodality. A stronger version uses r ( G ) r(G) r ( G )
Conjecture 6.2 (Ultra-log-concavity). For every finite simple graph G G G
( h k ( G ) ( r ( G ) k ) ) k = 0 ν ( G ) \left(\frac{h_k(G)}{\binom{r(G)}{k}}\right)_{k=0}^{\nu(G)} ( ( k r ( G ) ) h k ( G ) ) k = 0 ν ( G ) is log-concave. Equivalently, writing r = r ( G ) r=r(G) r = r ( G )
k ( r − k ) h k ( G ) 2 ≥ ( k + 1 ) ( r − k + 1 ) h k − 1 ( G ) h k + 1 ( G ) for 1 ≤ k < ν ( G ) . k(r-k)h_k(G)^2 \ge(k+1)(r-k+1)h_{k-1}(G)h_{k+1}(G) \qquad\text{for } 1 \le k < \nu(G). k ( r − k ) h k ( G ) 2 ≥ ( k + 1 ) ( r − k + 1 ) h k − 1 ( G ) h k + 1 ( G ) for 1 ≤ k < ν ( G ) . The parameter r ( G ) r(G) r ( G ) r ( G ) r(G) r ( G ) D ( G ) \mathcal{D}(G) D ( G ) (1) . Thus D ( G ) \mathcal{D}(G) D ( G )
k [ z 1 , … , z r ] / ( z 1 2 , … , z r 2 ) . \mathbb{k}[z_1,\ldots,z_r]/(z_1^2,\ldots,z_r^2). k [ z 1 , … , z r ] / ( z 1 2 , … , z r 2 ) . In particular, h k ( G ) ≤ ( r k ) h_k(G) \le\binom{r}{k} h k ( G ) ≤ ( k r )
( k + 1 ) h k + 1 ( G ) ≤ ( r − k ) h k ( G ) for 0 ≤ k < r . (k+1)h_{k+1}(G) \le(r-k)h_k(G) \qquad\text{for } 0 \le k < r. ( k + 1 ) h k + 1 ( G ) ≤ ( r − k ) h k ( G ) for 0 ≤ k < r . Hence the normalized sequence in Conjecture 6.2 is already nonincreasing; the conjecture asks for its log-concavity as well.
The choice of normalization matters. By Theorem 4.1 ,
H K 5 ( t ) = 1 + 4 t + 5 t 2 . H_{K_5}(t)=1+4t+5t^2. H K 5 ( t ) = 1 + 4 t + 5 t 2 . Normalizing its coefficients by ( ν ( K 5 ) k ) = ( 2 k ) \binom{\nu(K_5)}{k}=\binom{2}{k} ( k ν ( K 5 ) ) = ( k 2 ) ( 1 , 2 , 5 ) (1,2,5) ( 1 , 2 , 5 ) ( r ( K 5 ) k ) = ( 4 k ) \binom{r(K_5)}{k}=\binom{4}{k} ( k r ( K 5 ) ) = ( k 4 ) ( 1 , 1 , 5 / 6 ) (1,1,5/6) ( 1 , 1 , 5/6 ) H G ( t ) H_G(t) H G ( t ) Conjectures 6.1 and 6.2 for all simple graphs on at most seven vertices, up to isomorphism.
There is also a representation-theoretic strengthening of Conjecture 6.1 . The group Γ = Aut ( G ) \Gamma=\operatorname{Aut}(G) Γ = Aut ( G ) k [ x v : v ∈ V ] \mathbb{k}[x_v:v\in V] k [ x v : v ∈ V ] σ ( x v ) = x σ ( v ) \sigma(x_v)=x_{\sigma(v)} σ ( x v ) = x σ ( v ) P k ( G ) P_k(G) P k ( G ) p M p_M p M ± p σ ( M ) \pm p_{\sigma(M)} ± p σ ( M ) k \mathbb{k} k
Conjecture 6.3 (Strong equivariant log-concavity). For every finite simple graph G G G and all integers 1 ≤ i ≤ j < ν ( G ) 1 \le i \le j < \nu(G) 1 ≤ i ≤ j < ν ( G ) there exists an Aut ( G ) \operatorname{Aut}(G) Aut ( G )
P i − 1 ( G ) ⊗ P j + 1 ( G ) ↪ P i ( G ) ⊗ P j ( G ) . P_{i-1}(G) \otimes P_{j+1}(G) \hookrightarrow P_i(G) \otimes P_j(G). P i − 1 ( G ) ⊗ P j + 1 ( G ) ↪ P i ( G ) ⊗ P j ( G ) . Taking dimensions and setting i = j i=j i = j Conjecture 6.1 . Li’s theorem [19 ] proves the analogous statement for the permutation representations on matchings. It does not immediately imply the conjecture above: the matching products have orientation signs under graph automorphisms and can satisfy linear relations, and an injection before passing to a quotient need not descend to an injection afterwards.
For G = K n G=K_n G = K n Theorem 4.1 identifies the conjectured injection with an S n S_n S n
S^{(n-i+1,i-1)}\otimes S^{(n-j-1,j+1)}\lhook\joinrel\longrightarrow S^{(n-i,i)}\otimes S^{(n-j,j)}\qquad\left(1\le i\le j<\left\lfloor\frac{n}{2}\right\rfloor\right).
Here a zero second part is omitted. Equivalently, the symmetric function
s ( n − i , i ) ∗ s ( n − j , j ) − s ( n − i + 1 , i − 1 ) ∗ s ( n − j − 1 , j + 1 ) s_{(n-i,i)}*s_{(n-j,j)}-s_{(n-i+1,i-1)}*s_{(n-j-1,j+1)} s ( n − i , i ) ∗ s ( n − j , j ) − s ( n − i + 1 , i − 1 ) ∗ s ( n − j − 1 , j + 1 ) should be Schur-positive, with ∗ * ∗ i , j i,j i , j n n n [14 Theorem 5.4] . The conjecture asks for every admissible n n n
Appendix A. Cut quotients and zonotopal algebras: a comparison
In this section, we leave the matching algebra M ( G ) \mathcal{M}(G) M ( G ) k [ u e : e ∈ E ] \mathbb{k}[u_e:e\in E] k [ u e : e ∈ E ] [24 ] (sometimes implicitly), so we keep our proofs short.
Assume that the field k \mathbb{k} k 0 0 0 square-zero edge algebra
Φ ^ G : = k [ u e : e ∈ E ] / ( u e 2 : e ∈ E ) , \widehat{\Phi}_G:=\mathbb{k}[u_e:e\in E]/(u_e^2:e\in E), Φ G := k [ u e : e ∈ E ] / ( u e 2 : e ∈ E ) , which is larger than M ( G ) \mathcal{M}(G) M ( G ) θ v \theta_v θ v
C G e x : = k [ θ v : v ∈ V ] ⊆ Φ ^ G , C_G^{\mathrm{ex}}:=\mathbb{k}[\theta_v:v\in V]\subseteq\widehat{\Phi}_G, C G ex := k [ θ v : v ∈ V ] ⊆ Φ G , which is known as the external graphical zonotopal algebra (the forest version of the Postnikov–Shapiro algebra); see [24 §11] , as well as the zonotopal framework in [1 , 15 ] .
We shall next see what happens when we impose further monomial relations coming from edge cuts. For a nonempty proper subset S ⊂ V S\subset V S ⊂ V
δ ( S ) : = { e ∈ E : ∣ e ∩ S ∣ = 1 } , d S : = ∣ δ ( S ) ∣ , η S : = ∏ e ∈ δ ( S ) u e . \delta(S):=\{e\in E:|e\cap S|=1\},\qquad d_S:=|\delta(S)|,\qquad\eta_S:=\prod_{e\in\delta(S)}u_e. δ ( S ) := { e ∈ E : ∣ e ∩ S ∣ = 1 } , d S := ∣ δ ( S ) ∣ , η S := e ∈ δ ( S ) ∏ u e . Because edges internal to S S S
Θ S : = ∑ v ∈ S θ v = ∑ e ∈ δ ( S ) ε S , e u e , ε S , e ∈ { ± 1 } . (22) \Theta_S:=\sum_{v\in S}\theta_v=\sum_{e\in\delta(S)}\varepsilon_{S,e}u_e,\qquad\varepsilon_{S,e}\in\{\pm1\}. \tag*{(22)} Θ S := v ∈ S ∑ θ v = e ∈ δ ( S ) ∑ ε S , e u e , ε S , e ∈ { ± 1 } . (22) Since the u e u_e u e d S d_S d S Θ S d S \Theta_S^{d_S} Θ S d S e ∈ δ ( S ) e\in\delta(S) e ∈ δ ( S )
Θ S d S = d S ! ( ∏ e ∈ δ ( S ) ε S , e ) η S = ± d S ! η S . (23) \Theta_S^{d_S}=d_S!\left(\prod_{e\in\delta(S)}\varepsilon_{S,e}\right)\eta_S=\pm d_S!\eta_S. \tag*{(23)} Θ S d S = d S ! e ∈ δ ( S ) ∏ ε S , e η S = ± d S ! η S . (23) In characteristic zero this shows, in particular, that every cut monomial η S \eta_S η S C G e x C_G^{\mathrm{ex}} C G ex
The relation with the usual external and central power ideals makes the next quotient transparent. Put
R V : = k [ z v : v ∈ V ] / ( ∑ v ∈ V z v ) , ℓ S : = ∑ v ∈ S z v . R_V := \mathbb{k}[z_v : v \in V]\Big/\left(\sum_{v\in V}z_v\right), \qquad\ell_S := \sum_{v\in S}z_v. R V := k [ z v : v ∈ V ] / ( v ∈ V ∑ z v ) , ℓ S := v ∈ S ∑ z v . The standard graphical power-ideal presentations ([24 Theorem 11.1 and Corollary 10.5] ) are
C G e x ≅ R V / ( ℓ S d S + 1 : ∅ ≠ S ⊊ V ) (24) \mathcal{C}^{\mathrm{ex}}_G \cong R_V/\left(\ell_S^{d_S+1} : \varnothing\ne S \subsetneq V\right) \tag*{(24)} C G ex ≅ R V / ( ℓ S d S + 1 : ∅ = S ⊊ V ) (24) C G c e n t r a l ≅ R V / ( ℓ S d S : ∅ ≠ S ⊊ V ) . (25) \mathcal{C}^{\mathrm{central}}_G \cong R_V/\left(\ell_S^{d_S} : \varnothing\ne S \subsetneq V\right). \tag*{(25)} C G central ≅ R V / ( ℓ S d S : ∅ = S ⊊ V ) . (25) Here z v z_v z v θ v \theta_v θ v [24 Secs. 9 and 11] and [1 , 15 ] .
Proposition A.1 (The cut quotient inside the incidence-sum algebra). For a connected graph G = ( V , E ) G=(V,E) G = ( V , E )
C G e x / ( η S : ∅ ≠ S ⊊ V ) ≅ C G c e n t r a l . \mathcal{C}^{\mathrm{ex}}_G/(\eta_S : \varnothing\ne S \subsetneq V) \cong\mathcal{C}^{\mathrm{central}}_G. C G ex / ( η S : ∅ = S ⊊ V ) ≅ C G central . Consequently, if m = ∣ E ∣ m=|E| m = ∣ E ∣ r = ∣ V ∣ − 1 r=|V|-1 r = ∣ V ∣ − 1
Hilb ( C G e x / ( η S ) , t ) = Hilb ( C G c e n t r a l , t ) = t m − r T G ( 1 , t − 1 ) , \operatorname{Hilb}\left(\mathcal{C}^{\mathrm{ex}}_G/(\eta_S),t\right)=\operatorname{Hilb}\left(\mathcal{C}^{\mathrm{central}}_G,t\right)=t^{m-r}T_G(1,t^{-1}), Hilb ( C G ex / ( η S ) , t ) = Hilb ( C G central , t ) = t m − r T G ( 1 , t − 1 ) , where T G T_G T G G G G [12 ] ).
Proof. Under the presentation (24) , the element ℓ S d S \ell_S^{d_S} ℓ S d S (23) , to a nonzero scalar multiple of η S \eta_S η S C G e x \mathcal{C}^{\mathrm{ex}}_G C G ex η S \eta_S η S ℓ S d S = 0 \ell_S^{d_S}=0 ℓ S d S = 0 (25) . The Hilbert-series formula is the standard central zonotopal specialization of the Tutte polynomial [1 , 15 ] ; e.g., combine [24 Theorem 3.3 or Theorem 9.1] with [12 Theorem 3.12] . □
There is a second quotient by the same cut monomials η S \eta_S η S whole square-zero edge algebra rather than only on its incidence-sum subalgebra. This is larger, and it has an elementary basis. Let
I c u t : = ( η S : ∅ ≠ S ⊊ V ) ⊆ Φ ^ G . I_{\mathrm{cut}} := (\eta_S : \varnothing\ne S \subsetneq V) \subseteq\widehat{\Phi}_G. I cut := ( η S : ∅ = S ⊊ V ) ⊆ Φ G . For F ⊆ E F \subseteq E F ⊆ E u F : = ∏ e ∈ F u e u_F := \prod_{e\in F}u_e u F := ∏ e ∈ F u e
Proposition A.2 (The ambient cut quotient). For connected G G G
{ u F : G ∖ F is connected } \{u_F : G\setminus F\ \text{is connected}\} { u F : G ∖ F is connected } is a basis of Φ ^ G / I c u t \widehat{\Phi}_G/I_{\mathrm{cut}} Φ G / I cut
Hilb ( Φ ^ G / I c u t , t ) = ∑ H ⊆ G ; H c o n n e c t e d s p a n n i n g t m − ∣ H ∣ \operatorname{Hilb}(\widehat{\Phi}_G/I_{\mathrm{cut}},t)
=
\sum_{\substack{H\subseteq G;\\ H\ \mathrm{connected\ spanning}}} t^{m-|H|} Hilb ( Φ G / I cut , t ) = H ⊆ G ; H connected spanning ∑ t m − ∣ H ∣ = t m − r T G ( 1 , 1 + t − 1 ) . = t^{m-r}T_G(1,1+t^{-1}). = t m − r T G ( 1 , 1 + t − 1 ) . Proof. The squarefree monomials u F u_F u F Φ ^ G \widehat{\Phi}_G Φ G I c u t I_{\mathrm{cut}} I cut u F u_F u F η S \eta_S η S δ ( S ) ⊈ F \delta(S)\nsubseteq F δ ( S ) ⊈ F S ⊂ V S\subset V S ⊂ V F F F δ ( S ) \delta(S) δ ( S ) G ∖ F G\setminus F G ∖ F S S S V ∖ S V\setminus S V ∖ S G ∖ F G\setminus F G ∖ F
T G ( 1 , y ) = ∑ H ⊆ G ; H connected spanning ( y − 1 ) ∣ H ∣ − r T_G(1,y)=\sum_{\substack{H\subseteq G;\\ H\ \text{connected spanning}}}(y-1)^{|H|-r} T G ( 1 , y ) = H ⊆ G ; H connected spanning ∑ ( y − 1 ) ∣ H ∣ − r (see, e.g., [12 Proposition 3.10] ) and substitute y = 1 + t − 1 y=1+t^{-1} y = 1 + t − 1
Thus the same cut relations produce two different but closely related objects. They fit into the diagram
C G e x ⊆ Φ ^ G ↓ ↓ C G c e n t r a l ⊆ Φ ^ G / I c u t (26) \begin{aligned}
\mathcal{C}^{\mathrm{ex}}_G &\subseteq\widehat{\Phi}_G\\
\downarrow\quad&\quad\downarrow\\
\mathcal{C}^{\mathrm{central}}_G &\subseteq\widehat{\Phi}_G/I_{\mathrm{cut}} \tag*{(26)}
\end{aligned} C G ex ↓ C G central ⊆ Φ G ↓ ⊆ Φ G / I cut (26) (whose bottom row is injective because of [24 Corollary 10.5] 3 T G ( 1 , 1 ) T_G(1,1) T G ( 1 , 1 ) Proposition A.1 ). The lower-right algebra has total dimension T G ( 1 , 2 ) T_G(1,2) T G ( 1 , 2 ) Proposition A.2 ); its grading records the number of deleted edges. More precisely, if
R G ( p ) = ∑ H ⊆ G ; H connected spanning p ∣ H ∣ ( 1 − p ) m − ∣ H ∣ R_G(p)=\sum_{\substack{H\subseteq G;\\ H\ \text{connected spanning}}}p^{|H|}(1-p)^{m-|H|} R G ( p ) = H ⊆ G ; H connected spanning ∑ p ∣ H ∣ ( 1 − p ) m − ∣ H ∣ is the all-terminal reliability polynomial, then
Hilb ( Φ ^ G / I c u t , t ) = ( 1 + t ) m R G ( ( 1 + t ) − 1 ) . \operatorname{Hilb}(\widehat{\Phi}_G/I_{\mathrm{cut}},t)=(1+t)^mR_G((1+t)^{-1}). Hilb ( Φ G / I cut , t ) = ( 1 + t ) m R G (( 1 + t ) − 1 ) . References
DEPARTMENT OF MATHEMATICS, DREXEL UNIVERSITY, PHILADELPHIA, PA, USA
Email address: darijgrinberg@gmail.com
YANQI LAKE BEIJING INSTITUTE OF MATHEMATICAL SCIENCES AND APPLICATIONS, HUAIRou DISTRICT, BEIJING, CHINA
Email address: kirillov@bimsa.cn
DEPARTMENT OF MATHEMATICS, STOCKHOLM UNIVERSITY, STOCKHOLM, SWEDEN
Email address: shapiro@math.su.se
