论文标题
随机对称边缘多型，度序列和聚类的方面
Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering
论文作者
论文摘要
对称边缘多面体是与有限的简单图相关的晶格多面体，这些图在理论和应用中都很感兴趣。我们研究了各种随机图模型的对称边缘多面体的相结构。对于ERDőS-RENYI随机图，我们确定了一个阈值概率，在该阈值概率上，对称边缘多层与完整的图形共享许多相支持的超级平面。我们还研究了平均局部聚类（也称为Watts-Strogatz聚类系数）与具有固定数量边缘数量或固定度序列的图形的相之间的关系。我们使用著名的马尔可夫链蒙特卡洛采样方法来生成经验证据，即在固定度序列中，连接图中的较高平均局部聚类对应于相关的对称边缘多层型中的较高的刻面数。
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.
