Infinite homogeneous bipartite graphs with unequal sides

1994/09/06 by Martin Goldstern, Goldstern, Martin, R. Grossberg +3
Mathematics · #FOS: Mathematics #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.math/9409204

arxiv created 1994/09/06 · arxiv updated 2009/11/30

Abstract

We call a bipartite graph \it homogeneous if every finite partial automorphism which respects left and right can be extended to a total automorphism. A (κ,λ ) bipartite graph is a bipartite graph with left side of size κ and right side of size λ. We show, using a theorem of Hrushovski on finite graphs, that there is a homogeneous (ℵ₀,2^ℵ₀ ) bipartite graph of girth 4 (thus answering negatively a question by Kupitz and Perles), and that depending on the underlying set theory all homogeneous (ℵ₀,ℵ₁) bipartite graphs may be isomorphic, or there may be 2^ℵ₁ many isomorphism types of (ℵ₀,ℵ₁) homogeneous graphs.

Related

• IB-homogeneous graphs
• Countable homogeneous ordered bipartite graphs
• Set-homogeneous directed graphs
• Extensive approach to absolute homogeneity
• The classification of homomorphism homogeneous oriented graphs