An official website of the United States government
Symmetric edge polytopes are lattice polytopes associated with finite simplegraphs that are of interest in both theory and applications. We investigate thefacet structure of symmetric edge polytopes for various models of randomgraphs. For an Erd\H{o}s-Renyi random graph, we identify a thresholdprobability at which with high probability the symmetric edge polytope sharesmany facet-supporting hyperplanes with that of a complete graph. We alsoinvestigate the relationship between the average local clustering, also knownas the Watts-Strogatz clustering coefficient, and the number of facets forgraphs with either a fixed number of edges or a fixed degree sequence. We usewell-known Markov Chain Monte Carlo sampling methods to generate empiricalevidence that for a fixed degree sequence, higher average local clustering in aconnected graph corresponds to higher facet numbers in the associated symmetricedge polytope.
more »
« less
Tsirelson Polytopes and randomness generation
Abstract We classify the extreme points of a polytope of probability distributions in the (2,2,2) CHSH-Bell setting that is induced by a single Tsirelson bound. We do the same for a class of polytopes obtained from a parametrized family of multiple Tsirelson bounds interacting non-trivially. Such constructions can be applied to device-independent random number generation using the method of probability estimation factors (2018 Phys. Rev. A98040304(R)). We demonstrate a meaningful improvement in certified randomness applying the new polytopes characterized here.
more »
« less
- Award ID(s):
- 1839223
- PAR ID:
- 10303663
- Publisher / Repository:
- IOP Publishing
- Date Published:
- Journal Name:
- New Journal of Physics
- Volume:
- 22
- Issue:
- 8
- ISSN:
- 1367-2630
- Page Range / eLocation ID:
- Article No. 083036
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The matching polytope of a graphGis the convex hull of the indicator vectors of the matchings onG. We characterize the graphs whose associated matching polytopes are Gorenstein, and then prove that all Gorenstein matching polytopes possess the integer decomposition property. As a special case study, we examine the matching polytopes of wheel graphs and show that they arenotGorenstein, butdopossess the integer decomposition property.more » « less
-
Abstract We present a faster direct sampling algorithm for random equilateral closed polygons in three-dimensional space. This method improves on the moment polytope sampling algorithm of Cantarellaet al(2016J. Phys. A: Math. Theor.49275202) and has (expected) time per sample quadratic in the number of edges in the polygon. We use our new sampling method and a new code for computing invariants based on the Alexander polynomial to investigate the probability of finding unknots among equilateral closed polygons.more » « less
-
Abstract Generalized associahedra are a well‐studied family of polytopes associated with a finite‐type cluster algebra and a choice of starting cluster. We show that the generalized associahedra constructed by Padrol, Palu, Pilaud, and Plamondon, building on ideas from Arkani‐Hamed, Bai, He, and Yan, can be naturally viewed as moment polytopes for an open patch of the quotient of the cluster ‐variety with universal coefficients by its maximal natural torus action. We prove our result by showing that the construction of Padrol, Palu, Pilaud, and Plamondon can be understood on the basis of the way that moment polytopes behave under symplectic reduction.more » « less
-
Abstract We consider orthogonally invariant probability measures on$$\operatorname {\mathrm {GL}}_n(\mathbb {R})$$and compare the mean of the logs of the moduli of eigenvalues of the matrices with the Lyapunov exponents of random matrix products independently drawn with respect to the measure. We give a lower bound for the former in terms of the latter. The results are motivated by Dedieu and Shub [On random and mean exponents for unitarily invariant probability measures on$$\operatorname {\mathrm {GL}}_n(\mathbb {C})$$.Astérisque287(2003), xvii, 1–18]. A novel feature of our treatment is the use of the theory of spherical polynomials in the proof of our main result.more » « less
