Representing Embeddability as Set Inclusion

DOI10.1112/S0024610798006668MaRDI QIDQ4265406zbMATH OpenFDO

Authors Menachem Kojman

Publication date 25 October 1999

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

club guessing sequencecomplexity of classes of graphs with forbidden countable configurationscontinuity of representationembeddability of uncountable graphsforbidden subgraphpartial orderrepresentation theoremuniversal graph

Mathematics Subject Classification ID

Applications of model theory (03C98) Other combinatorial set theory (03E05) Applications of set theory (03E75) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Abstract: A few steps are made towards representation theory of embeddability among uncountable graphs. A monotone class of graphs is defined by forbidding countable subgraphs, related to the graph's end-structure. Using a combinatorial theorem of Shelah it is proved: - The complexity of the class in every regular uncountable $l>alep{h}_1$ is at least $lambd{a}^{+}+supm{u}^{alep{h}_0}:m{u}^{+}<lambda$ - For all regular uncountable $lambda>alep{h}_1$ there are $2^{l}ambda$ pairwise non embeddable graphs in the class having strong homogeneity properties. - It is characterized when some invariants of a graph $GinCal{G}_{l}ambda$ have to be inherited by one of fewer than $lambda$ subgraphs whose union covers $G$. All three results are obtained as corollaries of a representation theorem that asserts the existence of a surjective homomorphism from the relation of embeddability over isomorphism types of regular cardinality $lambda>alep{h}_1$ onto set inclusion over all subsets of reals or cardinality $lambda$ or less. Continuity properties of the homomorphism are used to extend the first result to all singular cardinals below the first cardinal fixed point of second order. The first result shows that, unlike what Shelah showed in the class of all graphs, the relations of embeddability in this class is not independent of negations of the GCH.

Recommendations

• Embedding theorems for graphs establishing negative partition relations
• The descriptive set-theoretical complexity of the embeddability relation on models of large size
• scientific article; zbMATH DE number 5233906
• The complexity of a class of infinite graphs
• On the immersion relation and an embedding problem for infinite graphs

Cited in

(10)

• On the existence of universal models
• The representability number of a chain
• There is no universal countable random-free graph
• On properties of theories which preclude the existence of universal models
• Almost isometric embedding between metric spaces
• Graph labellings in Boolean lattices
• Universal graphs at the successor of a singular cardinal
• scientific article; zbMATH DE number 6287557 (Why is no real title available?)
• Universal graphs between a strong limit singular and its power
• Club guessing and the universal models

This page was built for publication: Representing Embeddability as Set Inclusion

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