1
$\begingroup$

A clutter is a pair $C=(V,E)$ where $V\neq\emptyset$ is a set, and $E\subseteq {\cal P}(V)$ such that no member of $E$ is included in another member of $E$. A matching in $C$ is a collection of pairwise disjoint members of $E$. Zorn's Lemma implies that every matching is contained in a maximal matching (with respect to $\subseteq$).

Is it possible to find a clutter $C=(V,E)$ with $E\neq\emptyset$ and for every matching $M\subseteq E$ there is a matching $M'\subseteq E$ with $|M|<|M'|$?

$\endgroup$
2
  • 2
    $\begingroup$ So... a clutter is an antichain, and a matching is a strong antichain? (In the sense that in the Boolean algebra $\mathcal P(V)$, any two conditions are incompatible.) $\endgroup$
    – Asaf Karagila
    Commented Nov 13, 2019 at 12:24
  • $\begingroup$ Consider building a clutter by partitioning the reals in (0,1), expressed in binary with non terminating expansions. Let the first two sets of the clutter be one set with first digit 1 and second digit 0. The next partitions into four based on the values of the second and third digits. The next, eight based on digits four through six. And so on. Gerhard "And They Tell Two Friends..." Paseman, 2019.11.13. $\endgroup$ Commented Nov 13, 2019 at 14:56

2 Answers 2

5
$\begingroup$

Yes, this is possible. For each prime $p$ and $c \in \{0,1, \dots, p-1\}$ let $A_{c,p}=\{c+kp \mid k \in \mathbb{Z}\}$. Clearly, the set of all $A_{c,p}$ is a clutter $\mathcal C$ with ground set $\mathbb{Z}$. If we fix $p$, then the set of $A_{c,p}$ is a matching of size $p$. Since there are infinitely many primes, $\mathcal C$ has arbitrarily large finite matchings. On the other hand, no matching of $\mathcal C$ is infinite. To see this, it suffices to prove that if $A_{c_1,p_1}$ and $A_{c_2,p_2}$ are disjoint, then $p_1=p_2$. Suppose $p_1 \neq p_2$. By shifting both sequences by $c_1$, we may assume that $c_1=0$. Choosing $k \equiv -c_2 p_2^{-1} \pmod{p_1}$, we have $c_2+kp_2 \equiv 0 \pmod{p_1}$, and so $A_{c_1,p_1} \cap A_{c_2,p_2}$ is non-empty.

$\endgroup$
3
$\begingroup$

In the same spirit of Tony Huynh's answer:

Take $V = \prod_{n < \omega} n + 1 = \{f \colon \mathbb{N} \to \mathbb{N} \mid \forall n,\, f(n) \leq n\}$. Take $A_{n, i} = \{f \in V \mid f(n) = i\}$. Take $E = \{A_{n,i} \mid n < \omega, i \leq n\}$. Clearly, $A_{n,i} \cap A_{m,j} = \emptyset$ iff $n = m, i \neq j$. Thus, the sets of pairwise disjoint elements from $E$ are of any finite size, while $E$ is infinite. By a slight modification of the same idea we get:

Claim: Let $\mathcal{K}$ be an infinite collection of non-zero cardinals. There is a set $X$ of size $\sup \mathcal{K}$, a collection $E \subseteq P(X)$ of size $\prod \mathcal{K}$ such that for every $a, b \in E$, $a \not\subseteq b$ and the collection of cardinalities of maximal pairwise disjoint subsets of $E$ is exactly $\mathcal{K}$.

Proof: Take $X$ to be the finite support product of $\mathcal{K}$ (namely, choice functions for $\mathcal{K}$ which are non-zero only for finitely many coordinates). For every $x \in \prod \mathcal{K}$ (the full support product) which is identically zero at most once, and for every $\kappa \in \mathcal{K}$ and $\alpha \in \kappa$, take

$$A_{\kappa, \alpha, x} = \{f \in X \mid f(\kappa) = \alpha,\, \exists \mu \in \mathcal{K}, f(\mu) \neq 0, x(\mu)\},$$ and $E$ the collection of all $A_{\kappa,\alpha, x}$ such that $x(\kappa) = \alpha$. For $\kappa \neq \kappa'$ in $\mathcal{K}$, $\alpha \in \kappa, \alpha' \in \kappa'$ and $x, x'$ take $f$ to be the function such that $f(\kappa) = \alpha,\, f(\kappa') = \alpha'$ and pick one additional elements in $\mathcal{K}$ of size $>2$ to conflict with both $x$ and $x'$. Then $f \in A_{\kappa, \alpha, x} \cap A_{\kappa', \alpha', x'}$.

This argument shows that if two sets in $E$ are disjoint then $\kappa = \kappa', \alpha \neq \alpha'$, giving an explicit description of all maximal pairwise disjoint subsets of $E$.

We need to show that for all $a, b \in E$, $a \not\subseteq b$. Take $a = A_{\kappa,\alpha, x}, b = A_{\kappa', \alpha', x'}$. If $\kappa \neq \kappa'$ or $\alpha \neq \alpha'$, take $f(\kappa) = \alpha$, $f(\kappa') \neq \alpha'$. Otherwise, take $\mu \in \mathcal{K}$ such that $x(\mu) \neq x'(\mu)$ and set $f(\mu) = x'(\mu)$. Set all other values of $f$ to be zero, then $f \in A_{\kappa,\alpha, x}$ but $f \notin A_{\kappa',\alpha', x'}$.

$\endgroup$
1
  • $\begingroup$ Thank you @YairHayut - I would like to accept both your and Tony's answer, but this is not possible. As he was first, I am going to accept his answer. Thanks for your beautifully written post! $\endgroup$ Commented Nov 13, 2019 at 20:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .