Minimal functions on the random graph

DOI10.1007/S11856-014-1042-YzbMATH Open1292.05231arXiv1003.4030OpenAlexW2963197653MaRDI QIDQ2017162FDOQ2017162

Manuel Bodirsky, Michael Pinsker

Publication date: 25 June 2014

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: We show that there is a system of 14 non-trivial finitary functions on the random graph with the following properties: Any non-trivial function on the random graph generates one of the functions of this system by means of composition with automorphisms and by topological closure, and the system is minimal in the sense that no subset of the system has the same property. The theorem is obtained by proving a Ramsey-type theorem for colorings of tuples in finite powers of the random graph, and by applying this to find regular patterns in the behavior of any function on the random graph. As model-theoretic corollaries of our methods we re-derive a theorem of Simon Thomas classifying the first-order closed reducts of the random graph, and prove some refinements of this theorem; also, we obtain a classification of the minimal reducts closed under primitive positive definitions, and prove that all reducts of the random graph are model-complete.

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

Recommendations

• On the extremal function for graph minors
• Extremal functions for graph minors
• The minrank of random graphs
• The Minrank of Random Graphs
• scientific article; zbMATH DE number 7651160
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• Minors in random regular graphs
• On random graphs from a minor-closed class
• The minrank of random graphs over arbitrary fields

zbMATH Keywords

Ramsey-type theorem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Generalized Ramsey theory (05C55)

Cites Work

• Title not available (Why is that?)
• Ramsey classes of set systems
• The partite construction and Ramsey set systems
• Transitivity of permutation groups on unordered sets
• Partitions of finite relational and set systems
• Schaefer's theorem for graphs
• The reducts of equality up to primitive positive interdefinability
• Title not available (Why is that?)
• Constraint Satisfaction with Countable Homogeneous Templates
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Models Without Indiscernibles
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of satisfiability problems
• A survey of clones on infinite sets
• Maximal infinite-valued constraint languages
• Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
• The complexity of equality constraint languages
• Title not available (Why is that?)
• The random graph
• Title not available (Why is that?)
• Reducts of Ramsey structures
• Reducts of random hypergraphs
• The 116 reducts of (ℚ, <, a)
• Reducts of the random graph
• Title not available (Why is that?)
• More sublattices of the lattice of local clones
• All countable monoids embed into the monoid of the infinite random graph
• The endomorphism monoid of the random graph has uncountably many ideals.
• Oligomorphic clones
• The monoid of the random graph

Cited In (19)

• A survey of homogeneous structures
• PROJECTIVE CLONE HOMOMORPHISMS
• Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
• Permutation groups containing infinite symplectic linear groups and reducts of linear spaces over the two element field
• Infinitely many reducts of homogeneous structures
• Overgroups of the Automorphism Group of the Rado Graph
• The 42 reducts of the random ordered graph
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• Pseudo‐loop conditions
• Galois theory for semiclones
• A counterexample to the reconstruction of \(\omega\)-categorical structures from their endomorphism monoid
• Reducts of the random partial order
• THE REDUCTS OF THE HOMOGENEOUS BINARY BRANCHING C-RELATION
• Schaefer's theorem for graphs
• Smooth approximations and CSPs over finitely bounded homogeneous structures
• Permutations on the random permutation
• Forbidden tournaments and the orientation completion problem
• Solving equation systems in ω-categorical algebras
• Reducts of the Henson graphs with a constant

This page was built for publication: Minimal functions on the random graph

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