Wiki
Wiki

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

Updated

Two scoped limits of sparse direction and full-profile focusing


These results constrain two proposed Ramsey implementations. They do not exclude color-adaptive cancellation between several mixed trades, and are not a coloring theorem for the whole line family.

1. Bounded reciprocal mass forces bounded actual colors

For signed linear direction matchings of sizes did_i, put S=∑i1/diS=\sum_i1/d_i. Then

χ1≤χQ≤⌈1+S⌉.(1)\chi_1\leq\chi_{\mathbb Q}\leq\lceil1+S\rceil. \tag{1}

For any column subset BB, normalize its columns to unit length and let GBG_B be their Gram matrix. A size-did_i column meets at most did_i disjoint members of direction jj; each squared correlation is at most 1/(didj)1/(d_id_j). Hence

tr⁡GB=∣B∣,tr⁡(GB2)≤(1+S)∣B∣.\operatorname{tr}G_B=|B|,\qquad \operatorname{tr}(G_B^2)\leq(1+S)|B|.

Cauchy--Schwarz on its nonzero eigenvalues gives rank⁡QB≥∣B∣/(1+S)\operatorname{rank}_{\mathbb Q}B\geq|B|/(1+S). Edmonds, Theorem 1 now proves (1). Both the digest and exact source statement were checked.

Thus assigning domains so large that SS remains bounded cannot produce an unbounded-color direction family. The established extraction phase condition permits divergent SS; (1) does not rule out that regime.

2. Initial-plane profiles need not homogenize on a later column

In each field, flag, or polynomial line model, partition rows into initial affine pp-planes. Every later column meets each such plane at most once. Later sizes are pkp^k, k≥2k\geq2, with at most pkp^k directions at each size.

Claim. The initial planes can be labeled with sixteen labels so that no later column meets planes all bearing the same label.

For a finite stage, color planes independently and uniformly with sixteen labels. The event for a column of size DD has probability 161−D16^{1-D}. Assign it local-lemma weight xD=2−Dx_D=2^{-D}. A plane contains p2p^2 points and so meets at most p2MEp^2M_E columns among MEM_E directions of size EE. Thus the sum of neighboring event weights for a DD-column is at most

Dp2∑k≥2pk2−pk≤(8/7)D.(2)Dp^2\sum_{k\geq2}p^k2^{-p^k}\leq(8/7)D. \tag{2}

Successive summands have ratio p 2−(p−1)pk≤1/8p\,2^{-(p-1)p^k}\leq1/8. The first summand, after multiplication by p2p^2, is at most one since p4≤2p2p^4\leq2^{p^2}. This proves (2). Since all xD≤1/16x_D\leq1/16, the dependency product is at least

exp⁡(−(16/15)(8/7)D)=exp⁡(−128D/105).\exp(-(16/15)(8/7)D)=\exp(-128D/105).

For D≥4D\geq4,

D−1Dlog⁡16−log⁡2≥2log⁡2>4/3>128/105.\frac{D-1}{D}\log16-\log2\geq2\log2>4/3>128/105.

Therefore

161−D≤2−Dexp⁡(−128D/105),16^{1-D}\leq2^{-D}\exp(-128D/105),

which verifies the asymmetric local-lemma hypothesis. The relevant independent-variable statement was checked after its digest in Moser--Tardos, Theorems 1.1--1.2. Compactness gives the same labeling on a nested infinite model.

Realization by proper colors on the initial columns

In each initial pp-plane, split every parallel class into two nonempty parts. Each binary part is rationally independent: a relation in the full affine plane is constant within each parallel class, whereas the part omits a column from every class. Pair this binary color with the plane's sixteen-valued label. Across the disjoint initial planes, this gives thirty-two proper initial-column colors.

Any later column encounters distinct plane labels and hence distinct complete initial-plane color profiles. Consequently a Ramsey argument that requires identical full old-plane profiles along one entire later column cannot be universal.

This coloring is only on the initial columns. It does not color the later ones or split their mixed relations; several later columns can cancel outside a chosen profile class. No general color-adaptive lifting theorem is refuted. The finite dependency estimates and scope are author-recorded. No computational search was run.