## Abstract

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

Original language | English |
---|---|

Journal | Discrete Mathematics and Theoretical Computer Science |

Volume | 252 |

DOIs | |

State | Published - Dec 11 2023 |

### Bibliographical note

Publisher Copyright:© 2023 Discrete Mathematics and Theoretical Computer Science. All rights reserved.

### Funding

MK was partially supported by National Science Foundation award DMS-2005630. BB and KB were partially supported by National Science Foundation award DMS-1953785. The authors thank Tianran Chen and Rob Davis for helpful discussions that motivated this project. The authors thank Dhruv Mubayi for helpful suggestions regarding random graphs.

Funders | Funder number |
---|---|

National Science Foundation Arctic Social Science Program | DMS-2005630, DMS-1953785 |

## Keywords

- clustering
- facets
- random graphs
- Symmetric edge polytope

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science
- Discrete Mathematics and Combinatorics