Random homomorphisms into the orthogonality graph
From MaRDI portal
Publication:6367155
DOI10.1016/J.JCTB.2024.03.007arXiv2105.03657MaRDI QIDQ6367155FDOQ6367155
Dávid Kunszenti-Kovács, Balázs Szegedy, László Lovász
Publication date: 8 May 2021
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 , 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.
Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Density (toughness, etc.) (05C42)
This page was built for publication: Random homomorphisms into the orthogonality graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367155)
