Erdős problem 1173 — wave 8h

Date: 2026-07-28 (UTC)

Claim labels

• [a] elementary-rigorous: proved below from ZFC/cardinal arithmetic, or a

direct observation from the cited live source.

• [b] rigorous-modulo-named-theorem: the deduction is complete once the

explicitly named published theorem is accepted.

• [c] plausible/structural-unverified: a diagnosis or possible route, not a

theorem.

• [d] computational-only: exhaustively checked only in the finite range

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:

• status OPEN;
• 0 claimed proofs;
• “Currently working on this problem: None”;
• “Interested in collaborating: None”;
• one comment, by Alfaiz at 16:27 on 24 Jan 2026:

“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].

2. [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.

3. [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.

4. [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

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

3. First elementary reduction: popular points

Lemma 1

[a] If

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

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

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

Proof

Split \(S\) into

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

is \(\nu\)-almost disjoint by (1). Soukup's theorem yields sets

\(R_\alpha\in[f(\alpha)]^{<\mu}\) such that

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

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

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

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

König's theorem gives

while

For every \(n<\omega\) and every prefix

\(s\in\prod_{i \[ 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

the countable union has size \(\mu\). Call the union \(U\).

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

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

are fixed:

• \(|A_x|=\sum_n\lambda_n=\mu\).
• If \(x\neq y\) first differ at coordinate \(m\), then

\[ A_x\cap A_y=\bigcup_{n\leq m}D_{n,x\restriction n}, \]

so \(|A_x\cap A_y|=\lambda_m<\mu\).

• If \(\mathcal C\in[\mathcal B]^\kappa\) and \(n<\omega\), partition

\(\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

python3 runs/erdos1173_wave8h_reverify.py

e18eeef708c4bc56c85171cc0ef5af6efe4fffbec01da45f03de6dce008700dd

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

#!/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()