19
votes
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
18
votes
Accepted
Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$
It may be clarifying to work with equivalence relations $E$ on $X$ rather than partitions on $X$. The two are in natural bijection, with $E$ inducing a partitioning quotient map $q: X \to X/E$, and $X/...
- 52.4k
16
votes
Accepted
Connected graphs isomorphic to their own contraction
No. Let $G$ be the Rado graph (which is infinite, connected, and not complete), and $S$ a finite subset of the vertices of $G$ (because the Rado graph is countable). $G/S$ still has the extension ...
- 1,411
15
votes
Accepted
Selective ultrafilter and bijective mapping
No, this fails not only for selective ultrafilters but for all non-principal ultrafilters $\mathcal F$ on $\omega$.
The main ingredient in the proof is the theorem that, if an ultrafilter $\mathcal U$...
- 72.3k
15
votes
Accepted
Induced subgraphs of any given smaller chromatic number
Not necessarily. Komjáth showed that it is consistent that there is a graph of chromatic number $\aleph_2$ which does not have a subgraph (not just induced) of chromatic number $\aleph_1$. See P. ...
- 166
14
votes
Accepted
Minimal generating set for $S_\omega$
No.
Indeed, F. Galvin proved in 1995 that every countable subset of $S_\omega$ is contained in a finitely generated subgroup (and also $S_\kappa$ for every infinite $\kappa$). By contradiction ...
- 60.4k
14
votes
Accepted
Graph $G$ such that removing an edge leaves $G$ "unchanged"
An infinite path, the "left half" of its vertices is glued to triangles, the "right half" is glued to paths of length two.
You can remove an edge from one of the triangles without ...
- 12.6k
14
votes
Accepted
Is the set of powerful numbers piecewise syndetic?
The answer is no. A set $S$ to be piecewise syndetic iff there is an integer $d$ such that there exist intervals $I$ of arbitrary length such that distances between elements of $S\cap I$ are bounded ...
- 27.4k
14
votes
Size of maximal intersecting families
The answer is yes.
Consider first for simplicity the case where $X$ is countably infinite. If $\mathcal{S}$ is a maximal intersecting family, then I claim that $\mathcal{S}$ must contain a set with ...
- 225k
13
votes
Accepted
Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?
In ZFC, the player aiming for the empty set has a winning strategy in the game played on any infinite set, including the reals. Using the axiom of choice, we can well-order the set and thereby pretend ...
- 225k
13
votes
Accepted
Historical question about the $\aleph_2$-Souslin hypothesis
First, in case your question suggests that you managed to prove the consistency of $GCH+SH(\omega_2)$, then let me congratulate you wholeheartedly!
Second, to put things in context, let us recall that ...
- 1,156
13
votes
Does $\diamondsuit(\kappa)$ provably hold at Woodins or inaccessible Jónssons $\kappa$?
This is a partial answer. I will show that if $\delta$ is Woodin then $\diamondsuit_\delta$ holds.
Claim: Any Woodin cardinal is subtle.
Proof: Let $\delta$ be a Woodin cardinal. Let $\vec{A} = \...
- 5,192
13
votes
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
13
votes
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
12
votes
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 ...
- 30.2k
12
votes
Accepted
"Towers" on singular cardinals with countable cofinality
For $\lambda > 2^{\aleph_0}$, there is no such sequence.
Suppose $\lambda > 2^{\aleph_0}$. Because $2^{\aleph_0}$ cannot have countable cofinality, there is some $\kappa < \lambda$ with $2^{\...
- 17.4k
12
votes
Accepted
Is there a non-atomic finite positive measure in the plane, of which uncountably many projections have atoms?
Such a measure cannot exist. Suppose to the contrary that we have an uncountable family of lines $\ell$ such that $\mu(\ell)>0$. Then there is $\epsilon>0$ and an infinite family of lines $\{\...
- 27.3k
12
votes
Accepted
"Drinking number" of a graph
Known as unfriendly partition conjecture. Open for countable graphs: http://www.openproblemgarden.org/op/unfriendly_partitions.
- 136
12
votes
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
12
votes
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
12
votes
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
11
votes
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
11
votes
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.4k
11
votes
Accepted
Is $S_\omega/F_\omega$ embeddable to $S_\omega$?
No, it is not.
McKenzie (1971) observed that the "direct sum" of $\ge\aleph_1$ non-abelian groups cannot be embedded into $S_\omega$ (indeed, it yields an ascending chain of centralizers in $S_\...
- 60.4k
11
votes
Accepted
Is there a topological group with the small index property that does not have automatic continuity?
Here is a counterexample. Consider $\mathbb{R}$ with addition. We define a topology on this group by giving the cosets of all countable index subgroups as a sub-basis.
This subbasis is actually a ...
- 406
11
votes
Accepted
Coloring almost-disjointness
No, $\chi(G)=\mathfrak c$, in fact $G$ contains a complete subgraph on $\mathfrak c$ vertices.
A simple way to construct one is by fixing a bijection $f\colon\Bbb Q\to\omega$ and fixing, for every $r\...
- 2,904
11
votes
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
11
votes
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
11
votes
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
10
votes
Accepted
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 ...
- 103k
Only top scored, non community-wiki answers of a minimum length are eligible