ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1173 · PARTIAL

Erdős problem 1173 — wave 8h

Date: 2026-07-28 (UTC)

Claim labels

direct observation from the cited live source.

explicitly named published theorem is accepted.

theorem.

stated.

No claim below is that problem 1173 is solved.

0. Mandatory live-page gate

[a, direct source observation] I fetched <https://www.erdosproblems.com/1173> on 2026-07-28 through the Bright Data browser path, then fetched its discussion thread separately. The live page showed:

“Is the [Ko25] reference correct?” followed by “(The site has been updated to address this comment.)”

Thus the stop condition did not fire.

The following is the statement verbatim from the live page:

Assume the generalised continuum hypothesis. Let \[ > f: \omega_{\omega+1}\to [\omega_{\omega+1}]^{\leq \aleph_\omega} > \] be a set mapping such that \[ > \lvert f(\alpha)\cap f(\beta)\rvert <\aleph_\omega > \] for all \(\alpha\neq \beta\). Does there exist a free set of cardinality \(\aleph_{\omega+1}\)?

The page lists [Ko25b, Problem 35] and [Va99, 7.88], and says “A problem of Erdős and Hajnal.” It lists no further known result.

For clarity, the standard convention in this literature is that a set mapping has \(\alpha\notin f(\alpha)\), and \(H\) is free when \(H\cap f(\alpha)=\varnothing\) for every \(\alpha\in H\). Nothing below depends on the first convention: deleting \(\alpha\) from \(f(\alpha)\) does not worsen the hypotheses.

1. Primary-source and literature audit

Sources actually checked

  1. [a, source-verified] The 1999 booklet *Some of Paul's favorite

problems* is available as a scan at <https://web.math.pmf.unizg.hr/~vjekovac/EP/Some_of_Pauls_favorite_problems.pdf>. I rendered page 13 and visually checked Problem 7.88. Despite a cropped right margin, it says: assume GCH, take the indicated set mapping with \(|f(\alpha)\cap f(\beta)|<\aleph_\omega\), and ask for a free set of cardinality \(\aleph_{\omega+1}\). This independently verifies the provenance and substance of [Va99, 7.88].

  1. [a, bibliographically verified] Péter Komjáth,

“The Erdős–Hajnal Problem List,” Bulletin of Symbolic Logic 31(3) (2025), 418–461, DOI <https://doi.org/10.1017/bsl.2025.1>, exists and its publisher abstract says it updates the Erdős–Hajnal list. The full article redirected to a subscription/access page in this environment, so I do not attribute any extra theorem or commentary to its Problem 35 beyond the live page's citation.

  1. [b] The fixed-order free-set input used below is Hajnal's free-set

theorem: if \(\lambda<\kappa\), \(\kappa\) is infinite, and \(g:\kappa\to[\kappa]^{<\lambda}\) is a set mapping, then \(g\) has a free set of cardinality \(\kappa\). The original source is András Hajnal, “Some results and problems on set theory,” Acta Math. Acad. Sci. Hungar. 11 (1960), 277–298, DOI <https://doi.org/10.1007/BF02020945>. Its definition of free set agrees with the one above.

  1. [b] The other input is Lajos Soukup,

“Essentially disjoint families, conflict free colorings and Shelah's revised GCH,” Acta Math. Hungar. 140(3) (2013), 293–303, DOI <https://doi.org/10.1007/s10474-013-0298-8>, accessible as <https://arxiv.org/abs/1207.1971>. Theorem 3.4 states, in its notation, \[ \mathbf M(\lambda,\beth_\omega,\nu)\longrightarrow \mathbf{ED} \qquad(\nu<\beth_\omega\leq\lambda). \] Equivalently, every \(\nu\)-almost-disjoint family of \(\beth_\omega\)-element subsets of \(\lambda\) is essentially disjoint: fewer than \(\beth_\omega\) points can be removed from each member so that the remainders are pairwise disjoint.

Search result

