Geodesic
Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.9925
Classification : 05C10, 05C80, 52B11, 52B20 
@article{DMTCS_2024_25_2_a16,
     author = {Braun, Benjamin and Bruegge, Kaitlin and Kahle, Matthew},
     title = {Facets of {Random} {Symmetric} {Edge} {Polytopes,} {Degree} {Sequences,} and {Clustering}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2023-2024},
     doi = {10.46298/dmtcs.9925},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9925/}
}
TY  - JOUR
AU  - Braun, Benjamin
AU  - Bruegge, Kaitlin
AU  - Kahle, Matthew
TI  - Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9925/
DO  - 10.46298/dmtcs.9925
LA  - en
ID  - DMTCS_2024_25_2_a16
ER  - 
%0 Journal Article
%A Braun, Benjamin
%A Bruegge, Kaitlin
%A Kahle, Matthew
%T Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9925/
%R 10.46298/dmtcs.9925
%G en
%F DMTCS_2024_25_2_a16
Braun, Benjamin; Bruegge, Kaitlin; Kahle, Matthew. Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2. doi : 10.46298/dmtcs.9925. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9925/

Cité par Sources :