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.
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
Cites work
- scientific article; zbMATH DE number 3650557 (Why is no real title available?)
- scientific article; zbMATH DE number 5485512 (Why is no real title available?)
- scientific article; zbMATH DE number 3972929 (Why is no real title available?)
- scientific article; zbMATH DE number 44603 (Why is no real title available?)
- scientific article; zbMATH DE number 1007358 (Why is no real title available?)
- scientific article; zbMATH DE number 1944718 (Why is no real title available?)
- scientific article; zbMATH DE number 863494 (Why is no real title available?)
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A survey of clones on infinite sets
- All countable monoids embed into the monoid of the infinite random graph
- Constraint Satisfaction with Countable Homogeneous Templates
- Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
- Maximal infinite-valued constraint languages
- Models Without Indiscernibles
- More sublattices of the lattice of local clones
- Oligomorphic clones
- Partitions of finite relational and set systems
- Ramsey classes of set systems
- Reducts of Ramsey structures
- Reducts of random hypergraphs
- Reducts of the random graph
- The 116 reducts of (ℚ, <, a)
- The complexity of equality constraint languages
- The complexity of satisfiability problems
- The endomorphism monoid of the random graph has uncountably many ideals.
- The monoid of the random graph
- The partite construction and Ramsey set systems
- The random graph
- The reducts of equality up to primitive positive interdefinability
- Transitivity of permutation groups on unordered sets
Cited in
(19)- Reducts of Ramsey structures
- Overgroups of the automorphism group of the Rado graph
- Permutations on the random permutation
- Solving equation systems in ω-categorical algebras
- The 42 reducts of the random ordered graph
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- PROJECTIVE CLONE HOMOMORPHISMS
- A survey of homogeneous structures
- Constraint satisfaction problems for reducts of homogeneous graphs
- A counterexample to the reconstruction of \(\omega\)-categorical structures from their endomorphism monoid
- Permutation groups containing infinite symplectic linear groups and reducts of linear spaces over the two element field
- The reducts of the homogeneous binary branching \(C\)-relation
- Pseudo‐loop conditions
- Reducts of the Henson graphs with a constant
- Galois theory for semiclones
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Infinitely many reducts of homogeneous structures
- Forbidden tournaments and the orientation completion problem
- Reducts of the random partial order
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)
