# Minimal functions on the random graph

@article{Bodirsky2010MinimalFO, title={Minimal functions on the random graph}, author={Manuel Bodirsky and Michael Pinsker}, journal={Israel Journal of Mathematics}, year={2010}, volume={200}, pages={251-296} }

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… Expand

#### Supplemental Presentations

#### 39 Citations

Reducts of the random partial order

- Mathematics
- 2011

Abstract We determine, up to the equivalence of first-order interdefinability, all structures which are first-order definable in the random partial order. It turns out that there are precisely five… Expand

Reducts of Ramsey structures

- Mathematics, Computer Science
- AMS-ASL Joint Special Session
- 2009

A survey of results in model theory and theoretical computer science obtained recently by the authors in this context, which approaches the problem of classifying the reducts of countably infinite ordered homogeneous Ramsey structures in a finite language, and certain decidability questions connected with such reduCTs. Expand

Clones and homogeneous structures

- Mathematics
- 2017

A structure A is called homogeneous, if every isomorphism between its finitely generated substructures extends to an automorphism of A. In this thesis we are studying homogeneous structures with… Expand

Schaefer's Theorem for Graphs

- Computer Science, Mathematics
- J. ACM
- 2015

It is proved that either Ψ is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. Expand

Constraint satisfaction problems for reducts of homogeneous graphs

- Mathematics, Computer Science
- ICALP
- 2016

It is shown that for all structures with domain H_n whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $\Gamma$ is either in P or is NP-complete, which completes the complexity classification of constraint satisfaction problems of structures first- order definability in countably infinite homogeneous graphs. Expand

Schaefer's theorem for graphs

- Mathematics, Computer Science
- STOC '11
- 2011

It is proved that either Psi is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. Expand

The universal homogeneous binary tree

- Computer Science, Mathematics
- J. Log. Comput.
- 2018

This work classifies the model-complete cores of the reducts of S2, that is, the relational structures with the same domain as S2 all of whose relations are first-order definable in S2. Expand

Multicoloured Random Graphs: Constructions and Symmetry

- Mathematics
- 2015

This is a research monograph on constructions of and group actions on countable homogeneous graphs, concentrating particularly on the simple random graph and its edge-coloured variants. We study… Expand

Constraint satisfaction tractability from semi-lattice operations on infinite sets

- Mathematics, Computer Science
- TOCL
- 2013

A generalization of the theorem by Jeavons et al. to infinite domain CSPs where the number of orbits of n-subsets grows subexponentially in n, and it is proved that preservation under a semi-lattice operation for such C SPs implies polynomial-time tractability. Expand

Equations in oligomorphic clones and the Constraint Satisfaction Problem for $ω$-categorical structures

- Mathematics, Computer Science
- J. Math. Log.
- 2019

It is proved that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a non-trivial system of linear identities, and obtain non-Trivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Expand

#### References

SHOWING 1-10 OF 47 REFERENCES

Reducts of Ramsey structures

- Mathematics, Computer Science
- AMS-ASL Joint Special Session
- 2009

A survey of results in model theory and theoretical computer science obtained recently by the authors in this context, which approaches the problem of classifying the reducts of countably infinite ordered homogeneous Ramsey structures in a finite language, and certain decidability questions connected with such reduCTs. Expand

Schaefer's theorem for graphs

- Mathematics, Computer Science
- STOC '11
- 2011

It is proved that either Psi is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. Expand

Constraint Satisfaction with Countable Homogeneous Templates

- Computer Science, Mathematics
- J. Log. Comput.
- 2006

It is proved that the primitive positive definable relations over an ω-categorical structure Γ are precisely the relations that are preserved by the polymorphisms of Γ. Expand

Reducts of Random Hypergraphs

- Mathematics, Computer Science
- Ann. Pure Appl. Log.
- 1996

It is shown that there exist only finitely many closed permutation groups G such that AUt(rk ) < G < &vn( rk) and each of the associated reducts of rk is homogeneous with respect to a finite relational language. Expand

The complexity of satisfiability problems

- Computer Science, Mathematics
- STOC
- 1978

An infinite class of satisfiability problems is considered which contains these two particular problems as special cases, and it is shown that every member of this class is either polynomial-time decidable or NP-complete. Expand

Oligomorphic clones

- 2007

Abstract.A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its… Expand

The Endomorphism
Monoid of the Random Graph has Uncountably Many Ideals

- Mathematics
- 2004

Abstract
In this note we prove that the monoid End(R) of all
endomorphisms of the random graph R is not simple. On the
contrary, the lattice of ideals of End(R) embeds the poset of
all subsets of ω,… Expand

All countable monoids embed into the monoid of the infinite random graph

- Computer Science, Mathematics
- Discret. Math.
- 2010

It is proved that the full transformation monoid on a countably infinite set is isomorphic to a submonoid of End(R), the endomorphism monoid of the infinite random graph R, which has an undecidable universal theory. Expand

The 116 reducts of (Q, <, a)

- Computer Science
- J. Symb. Log.
- 2008

This article aims to classify those reducts of expansions of (Q, <) by unary predicates which eliminate quantifiers, and in particular to show that, up to interdefinability, there are only finitely… Expand

Topological Birkhoff

- Mathematics, Computer Science
- ArXiv
- 2012

One of the most fundamental mathematical contributions of Garrett Birkhoff is the HSP theorem, which implies that a finite algebra B satisfies all equations that hold in a finite algebra A of the… Expand