Random homomorphisms into the orthogonality graph

Kunszenti-Kovács, Dávid and Lovász, László and Szegedy, Balázs (2023) Random homomorphisms into the orthogonality graph. JOURNAL OF COMBINATORIAL THEORY SERIES B. ISSN 0095-8956

Preview

Text 2105_03657v1.pdf Download (328kB) | Preview

Abstract

Subgraph densities have been defined, and served as basic tools, both in the case of graphons (limits of dense graph sequences) and graphings (limits of bounded-degree graph sequences). While limit objects have been described for the "middle ranges", the notion of subgraph densities in these limit objects remains elusive. We define subgraph densities in the orthogonality graphs on the unit spheres in dimension d, under appropriate sparsity condition on the subgraphs. These orthogonality graphs exhibit the main difficulties of defining subgraphs the "middle" range, and so we expect their study to serve as a key example to defining subgraph densities in more general Markov spaces. The problem can also be formulated as defining and computing random orthogonal representations of graphs. Orthogonal representations have played a role in information theory, optimization, rigidity theory and quantum physics, so to study random ones may be of interest from the point of view of these applications as well.

Actions (login required)

Edit Item