✦ LIBER ✦

Random graphons and a weak Positivstellensatz for graphs

✍ Scribed by László Lovász; Balázs Szegedy

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 146 KB
Volume: 70
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20611

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2‐variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

Very weak zero one law for random graphs

Very weak zero one law for random graphs with order and random binary functions

✍ Saharon Shelah 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 450 KB 👁 1 views

Natural languages and random structures are given for which there are sentences A with no limit probability, yet for every A the difference between the probabilities that A holds on random structures of sizes n and n + 1 approaches zero with n.

On k-connectivity for a geometric random

On k-connectivity for a geometric random graph

✍ Mathew D. Penrose 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB 👁 1 views

For n points uniformly randomly distributed on the unit cube in d dimensions, ## Ž . with dG 2, let respectively, denote the minimum r at which the graph, obtained by n n adding an edge between each pair of points distant at most r apart, is k-connected Ž . w x respectively, has minimum degree k

A Randomized Parallel Algorithm for Plan

A Randomized Parallel Algorithm for Planar Graph Isomorphism

✍ Hillel Gazit; John H Reif 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 223 KB

We present a parallel randomized algorithm running on a CRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph Ž Ž 2 . 1 q ⑀ which can be computed by known algorithms in O log n time with

A new family of random graphs for testin

A new family of random graphs for testing spatial segregation

✍ Elvan Ceyhan; Carey E. Priebe; David J. Marchette 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 French ⚖ 382 KB

## Abstract The authors discuss a graph‐based approach for testing spatial point patterns. This approach falls under the category of data‐random graphs, which have been introduced and used for statistical pattern recognition in recent years. The authors address specifically the problem of testing c

Algorithms for coloring semi-random grap

Algorithms for coloring semi-random graphs

✍ C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 3 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co

A RANDOM GRAPH MODEL FOR THE FINAL-SIZE

A RANDOM GRAPH MODEL FOR THE FINAL-SIZE DISTRIBUTION OF HOUSEHOLD INFECTIONS

✍ M. N. ISLAM; C. D. O'SHAUGHNESSY; B. SMITH 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 344 KB 👁 2 views

In epidemiological/disease control studies, one might be interested in estimating the parameters community probability infection (CPI) and the household secondary attack rate (SAR), as introduced by Longini and Koopman. The quasi-binomial distribution I (QBD I) with parameters n, p and 0, introduced