Cluster analysis of local convergent sequences of structures

DOI10.1002/RSA.20719MaRDI QIDQ4597605zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. Ossona de Mendez

Publication date 13 December 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.07788

zbMATH Keywords

first-order logicgraph and relational structuregraph limitsmeasurable graphmodel theoryRadon measuresstone spacestructural limits

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: The cluster analysis of very large objects is an important problem, which spans several theoretical as well as applied branches of mathematics and computer science. Here we suggest a novel approach: under assumption of local convergence of a sequence of finite structures we derive an asymptotic clustering. This is achieved by a blend of analytic and geometric techniques, and particularly by a new interpretation of the authors' representation theorem for limits of local convergent sequences, which serves as a guidance for the whole process. Our study may be seen as an effort to describe connectivity structure at the limit (without having a defined explicit limit structure) and to pull this connectivity structure back to the finite structures in the sequence in a continuous way.

Recommendations

• scientific article; zbMATH DE number 3903775
• scientific article; zbMATH DE number 3883431
• Analytic representations of large graphs
• Working session: Limits of structures. Abstracts from the working session held March 31 -- April 15, 2013.
• scientific article; zbMATH DE number 4041080

Cited in

(7)

• scientific article; zbMATH DE number 2065270 (Why is no real title available?)
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Local-global convergence, an analytic and structural approach
• Structural convergence and algebraic roots
• On first-order transductions of classes of graphs
• Rooting algebraic vertices of convergent sequences (extended abstract)
• Gadget construction and structural convergence

This page was built for publication: Cluster analysis of local convergent sequences of structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4597605)