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&=\{...

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/...

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

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$...

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

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

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

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

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

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

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

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} = \...

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

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

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

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^{\...

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 $\{\...

12
votes

Accepted

### "Drinking number" of a graph

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

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: ...

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

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

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

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

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_\...

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

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

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 #...

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

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

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

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

infinite-combinatorics × 479set-theory × 302

co.combinatorics × 117

graph-theory × 103

hypergraph × 81

lo.logic × 74

graph-colorings × 41

forcing × 35

gn.general-topology × 22

gr.group-theory × 19

order-theory × 17

large-cardinals × 16

ultrafilters × 15

matching-theory × 15

ramsey-theory × 14

cardinal-characteristics × 14

nt.number-theory × 13

reference-request × 12

descriptive-set-theory × 12

posets × 12

measure-theory × 11

covering × 11

partitions × 10

axiom-of-choice × 9

sequences-and-series × 7