Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.
Updated
Statement
For positive integers and every integer , existence of a model for implies existence of a model for
The graph operation for is suspension, including its hub edge. For it is the promoted hub-path operation, with no hub edge. These are different graph constructions even though their parameter formulas agree at zero.
Proof
Let be a model for . Its internal set is nonempty, it is bipartite and balanced, and for every its rooted power is connected and has upper exponent
If , use rooted suspension. The operation lemma gives nonempty internal set, bipartiteness, balance for , connectivity of every power, and . The suspension upper bound applied to each fixed connected bipartite gives exponent
Its constants may depend on , exactly as the model definition permits. Thus the suspended graph is a model for .
If , use the rooted graph with the path vertices on root-root edges promoted to roots. The operation lemma proves balance for , nonempty internal set, bipartiteness, connectivity of every positive power, and . Apply Proposition 4.1 to each . Its exponent is
Every denominator is positive. The numerator is positive and is at most , so the new parameters remain in the required range. All model conditions now follow, including the quantifier over every positive power.
Source and scope
Exposition, Proposition 4.2,
p. 6. Formal counterparts are RootedUpperModels.suspension,
RootedHubPathModels.model, and UniversalHubModels.transform, pinned
Lean lines 4950–4965, 10215–10272, and 10299–10305. This page uses the
nonempty-internal-set convention stated explicitly in the formal model
and omitted from the preliminary PDF definition.
Used by. Lemma 5.1.
Bears on. #571.