[a, search observation; not a theorem] Exact-phrase searches for the displayed intersection condition, the cardinal pair \((\aleph_\omega,\aleph_{\omega+1})\), “free set,” and Problem 1173 found the live tracker, its two listed sources, and general papers about free sets and almost-disjoint families, but no later paper claiming this instance. OpenAlex also showed no indexed citation to the 2025 Komjáth article at query time. These misses do not prove that no relevant literature exists.

2. Notation

Put

\[ \mu=\aleph_\omega,\qquad \kappa=\mu^+=\aleph_{\omega+1}. \]

Under GCH, \(\mu=\beth_\omega\). For \(x<\kappa\), define the inverse fibre

\[ I_x=\{\alpha<\kappa:x\in f(\alpha)\}. \]

3. First elementary reduction: popular points

Lemma 1

[a] If

\[ P=\{x<\kappa:|I_x|=\kappa\} \]

has cardinality at most \(\mu\), then \(f\) has a free set of cardinality \(\kappa\). This lemma needs neither GCH nor the intersection hypothesis.

Proof

Let \(X=\kappa\setminus P\), so \(|X|=\kappa\). Recursively choose \(\langle h_\xi:\xi<\kappa\rangle\) from \(X\). After choosing \(H_\xi=\{h_\eta:\eta<\xi\}\), forbid

\[ H_\xi\ \cup\ \bigcup_{\beta\in H_\xi}f(\beta)\ \cup\ \bigcup_{\beta\in H_\xi}I_\beta. \]

Every \(\xi<\kappa=\mu^+\) has \(|\xi|\leq\mu\). Each direct image has size at most \(\mu\). Also, because every chosen \(\beta\) lies outside \(P\), \(|I_\beta|<\kappa\), hence \(|I_\beta|\leq\mu\). The forbidden set therefore has size at most \(\mu\), leaving a point of \(X\). If \(\eta<\xi\), the two last unions ensure both \(h_\xi\notin f(h_\eta)\) and \(h_\eta\notin f(h_\xi)\). Thus the resulting set is free and has size \(\kappa\). \(\square\)

Consequently, [a] any counterexample must have \(\kappa\) many points, each of which belongs to \(\kappa\) many images.

4. Main partial theorem: a uniform intersection bound suffices

Theorem 2

