Conditional Erlangen Program

Abstract

This thesis is concerned with combinatorial structures that arise in the axiomatization of notions of independence, in particular conditional independence among random variables. One of the most important historic milestones in mathematics is Felix Klein’s Erlangen Program. He initiated the classification of and the systematic study on geometries through the groups of their symmetries and suggested that each geometry can be characterized by a group of transformations and a geometry is the theory of invariants under this group of transformations. Following this idea, the systematic development of matroid-like structures is initiated by Kung under the name of the Combinatorial Erlanger Programm. From another approach Gelfand and Serganova introduced the Coxeter matroids as a generalization of matroids to all Coxeter types. Following the Erlangen Program and the Combinatorial Erlangen Program, we here aim to answer the classic question “What about other Coxeter types” for conditional independence, and call the classification and axiomatization of conditional independence structures in all Coxeter types the “Conditional Erlangen Program”. Chapter 2 provides an introduction to the theory of conditional independence struc- tures of type A. Section 2.1 reviews the background on semigraphoids and semima- troids and their geometry. In Section 2.2, after reviewing the background on Gaussians, gaussoids and the representability over fields and ordered fields, we introduce the gaussoid representations over skew fields with antiautomorphisms. We also discuss the relation of gaussoids to the orthogonality and introduce a lattice-theoretic represen- tation of a gaussoid. Section 2.3 reviews the ascending semigraphoids and gaussoids, which are CI-structures abstracting various notions of connectedness. Section 2.4 gives new axiomatizations of matroids as CI-structures and of oriented matroids as oriented conditional independence structures, which provide a strong connection of matroid theory to the theory of conditional independence. We initiate the Conditional Erlangen Program by introducing the Φ-semigraphoids and Φ-semimatroids for any root system Φ in Section 3.1, and describe them explicitly for the classical types B, C and D in Section 3.2. As an application of the Conditional Erlangen Program to the Combinatorial Erlangen Program, the axiomatizations of delta-matroids as CI-structures of type C and of orthogonal delta-matroids as CI- structures of type D are given in Section 3.3. Section 3.4 studies the geometry of the generalized permutohedra of type B or C. We write every generalized permutohedron of type B, C or D explicitly as a signed Minkowski sum of rank 1 symplectic matroid basis polytopes. In other words, we found a basis of the linear space spanned by the bisubmodular functions and describe the exchange matrix explicitly. Then we discuss the connectedness of type B or C, give an explicit volume formula for any generalized permutohedron of type B, C or D and elementary proofs for the formulas for the mixed volumes of standard simplices and rank 1 symplectic matroid independent set polytopes, and prove the various marriage theorems in transversal theory using elementary properties of mixed volumes. The maximum likelihood degree (ML-degree) of a linear concentration model repre- sented by a generic linear space, the algebraic degree of semidefinite programming (SDP-degree) are fundamental measures for the computational complexity of the statistical model and the SDP, respectively. They can be expressed in the language of enumerative geometry and generalized to types A and D. All of them are polynomial functions. The proofs boils down to show the polynomiality of Lascoux polynomials. In Chapter 4 we give explicit formulas for the degrees and the leading coefficients of the Lascoux (quasi-)polynomials of types C, A and D. As an application, we give the degree of the polynomial, the algebraic degree δ(m, n, n − s), and the leading coefficient for s = 1 explicitly in types C, A and D. This is joint work with Alessio Borz`ı, Harshit J. Motwani, Lorenzo Venturello and Martin Vodiˇcka.