Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering
Symmetric edge polytopes are lattice polytopes associated with finite simple graphs that are of interest in both theory and applications. We investigate the facet structure of symmetric edge polytopes for various models of random graphs. For an Erd\H{o}s-Renyi random graph, we identify a threshold p...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-12-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/9925/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849344634468171776 |
|---|---|
| author | Benjamin Braun Kaitlin Bruegge Matthew Kahle |
| author_facet | Benjamin Braun Kaitlin Bruegge Matthew Kahle |
| author_sort | Benjamin Braun |
| collection | DOAJ |
| description | Symmetric edge polytopes are lattice polytopes associated with finite simple graphs that are of interest in both theory and applications. We investigate the facet structure of symmetric edge polytopes for various models of random graphs. For an Erd\H{o}s-Renyi random graph, we identify a threshold probability at which with high probability the symmetric edge polytope shares many facet-supporting hyperplanes with that of a complete graph. We also investigate the relationship between the average local clustering, also known as the Watts-Strogatz clustering coefficient, and the number of facets for graphs with either a fixed number of edges or a fixed degree sequence. We use well-known Markov Chain Monte Carlo sampling methods to generate empirical evidence that for a fixed degree sequence, higher average local clustering in a connected graph corresponds to higher facet numbers in the associated symmetric edge polytope. |
| format | Article |
| id | doaj-art-5a1bbe8a0dba4dfa9671614aa91eb1c0 |
| institution | Kabale University |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-12-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-5a1bbe8a0dba4dfa9671614aa91eb1c02025-08-20T03:42:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-12-01vol. 25:2Combinatorics10.46298/dmtcs.99259925Facets of Random Symmetric Edge Polytopes, Degree Sequences, and ClusteringBenjamin Braunhttps://orcid.org/0000-0001-6636-8156Kaitlin BrueggeMatthew KahleSymmetric edge polytopes are lattice polytopes associated with finite simple graphs that are of interest in both theory and applications. We investigate the facet structure of symmetric edge polytopes for various models of random graphs. For an Erd\H{o}s-Renyi random graph, we identify a threshold probability at which with high probability the symmetric edge polytope shares many facet-supporting hyperplanes with that of a complete graph. We also investigate the relationship between the average local clustering, also known as the Watts-Strogatz clustering coefficient, and the number of facets for graphs with either a fixed number of edges or a fixed degree sequence. We use well-known Markov Chain Monte Carlo sampling methods to generate empirical evidence that for a fixed degree sequence, higher average local clustering in a connected graph corresponds to higher facet numbers in the associated symmetric edge polytope.http://dmtcs.episciences.org/9925/pdfmathematics - combinatorics |
| spellingShingle | Benjamin Braun Kaitlin Bruegge Matthew Kahle Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering |
| title_full | Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering |
| title_fullStr | Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering |
| title_full_unstemmed | Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering |
| title_short | Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering |
| title_sort | facets of random symmetric edge polytopes degree sequences and clustering |
| topic | mathematics - combinatorics |
| url | http://dmtcs.episciences.org/9925/pdf |
| work_keys_str_mv | AT benjaminbraun facetsofrandomsymmetricedgepolytopesdegreesequencesandclustering AT kaitlinbruegge facetsofrandomsymmetricedgepolytopesdegreesequencesandclustering AT matthewkahle facetsofrandomsymmetricedgepolytopesdegreesequencesandclustering |