Exponential random graph models with soft clique constraints

arXiv:2608.30869v1 Announce Type: cross Abstract: Let rgeq3 be fixed, and let mathbf{G}_n be the set of all simple graphs with vertex set [n]={1,ldots,n}. We consider an exponential random graph model which gives higher probability to G in mathbf{G}_n than to H in mathbf{G}_n if G has fewer r-cliques than H. But all graphs in mathbf{G}_n have positive probability. The degree to which graphs with fewer r-cliques are given higher probability is determined by a positive weight w. We prove that, asymptotically almost surely as n o infty, a random graph from mathbf{G}_n has a vertex partition into r-1 parts of roughly equal size, the density of edges between the parts is close to 1/2, and for every arepsilon > 0 the density of edges within any part is less than arepsilon. The asymptotic structural properties are independent of the weight w as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.

Source: arXiv cs.AI | 2026-09-01