Benjamin Braun ; Kaitlin Bruegge ; Matthew Kahle - Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering

dmtcs:9925 - Discrete Mathematics & Theoretical Computer Science, December 11, 2023, vol. 25:2 -
Facets of Random Symmetric Edge Polytopes, Degree Sequences, and ClusteringArticle

Authors: Benjamin Braun ; Kaitlin Bruegge ; Matthew Kahle

    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ő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.

    Volume: vol. 25:2
    Section: Combinatorics
    Published on: December 11, 2023
    Accepted on: September 26, 2023
    Submitted on: August 16, 2022
    Keywords: Mathematics - Combinatorics
      Source : OpenAIRE Graph
    • Questions and Experiments in Geometric Combinatorics; Funder: National Science Foundation; Code: 1953785

    Consultation statistics

    This page has been seen 215 times.
    This article's PDF has been downloaded 141 times.