Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Statement

For positive integers a≤ba\le b and every integer k≥0k\ge0, existence of a model for (a,b)(a,b) implies existence of a model for

Tk(a,b)=(a+kb, a+(k+1)b).T_k(a,b)=(a+kb,\ a+(k+1)b).

The graph operation for k=0k=0 is suspension, including its hub edge. For k≥1k\ge1 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 FF be a model for (a,b)(a,b). Its internal set is nonempty, it is bipartite and balanced, and for every t≥1t\ge1 its rooted power is connected and has upper exponent

α=2−a/b∈[1,2).\alpha=2-a/b\in[1,2).

If k=0k=0, use rooted suspension. The operation lemma gives nonempty internal set, bipartiteness, balance for (a,a+b)(a,a+b), connectivity of every power, and S(F)(t)≅S(F(t))S(F)^{(t)}\cong S(F^{(t)}). The suspension upper bound applied to each fixed connected bipartite F(t)F^{(t)} gives exponent

1+13−(2−a/b)=2−aa+b.1+\frac1{3-(2-a/b)}=2-\frac{a}{a+b}.

Its constants may depend on tt, exactly as the model definition permits. Thus the suspended graph is a model for T0(a,b)T_0(a,b).

If k≥1k\ge1, use the rooted graph Tk(F)T_k(F) with the path vertices on root-root edges promoted to roots. The operation lemma proves balance for (a+kb,a+(k+1)b)(a+kb,a+(k+1)b), nonempty internal set, bipartiteness, connectivity of every positive power, and Tk(F)(t)≅Hk(F(t))T_k(F)^{(t)}\cong H_k(F^{(t)}). Apply Proposition 4.1 to each F(t)F^{(t)}. Its exponent is

1+1k+3−(2−a/b)=1+ba+(k+1)b=2−a+kba+(k+1)b.1+\frac1{k+3-(2-a/b)} =1+\frac{b}{a+(k+1)b} =2-\frac{a+kb}{a+(k+1)b}.

Every denominator is positive. The numerator a+kba+kb is positive and is at most a+(k+1)ba+(k+1)b, 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.