Algorithmic and Combinatorial Aspects of CAT(0) Complexes
Delve into the fascinating world of CAT(0) complexes with insights on combinatorial and algorithmic aspects, exploring geodesic metric spaces, phylogenetic trees, and the unique properties of CAT(0)-spaces. Discover how researchers like Hiroshi Hirai are unraveling the mysteries of these intriguing mathematical structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Combinatorial and algorithmic aspects of CAT(0) complexes Hiroshi Hirai Department of Mathematical Informatics, Graduate School of Information Science and Technology The University of Tokyo JST PRESTO hirai@mist.i.u-tokyo.ac.jp IST Austria 15 November 2019 1
Cartan, Alexandrov, Topogonov, curvature 0 Def: CAT(0)-space (Gromov 1987) geodesic metric space (?,?) s.t. every triangle is slimmer ? ? 2 (?,?) ? ?,? = ? ?,? = ? ?,? = ? ?2 ? ?2 ? ?2 ? ? ? ? ? ? ? ?,? ? ?2 FACT: CAT(0)-space is uniquely geodesic Ex: Euclidean space ?, tree, hyperbolic space, ... 2
In this talk, I will explain some algorithmic & combinatorial results on CAT(0) spaces associated with combinatorial objects 1. The space of phylogenetic trees -- Owen-Provan algorithm computing geodesics 2. Orthoscheme complexes of (semi)lattices 3
Phylogenetic tree 0 0 ? ? ?(?,? ) ? ? ? ? ? ? ? ? ? How to measure two distinct phylogenetic trees ? Continuous: edge-length v.s. Discrete: topology of the tree
The space of phylogenetic trees Billera-Holomes-Vogtman 2001 ?: a set of taxa ? = ? ?:2? +s.t.supp ? is laminar tree ? 1.4 2.9 2.9 1.1 1.1 ? ? ? ? ? 1.4 ? ? ? ? ? Tree space ? ?:2? + supp ? is laminar}
0 0 ? {?,?} ? ? ? ?? ? ? {?,?} {?,?,?} 0 0 ? ? ? ? {?,?} ? {?,?,?} 0 ? ? ? ? ? ? ? ? 2? | 2?:laminar}, where + ? = { + + 2? is not convex. ? + The length of a path is measured in each orthant +
Cross section of the tree space on ? = ?,?,?,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ?,? inf ?(?) Distance of ?,? : ?: 0,1 ? ? 0 = ?,? 1 = ? Thm (Billera-Holmes-Vogtman 2001) (?,?) is a CAT(0) metric space ?1 ?? ?0 ? 3.0 1.0 ? ? 2.0 ? ? ? 5.0 ? ? 5 ? ? ? 4.0 1.0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =5 5 0.69 4
0 ? ? ? ? ? ? ? ? ? 0 ? 0 ?? ? ? ? ? ? ?
Gromovs Characterization (Gromov 1987) ? 2?: abstract simplicial complex on ? ? ? ? ? ? ? ?, where + ? ? ? ? ? + + Thm. [G87] ? ? is CAT(0) ?is flag ? is the family of stable sets of some graph ? Ex: { laminar families } 22[?] stable sets in the graph of the crossing relation on 2[?] 10
Owen-Provan algorithm ? = ?,? ? ? CAT(0) orthant complex ? ? + + ?:stable set of ? Find geodesic ? ? ? connecting given ?,? ? ? Thm (Owen-Provan 2011) This problem is solved by a parametric network flow. geodesic problem in tree space is solved in polytime. 11
? ? ? = ?,? , ? ? + + ?:stable set of ? Find a geodesic ? ? ? connecting given ?,? ? ? . ? supp ?,? supp ? (stable sets of ?) ? ?= ? ?[? ?] Lem: ? ? ? + we can assume ? = ? ? ? ? Lem: ? ?[? ?] = ?(? ? ? ) + we can assume ? = ? ?,? ? = ? is a bipartite graph with color classes ?,? 12
(Potentially shortest) Path ? = ? ? ? [0,1] ? ? connecting ?,? supp ? ? ? [0,1]= (? = ?0,?1, ,??= ?) sequence of stable sets ? ?4 ?1 ?3 ?2 ? ? ??+1= ?? ??+ ?? ?2 ?3 ?4 ?1 ?|?? ?|?1 ?|?2 ? ~ ?|?2 ?|?1 ?|?? ?? + ?? ?2 + ?2 ?1 + ?1 + + 13 +
?|?? ?|?1 ?|?2 ?|?2 ?|?1 ?|?? 2 ? ?=1 ?|?? + ?|?? ?(?) Lem (Owen 2011; informal) The geodesic is attained by such a path, i.e., 2 ? ?=1 ?|?? + ?|?? ? ?,? = min ? = ?0,?1, ,??= ? 14
2 ?4= ? ?3 (?,1 ?) ?2 stable set ? ( ?|? ? 2, 2 ) ?|? ? ?1 ?0= ? 2+ (1 ?) 2 max. ? ?? ?? ? ? ? ? ? ? s.t. ?:stable set in ? = (?,?;?) parametric network flow 15
Hayashi (ICALP 2018): a polynomial iterative geodesic algorithm for general CAT(0) cubical complexes, by using Owen-Provan algorithm as a subroutine. ? ? ? ? CAT(0) orthant space CAT(0) orthant space 16
Application to robotics The configuration spaces for a class of robots become CAT(0) spaces (Abram-Ghrist 2004) move 1 move 2 motion plan of minimum energy geodesic problem
Orthoscheme (named by Coxeter 1991) Def. ?-dimensional orthoscheme ?-dim. simplex of vertices ? 0,0, ,0 , 1,0, ,0 , (1,1,0, ,0), ,(1,1,1, ,1) 111 3 2 11 110 10 00 000 100 19
Orthoscheme Complex (Brady-McCammond 2012) : graded poset ? := the set of all convex combinations ? ? ? ? of elements in s.t. supp ? is chain, where each simplex is metrized by orthoschemes ?3 111 ( ?,?2) ?2 110 ?1 000 100 ?0 20
?() ? ? ? The length ?(?) of a path ?:[0,1] ?( ) is well-defined ? ?,? inf ? ? ?: ?,? path} (? ,?) is a geodesic metric space 21
What are posets to have CAT(0) orthoscheme complex ? ? Brady-McCammond 2012 22
Brady-McCammond Conjecture (Brady-McCammond 2012) 1 Noncrossing partition on 1,2, ,8 Ex. { 8,1 , 7,2,3 , 4,6 , 5 } 8 2 3 7 Noncrossing partition lattice := { noncrossing partitions } w.r.t. refinement relation 4 6 5 Conj. [BM12] : noncrossing partition lattice ? : CAT(0) Thm. [BM12] BM conjecture true braid group is CAT(0) group 23
Boolean Lattice Lem: = 2{1,2, ,?} ? 0,1? CAT(0) 24
Distributive Lattice ?( ) Birkhoff Lem: = The family of ideals in a poset (?, ) ? ? 0,1? ? ? ? ? (?,? ?:? ?)} CAT(0) c.f. order polytope [Stanley 86; Fujishige 84] 25
Modular Lattice ... ? Thm. [Chalopin-Chepoi-H-Osajda 2014] : modular lattice ? : CAT(0) Thm. [H.18] ?: is submodular ?:?( ) is convex ? ? ????(??) (? = ????? ?( )) Application to MVSP (Hamada-Hirai 2017) 26
MVSP; Maximum Vanishing Subspace Problem Input ?1,?2, ,?? ?? ?( ?: field ) Max. dim ? + dim ? s.t. ???,? = {0} ? ??,? ??vector subspace ? where ???,? ????? Block-triangularization of a matrix (Ito-Iwata-Murota 1995) Non-commutative rank (Garg et al. 2015, Ivanyos et al. 2015) Submodular optimization on the modular lattice of vector subsp. Hamada-Hirai 2017: Via ? , solve MVSP as convex optimization on CAT(0) space 27
semimodular lattice H.2019 Not CAT(0) (Hayashi 2019) modular semilattice geometric lattice supersolvable lattice median semilattice modular lattice ?? CAT(0) ?? CAT(0) noncrossing partition lattice BM conjecture partition lattice distributive lattice Boolean semilattice tree space Boolean lattice 28
Thm. [H2019] Conj [CCHO2014] : modular semilattice ? : CAT(0) principal ideal is a modular lattice ? ?,? ?,? ? ? ? ? Proof Outline: For ? , CAT(0) property Unique Geodesic Property We prove UGP in constructive way Key Fact: Owen-Provan algorithm for geodesics in tree space ?? can prove UGP (without knowing CAT(0)) We extend this argument. 29
modular lattice Reduce to: ?,? ?( ) ? ? ? ? ,? ? 2 (?,1 ?) ?,? ( ? ? 2, 2 ) ? ? 2+ 1 ? 2 max. ? ? ? ? ? s.t. (?,?) ? --- generalization of (parametric) MVSP 30
