Universality among graphs omitting a complete bipartite graph

DOI10.1007/S00493-012-2033-4zbMATH Open1299.03053arXivmath/0102058OpenAlexW2022112107MaRDI QIDQ2250798FDOQ2250798

Authors: S. Shelah 

Publication date: 21 July 2014

Published in: Combinatorica (Search for Journal in Brave)

Abstract: For cardinals lambda, kappa, theta we consider the class of graphs of cardinality lambda which has no subgraph which is (kappa, theta)-complete bipartite graph. The question is whether in such a class there is a universal one under (weak) embedding. We solve this problem completely under GCH. Under various assumptions mostly related to cardinal arithmetic we prove nonexistence of universals for this problem and some related ones.

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

Recommendations

• Universal graphs without large bipartite subgraphs
• Universal graphs without large bipartite graphs assuming GCH
• Small universal families for graphs omitting cliques without GCH
• Universal infinite clique-omitting graphs
• Universal graphs omitting finitely many finite graphs

zbMATH Keywords

complete bipartite graphcofinalitystrong limit cardinalweak embedding

Mathematics Subject Classification ID

Infinite graphs (05C63) Other combinatorial set theory (03E05) Ordered sets and their cofinalities; pcf theory (03E04)

Cites Work

• The generalized continuum hypothesis revisited
• More on the revised GCH and the black box
• Notes on combinatorial set theory
• Title not available (Why is that?)
• Universal graphs without large cliques
• Universal graphs without large bipartite subgraphs
• Two cases when \(d_\kappa\) and \(d^*_\kappa\) are equal

Cited In (2)

• Embedding theorems for graphs establishing negative partition relations
• Universal graphs without large bipartite subgraphs

This page was built for publication: Universality among graphs omitting a complete bipartite graph

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