Getting to the Root of the Problem: Sums of Squares for Limits of Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918253059637248 |
|---|---|
| author | Brosch, Daniel Puges, Diane |
| author_facet | Brosch, Daniel Puges, Diane |
| contents | The inducibility of a graph represents its maximum density as an induced subgraph over all possible sequences of graphs of size growing to infinity. This invariant of graphs has been extensively studied since its introduction in $1975$ by Pippenger and Golumbic. In $2017$, Czabarka, Székely and Wagner extended this notion to leaf-labeled rooted binary trees, which are objects widely studied in the field of phylogenetics. They obtain the first results and bounds for the densities and inducibilities of such trees. Following up on their work, we apply Razborov's flag algebra theory to this setting, introducing the flag algebra of rooted leaf-labeled binary trees. This framework allows us to use polynomial optimization methods, based on semidefinite programming, to efficiently obtain new upper bounds for the inducibility of trees and to improve existing ones. Additionally, we obtain the first outer approximations of profiles of trees, which represent all possible simultaneous densities of a pair of trees in a sequence of trees of growing sizes. Finally, we are able to prove the non-convexity of some of these profiles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12838 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Getting to the Root of the Problem: Sums of Squares for Limits of Trees Brosch, Daniel Puges, Diane Optimization and Control Combinatorics 05C35, 05C60, 90C22, 90C23 The inducibility of a graph represents its maximum density as an induced subgraph over all possible sequences of graphs of size growing to infinity. This invariant of graphs has been extensively studied since its introduction in $1975$ by Pippenger and Golumbic. In $2017$, Czabarka, Székely and Wagner extended this notion to leaf-labeled rooted binary trees, which are objects widely studied in the field of phylogenetics. They obtain the first results and bounds for the densities and inducibilities of such trees. Following up on their work, we apply Razborov's flag algebra theory to this setting, introducing the flag algebra of rooted leaf-labeled binary trees. This framework allows us to use polynomial optimization methods, based on semidefinite programming, to efficiently obtain new upper bounds for the inducibility of trees and to improve existing ones. Additionally, we obtain the first outer approximations of profiles of trees, which represent all possible simultaneous densities of a pair of trees in a sequence of trees of growing sizes. Finally, we are able to prove the non-convexity of some of these profiles. |
| title | Getting to the Root of the Problem: Sums of Squares for Limits of Trees |
| topic | Optimization and Control Combinatorics 05C35, 05C60, 90C22, 90C23 |
| url | https://arxiv.org/abs/2404.12838 |