First order distinguishability of sparse random graphs

DOI10.1145/3661814.3662117MaRDI QIDQ6970231zbMATH OpenFDO

Authors Tal Hershko, M. E. Zhukovskii

Publication date 18 June 2025

zbMATH Keywords

graph isomorphismrandom graphszero-one lawsLiouville numbersfirst order logicquantifier depthasymmetry of graphsdistinguishability of graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13)

Cites work

• scientific article; zbMATH DE number 3465382 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• An application of games to the completeness problem for formalized theories
• Einige Sätze über Kettenbrüche, mit Anwendungen auf die Theorie der Diophantischen Approximationen.
• Elements of finite model theory.
• First order distinguishability of sparse random graphs
• How complex are random graphs in first order logic?
• Matching and covering the vertices of a random graph by copies of a given graph
• Probabilities on finite models
• Random Graph Isomorphism
• Rational approximations to algebraic numbers
• Strongly balanced graphs and random graphs
• Subgraphs of dense random graphs with specified degrees
• The Asymptotic Number of Unlabelled Regular Graphs
• The first order definability of graphs: Upper bounds for quantifier depth
• The strange logic of random graphs
• The tenacity of zero-one laws
• Zero-One Laws for Sparse Random Graphs

Cited in

(1)

• First order distinguishability of sparse random graphs

This page was built for publication: First order distinguishability of sparse random graphs

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