Reducts of the random bipartite graph

DOI10.1215/00294527-1731371MaRDI QIDQ1934952zbMATH OpenOpenAlexFDO

Authors Yun Lu

Publication date 30 January 2013

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.1947, https://projecteuclid.org/euclid.ndjfl/1355494521

zbMATH Keywords

closed permutation subgroupsfinite submodel propertyrandom bipartite graphreduct

Mathematics Subject Classification ID

Models of other mathematical theories (03C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $Gamma$ be the random bipartite graph, a countable graph with two infinite sides, edges randomly distributed between the sides, but no edges within a side. In this paper, we investigate the reducts of $Gamma$ that preserve sides. We classify the closed permutation subgroups containing the group $Aut(Gamma{)}^{\ast }$, where $Aut(Gamma{)}^{\ast }$ is the group of all isomorphisms and anti-isomorphisms of $Gamma$ preserving the two sides. Our results rely on a combinatorial theorem of Nev{s}etv{r}il-R"{o}dl and a strong finite submodel property for $Gamma$.

Recommendations

• Reducts of the random graph
• Reducts of random hypergraphs
• Reducts of the generic digraph
• The 42 reducts of the random ordered graph
• scientific article; zbMATH DE number 3893250

Cites work

• HOMOGENEOUS RELATIONS
• scientific article; zbMATH DE number 3638844 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Models Without Indiscernibles
• Reducts of random hypergraphs
• Reducts of the random graph
• The 116 reducts of (ℚ, <, a)
• The Ramsey property for graphs with forbidden complete subgraphs
• The reducts of equality up to primitive positive interdefinability

Cited in

(3)

• The 42 reducts of the random ordered graph
• Reducts of the random graph
• Reducts of the generic digraph

This page was built for publication: Reducts of the random bipartite graph

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