Infinite spectra in the first order theory of graphs

DOI10.1007/BF02122699MaRDI QIDQ810048zbMATH OpenFDO

Authors Joel Spencer

Publication date 1990

Published in Combinatorica (Search for Journal in Brave)

zbMATH Keywords

random graphsthreshold functioninfinite spectra

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 54570
• On infinite spectra of first-order properties of random graphs
• A Survey on Spectra of infinite Graphs
• On the spectrum of an infinite graph
• Spectra of infinite graphs via Schur complement
• scientific article; zbMATH DE number 3963877
• Infinite spectra of first-order properties for random hypergraphs
• The Spectrum of an Infinite Graph
• scientific article; zbMATH DE number 733160
• The spectral characterization of \(\infty\)-graphs

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• Zero-One Laws for Sparse Random Graphs

Cited in

(27)

• On limit points of spectra of the random graph first-order properties
• Bounded quantifier depth spectra for random graphs
• The spectral characterization of \(\infty\)-graphs
• Spectra of short monadic sentences about sparse random graphs
• Zero-one laws for sentences with \(k\) variables
• Bounded quantifier depth spectrum for random uniform hypergraphs
• Threshold spectra via the Ehrenfeucht game
• On the spectra of first-order language properties for random graphs
• Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations
• Divisors and the spectrum of infinite graphs
• scientific article; zbMATH DE number 2121574 (Why is no real title available?)
• Two cardinal properties of homogeneous graphs
• On the 4-spectrum of first-order properties of random graphs
• Universal zero-one k-law
• Infinite spectra of first-order properties for random hypergraphs
• The spectrum of infinite regular line graphs
• Short monadic second order sentences about sparse random graphs
• On infinite spectra of first-order properties of random graphs
• Limit points of spectra for first-order properties of random hypergraphs
• Spectrum of FO logic with quantifier depth 4 is finite
• A Survey on Spectra of infinite Graphs
• First order sentences about random graphs: small number of alternations
• Quantifier alternation in first-order formulas with infinite spectra
• Spectra of infinite graphs via freeness with amalgamation
• Ordinal spectra of first-order theories
• On the spectrum of an infinite graph
• Bounded degree and planar spectra

This page was built for publication: Infinite spectra in the first order theory of graphs

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