[b, Soukup Theorem 3.4 + Hajnal's free-set theorem] Assume GCH. Suppose there are \(S\in[\kappa]^\kappa\) and a cardinal \(\nu<\mu\) such that

\[ |f(\alpha)\cap f(\beta)|<\nu \quad\text{for all distinct }\alpha,\beta\in S. \tag{1} \]

Then \(f\) has a free set of cardinality \(\kappa\).

Proof

Split \(S\) into

\[ S_{<}=\{\alpha\in S:|f(\alpha)|<\mu\},\qquad S_{=}=\{\alpha\in S:|f(\alpha)|=\mu\}. \]

Since \(\kappa\) is regular, one part has size \(\kappa\).

Case 1: \(|S_<|=\kappa\)

Since \(\operatorname{cf}(\mu)=\omega\), write \(S_<\) as countably many classes according to a bound \(|f(\alpha)|<\aleph_n\). One class \(T\) has size \(\kappa\). Apply Hajnal's theorem to the restricted mapping \(\alpha\mapsto f(\alpha)\cap T\), obtaining a free subset of \(T\) of size \(\kappa\).

Case 2: \(|S_=|=\kappa\)

Under GCH, \(\mu=\beth_\omega\). The family

\[ \mathcal A=\{f(\alpha):\alpha\in S_=\}\subseteq[\kappa]^\mu \]

is \(\nu\)-almost disjoint by (1). Soukup's theorem yields sets \(R_\alpha\in[f(\alpha)]^{<\mu}\) such that

\[ B_\alpha=f(\alpha)\setminus R_\alpha \]

are pairwise disjoint.

Again use \(\operatorname{cf}(\mu)=\omega\): thin to \(T\in[S_=]^\kappa\) and choose \(n<\omega\) so that \(|R_\alpha|<\aleph_n\) for every \(\alpha\in T\). Hajnal's theorem applied to \(\alpha\mapsto R_\alpha\cap T\) gives \(T_0\in[T]^\kappa\) free for all the exceptional parts \(R_\alpha\).

It remains to handle the disjoint remainders. Recursively choose \(\langle h_\xi:\xi<\kappa\rangle\) from \(T_0\). At stage \(\xi\), with \(H_\xi=\{h_\eta:\eta<\xi\}\), forbid

\[ H_\xi\ \cup\ \bigcup_{\beta\in H_\xi}B_\beta\ \cup\ \{\gamma\in T_0:B_\gamma\cap H_\xi\neq\varnothing\}. \tag{2} \]

The middle union has size at most \(\mu\). Pairwise disjointness of the \(B_\gamma\)'s injects the last set into \(H_\xi\), so it too has size at most \(\mu\). Thus (2) omits some point of \(T_0\). The construction makes the chosen set free for every \(B_\alpha\), while membership in \(T_0\) makes it free for every \(R_\alpha\). It is therefore free for \(f\) and has size \(\kappa\). \(\square\)

Necessary shape of any counterexample

Combining Lemma 1, Hajnal's theorem, and Theorem 2 gives the following verified reduction.

[b] Any counterexample must simultaneously satisfy:

  1. \(\big|\{\alpha<\kappa:|f(\alpha)|=\mu\}\big|=\kappa\);
  2. \(\big|\{x<\kappa:|I_x|=\kappa\}\big|=\kappa\);
  3. for every \(S\in[\kappa]^\kappa\) and every \(\nu<\mu\), some distinct

\(\alpha,\beta\in S\) satisfy \[ |f(\alpha)\cap f(\beta)|\geq\nu. \tag{3} \]

Item 3 is the exact point where the known essential-disjointness theorem stops: Soukup covers every fixed \(\nu<\beth_\omega\), whereas the problem allows bounds cofinal in \(\beth_\omega\).

The first two necessary conditions can coexist

[a] Conditions 1 and 2 do not by themselves force a contradiction, even when intersections have the much stronger bound \(1\). Let \(K\) be a field of cardinality \(\kappa\), and fix \(I\in[K]^\mu\). On the point set \(U=I\times K\), consider the \(\kappa\) affine graphs

\[ L_{a,b}=\{(x,ax+b):x\in I\}\qquad ((a,b)\in K^2). \]

Every \(L_{a,b}\) has size \(\mu\), two distinct graphs meet in at most one point, and every point \((x,y)\in U\) lies on \(\kappa\) graphs (choose any slope \(a\), then \(b=y-ax\)). Since \(|K^2|=|U|=\kappa\), bijections identify both the graphs and points with \(\kappa\), producing a set mapping with \(\kappa\) full-sized rows and \(\kappa\) popular points. Deleting a possible self-incidence preserves all these cardinalities.

By Theorem 2, [b] this mapping nevertheless has a free set of size \(\kappa\), because its intersections have a fixed finite bound. Thus the cofinal-intersection requirement in item 3 is essential to the remaining case, not an artefact of the reduction.

5. The uniformisation step is false for unindexed set families

The next construction shows that one cannot derive a \(\kappa\)-sized uniformly bounded subfamily merely from pairwise intersections \(<\mu\). It is not a counterexample to Problem 1173; its role is to locate the missing ingredient precisely.

Prefix-block construction

Let

\[ \lambda_n=\aleph_{n+1},\qquad \mathcal B=\prod_{n<\omega}\lambda_n. \]

[b, modulo König's theorem] Under GCH, \(|\mathcal B|=\kappa\). Indeed, König's theorem gives

\[ \mu=\sum_{n<\omega}\aleph_n <\prod_{n<\omega}\aleph_{n+1}=|\mathcal B|, \]

while

\[ |\mathcal B|\leq\mu^{\aleph_0} \leq(2^\mu)^{\aleph_0}=2^\mu=\mu^+=\kappa. \]

For every \(n<\omega\) and every prefix \(s\in\prod_{i<n}\lambda_i\), choose pairwise disjoint blocks

\[ D_{n,s}\quad\text{with}\quad |D_{n,s}|=\lambda_n. \]

There are only \(\mu\) block-points in total: at level \(n\) there are \(\prod_{i<n}\lambda_i<\mu\) blocks, and the level has size \(\lambda_n\); the countable union has size \(\mu\). Call the union \(U\).

For a branch \(x\in\mathcal B\), put

\[ A_x=\bigcup_{n<\omega}D_{n,x\restriction n}. \]

The following properties are all [a] once the displayed cardinalities are fixed:

\[ A_x\cap A_y=\bigcup_{n\leq m}D_{n,x\restriction n}, \] so \(|A_x\cap A_y|=\lambda_m<\mu\).

\(\mathcal C\) by prefixes of length \(n\). There are fewer than \(\kappa\) classes, so one class has size \(\kappa\). Two members of that class have intersection at least \(\lambda_n\).

Hence [b] every \(\kappa\)-sized subfamily has intersection sizes unbounded in \(\mu\), despite all pairwise intersections being \(<\mu\).

Every point of \(U\) belongs to \(\kappa\) members: the set of branches extending a fixed finite prefix has size \(\kappa\), by the same König/upper-bound calculation applied to the tail product. However, this construction deliberately has only \(|U|=\mu\) such popular points. If its members are indexed by \(\kappa\) and used as values of a set mapping, then \(\kappa\setminus U\) is immediately free. Thus [a] it is not a counterexample. It demonstrates that a proof of the original problem must use the alignment between the indices and the points in the images—specifically the \(\kappa\)-many-popular-points regime of Lemma 1—and cannot rely only on the abstract almost-disjoint family.

6. A sharp finite analogue

For finite \(V\), let \(f(v)\subseteq V\setminus\{v\}\), with \(|f(v)|\leq d\) and

\[ |f(u)\cap f(v)|<d\quad(u\neq v). \]

Proposition 3

[a] The largest \(|V|\) for which such a mapping can have no two-point free set is exactly \(2d+1\).

If there is no free pair, each unordered pair consumes at least one directed incidence. Therefore

\[ \binom{|V|}{2}\leq\sum_{v\in V}|f(v)|\leq d|V|, \]

so \(|V|\leq2d+1\).

For equality, take \(V=\mathbb Z/(2d+1)\mathbb Z\) and

\[ f(i)=\{i+1,\ldots,i+d\}\pmod{2d+1}. \]

This is the cyclic regular tournament. Exactly one direction occurs on every pair, so no pair is free; every row has size \(d\); and the maximum intersection of two rows is \(d-1<d\).

This finite theorem warns against a finite extrapolation: the literal strict analogue “intersection \(<\) row bound” permits mappings with no free pair for every finite \(d\). The infinite problem needs the singular-limit structure, not a local finite inequality.

7. Reproducible computation

The standalone checker is runs/erdos1173_wave8h_reverify.py.

Command:

python3 runs/erdos1173_wave8h_reverify.py

SHA-256 at the time of this report:

e18eeef708c4bc56c85171cc0ef5af6efe4fffbec01da45f03de6dce008700dd

It uses only the Python standard library. It:

  1. verifies the cyclic construction for \(1\leq d\leq12\);
  2. independently enumerates every labelled tournament for the exact small

cases \((d,n)=(1,3),(2,5)\); and

  1. materialises a finite prefix-block system and checks every pairwise

intersection and every prefix bucket.

The run produced:

cyclic finite analogue
d  n=2d+1  max-row  max-row-intersection  free-number
 1        3        1                     0            1
 2        5        2                     1            1
 3        7        3                     2            1
 4        9        4                     3            1
 5       11        5                     4            1
 6       13        6                     5            1
 7       15        7                     6            1
 8       17        8                     7            1
 9       19        9                     8            1
10       21       10                     9            1
11       23       11                    10            1
12       25       12                    11            1

exhaustive labelled tournament witnesses
d=1, n=3: 2 witnesses
d=2, n=5: 24 witnesses

prefix-block finite truncation
branches=120, universe=719, maximum proper intersection=10
ALL CHECKS PASSED

These numerical outputs are [d]. Proposition 3 and the infinite prefix-block calculations have separate proofs above and do not depend on the run.

Complete checker source

#!/usr/bin/env python3
"""Independent finite checks for the reductions in erdos1173_wave8h.md.

This script uses only the Python standard library.  It does not purport to
decide the infinite-cardinal problem.  It checks:

1. the sharp finite no-free-pair construction on 2d+1 points;
2. exhaustive small tournament cases d=1,2; and
3. a finite truncation of the prefix-block family used to show that
   pointwise-small intersections need not have a uniform bound.
"""

from __future__ import annotations

import argparse
import itertools
import math


def cyclic_tournament_rows(d: int) -> list[set[int]]:
    """Return out-neighbourhoods of the cyclic tournament on 2d+1 vertices."""
    if d < 1:
        raise ValueError("d must be positive")
    n = 2 * d + 1
    return [{(i + step) % n for step in range(1, d + 1)} for i in range(n)]


def verify_cyclic_tournament(d: int) -> tuple[int, int, int]:
    rows = cyclic_tournament_rows(d)
    n = len(rows)

    assert all(i not in rows[i] for i in range(n))
    assert all(len(row) == d for row in rows)

    free_pairs = []
    intersection_sizes = []
    for i, j in itertools.combinations(range(n), 2):
        directions = int(j in rows[i]) + int(i in rows[j])
        assert directions == 1
        if directions == 0:
            free_pairs.append((i, j))
        intersection_sizes.append(len(rows[i] & rows[j]))

    assert not free_pairs
    max_intersection = max(intersection_sizes, default=0)
    assert max_intersection < d
    if d > 1:
        assert max_intersection == d - 1

    # If there is no free pair, every unordered pair consumes at least one
    # directed incidence.  Hence C(n,2) <= nd, giving n <= 2d+1.
    assert math.comb(n, 2) == n * d
    assert math.comb(n + 1, 2) > (n + 1) * d
    return n, max_intersection, 1


def exhaustive_tournament_count(d: int) -> int:
    """Count labelled tournament witnesses on n=2d+1 for d <= 2."""
    n = 2 * d + 1
    pairs = list(itertools.combinations(range(n), 2))
    witnesses = 0
    for orientation_mask in range(1 << len(pairs)):
        rows = [0] * n
        for bit, (i, j) in enumerate(pairs):
            if (orientation_mask >> bit) & 1:
                rows[i] |= 1 << j
            else:
                rows[j] |= 1 << i
        if any(row.bit_count() > d for row in rows):
            continue
        if any(
            (rows[i] & rows[j]).bit_count() >= d
            for i, j in itertools.combinations(range(n), 2)
        ):
            continue
        witnesses += 1
    return witnesses


def all_prefixes(alphabet_sizes: tuple[int, ...], length: int):
    alphabets = [range(q) for q in alphabet_sizes[:length]]
    return itertools.product(*alphabets)


def verify_prefix_block_schema() -> tuple[int, int, int]:
    """Materialize and check a finite prefix-block analogue from scratch."""
    alphabet_sizes = (2, 3, 4, 5)
    # There is one block level for every prefix length, including the full
    # branch.  The terminal level is needed to keep truncated branches distinct.
    block_sizes = (1, 2, 3, 4, 5)
    branches = list(itertools.product(*(range(q) for q in alphabet_sizes)))

    blocks: dict[tuple[int, tuple[int, ...]], set[tuple]] = {}
    universe: set[tuple] = set()
    for level, block_size in enumerate(block_sizes):
        for prefix in all_prefixes(alphabet_sizes, level):
            prefix = tuple(prefix)
            block = {
                ("block-point", level, prefix, offset)
                for offset in range(block_size)
            }
            blocks[(level, prefix)] = block
            universe.update(block)

    family: dict[tuple[int, ...], set[tuple]] = {}
    for branch in branches:
        member: set[tuple] = set()
        for level in range(len(block_sizes)):
            member.update(blocks[(level, branch[:level])])
        family[branch] = member

    expected_member_size = sum(block_sizes)
    assert all(len(member) == expected_member_size for member in family.values())
    assert len(set(map(frozenset, family.values()))) == len(branches)

    maximum_intersection = 0
    for left, right in itertools.combinations(branches, 2):
        first_difference = next(
            index
            for index, (x, y) in enumerate(zip(left, right))
            if x != y
        )
        expected = sum(block_sizes[: first_difference + 1])
        actual = len(family[left] & family[right])
        assert actual == expected
        assert actual < expected_member_size
        maximum_intersection = max(maximum_intersection, actual)

    # At each nonterminal level, prefixes form fewer buckets than branches.
    # Every bucket has the expected number of extensions, and all members in it
    # share the block at that level.
    for level in range(len(alphabet_sizes)):
        buckets: dict[tuple[int, ...], list[tuple[int, ...]]] = {}
        for branch in branches:
            buckets.setdefault(branch[:level], []).append(branch)
        expected_bucket_count = math.prod(alphabet_sizes[:level])
        expected_bucket_size = math.prod(alphabet_sizes[level:])
        assert len(buckets) == expected_bucket_count
        assert all(len(bucket) == expected_bucket_size for bucket in buckets.values())
        for prefix, bucket in buckets.items():
            shared_block = blocks[(level, prefix)]
            assert all(shared_block <= family[branch] for branch in bucket)

    return len(branches), len(universe), maximum_intersection


def main() -> None:
    parser = argparse.ArgumentParser()
    parser.add_argument("--max-d", type=int, default=12)
    args = parser.parse_args()
    if args.max_d < 1:
        raise SystemExit("--max-d must be positive")

    print("cyclic finite analogue")
    print("d  n=2d+1  max-row  max-row-intersection  free-number")
    for d in range(1, args.max_d + 1):
        n, max_intersection, free_number = verify_cyclic_tournament(d)
        print(f"{d:2d} {n:8d} {d:8d} {max_intersection:21d} {free_number:12d}")

    print("\nexhaustive labelled tournament witnesses")
    for d in (1, 2):
        count = exhaustive_tournament_count(d)
        assert count > 0
        print(f"d={d}, n={2*d+1}: {count} witnesses")

    branches, universe_size, maximum_intersection = verify_prefix_block_schema()
    print("\nprefix-block finite truncation")
    print(
        f"branches={branches}, universe={universe_size}, "
        f"maximum proper intersection={maximum_intersection}"
    )
    print("ALL CHECKS PASSED")


if __name__ == "__main__":
    main()

8. Exact remaining wall

[c, structural diagnosis] The standard route now has a sharply identified failure point. Soukup's revised-GCH theorem handles \(\nu\)-almost-disjoint \(\beth_\omega\)-uniform families for every fixed \(\nu<\beth_\omega\). Problem 1173 sits exactly at the omitted boundary: intersections are individually \(<\beth_\omega\), with no common \(\nu<\beth_\omega\). The prefix-block construction proves that abstract set-family thinning cannot repair this.

A positive solution would follow from either of these genuinely new inputs:

  1. an indexed boundary essential-disjointness/thinning lemma applicable after

the three reductions in Section 4; or

  1. a direct free-set recursion that handles \(\kappa\) popular points while

the intersection sizes are cofinal in \(\mu\).

A negative solution must construct an indexed family satisfying all three necessary conditions in Section 4 and arrange that every \(\kappa\)-set contains a directed conflict. The prefix-block family fails precisely because its entire union has size only \(\mu\), leaving \(\kappa\) indices outside the union.

Finite exhaustive search cannot settle this wall: Proposition 3 already shows that every finite strict analogue permits the worst possible outcome. The missing step is singular-cardinal uniformity/index alignment, not a finite configuration whose search could be scaled with more CPU time.

PARTIAL: Under GCH a uniform intersection bound below aleph_omega on any aleph_{omega+1}-sized subfamily forces the desired free set; every counterexample must have kappa full-sized rows, kappa popular points, and intersections unbounded in aleph_omega on every kappa-subfamily, and an explicit prefix-block family proves that abstract almost-disjoint thinning alone cannot remove this final boundary case.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger