Tag Info

Accepted

"Rocket elements" in bijections $f:\mathbb{N}\to \mathbb{N}$

Choose any infinite set $A\subseteq\mathbb N$ such that $\mu^+(A)=0$. Enumerate both $A$ and $B=\mathbb N\setminus A$ as \begin{align*} A&=\{a_1<a_2< \dots < a_n < \dots\}\\ B&=\{...
• 4,618
Accepted

• 5,192
Accepted

Family of sets with a covering property

Yes. Let $S$ be a set of cardinality $|S|\ge k+2$. Let $X=\binom Sk$, the set of all $k$-element subsets of $S$. For each $s\in S$ let $a_s=\{x\in X:s\notin x\}$, and let $A=\{a_s:s\in S\}$. It is ...
• 11.9k

Connected graphs isomorphic to their own contraction

No. Let $V = \mathbb{N}$ and $E = (0, i)$ for $i$ in $\mathbb{N}^*$ (a "star" graph where every vertex is connected to $0$). If you collapse a subset containing $0$, the collapsed vertex can ...
• 181
Accepted

Non-isomorphic projective planes on $\omega$

You ask for the number of isomorphism classes of projective planes on $\omega$. I claim that it is exactly $2^{\aleph_0}$. It is at most $2^{\aleph_0}$. Indeed, a projective plane on $\omega$ can ...
• 30k
Accepted

• 27.3k
Accepted

"Drinking number" of a graph

Known as unfriendly partition conjecture. Open for countable graphs: http://www.openproblemgarden.org/op/unfriendly_partitions.
• 136

Diagonalizing against $\omega_1$-sequences of functions mod finite

This isn't an answer, as you're working in ZFC. But it seems worth noting. Assume ZFC + AD$^{L(\mathbb{R})}$. Then $L(\mathbb{R})$ satisfies ZF + AD + DC + "the statement is false". Proof: ...
• 8,752
Accepted

Size of maximal intersecting families

Let $\mathcal S$ be a maximal intersecting family of subsets of a nonempty set $X$. Note that, for each set $A\subseteq X$, exactly one of the sets $A$ and $X\setminus A$ belongs to $\mathcal S$. It ...
• 11.9k

The Stable Set Conjecture

There is a subsequent 1989 paper by Hildebrand, "On integer sets containing strings of consecutive integers" which shows that the if the set satisfies $d(A)>\frac{k-2}{k-1}$ then the ...
• 6,100
Accepted

"König's theorem" for $T_2$-spaces?

What you are calling the "matching number" of $X$ is usually called its Souslin number -- the smallest cardinal bounding the size of any collection of pairwise disjoint open subsets of $X$. What you ...
• 17.4k
Accepted

Cardinality of families of subsets of $\mathbb{N}$ whose intersections are finite

I guess this is a variant of Noah's construction: Let $S$ be an infinite subset of $\mathbf{N}=\{0,1,2,\dots\}$. Define a leafless rooted tree $V_S$, starting from a root at level 0, such that given ...
• 60.1k
Accepted

• 2,894
Accepted

Does "$X \not\to (\omega)^\omega_2$ for every infinite $X$" imply ${\sf AC}$?

The answer is no, the statement that for every set $X$ we have $$X\not\to(\omega)^\omega_2$$ does not imply the axiom of choice. This was shown by Kleinberg and Seiferas in 1973, see MR0340025 (49 #...
• 32.2k
Accepted

Maximal intersecting families on $\omega$ that are not ultrafilters

Let $U,V,W$ be three distinct ultrafilters on $\omega$. Let $M$ be the family of those subsets of $\omega$ that belong to at least two of $U,V,W$. Then $M$ is a maximal intersecting family, it is not ...
• 72.3k

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$

The following partial answer (inspired by Pace Nielsen's deleted answer) addresses only the instances where $|R|=\aleph_0$ and $|S|\gt2^{\aleph_0}$. I claim that it's consistent (relative to the ...
• 11.9k
On a set of sets intersecting in $1$ point
Consider two sets $e,f\in E$, assume that $\max(|f|,|e|)=:\mu<\kappa$, $\{x\}:=e\cap f$. Take arbitrary element $y\in f\setminus x$, it is contained in at most $\mu$ sets from $E$. Indeed, they all ...