Random graphs and the parity quantifier

DOI10.1145/2528402MaRDI QIDQ5395733zbMATH OpenOpenAlexFDO

Authors Phokion G. Kolaitis, Swastik Kopparty

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2528402

zbMATH Keywords

Gowers normslow-degree polynomialsparity quantifierrandom graphssubgraph countszero-one laws

Mathematics Subject Classification ID

Classical first-order logic (03B10) Logic in computer science (03B70) Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Random graphs (graph-theoretic aspects) (05C80) Descriptive complexity and finite models (68Q19)

Recommendations

• Random graphs and the parity quantifier
• On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth
• Zero-one \(k\)-law
• Graph decomposition and parity
• Zero-one laws for first-order formulas with a bounded quantifier depth

Cited in

(14)

• Anti-concentration for subgraph counts in random graphs
• Modular statistics for subgraph counts in sparse random graphs
• General paritioning on random graphs
• Braess's Paradox in large random graphs
• Degree lower bounds of tower-type for approximating formulas with parity quantifiers
• Graph decomposition and parity
• Random graphs and the parity quantifier
• scientific article; zbMATH DE number 6767551 (Why is no real title available?)
• Degree lower bounds of tower-type for approximating formulas with parity quantifiers
• A local central limit theorem for triangles in a random graph
• Local limit theorems for subgraph counts
• On counting t-cliques mod 2
• First-order logic with equicardinality in random graphs
• The Grothendieck constant of random and pseudo-random graphs

This page was built for publication: Random graphs and the parity quantifier

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