Questions tagged [infinite-combinatorics]
Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.
110 questions with no upvoted or accepted answers
16
votes
0
answers
471
views
Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?
My question is
Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must
$G$ have the following substructures?
i) a leafless spanning
tree;
ii) a spanning forest consisting ...
- 2,116
15
votes
0
answers
385
views
Coherent families of injections
This is a follow-up question to a very old one of mine, which was actually answered in a 1991 paper of Scheepers.
Let $[X]^\omega$ denote the family of all countable subsets of $X$.
Suppose $\{ f_x : ...
- 21.4k
13
votes
0
answers
768
views
Indecomposable binary relations
Let $X$ be a non-empty set. We say that a relation $R \subseteq (X \times X)$ is shrinkable to $A \subseteq X$ if there is an injection $f:X \to A$ with $(x, y) \in R$ if and only if $(f(x), f(y)) \in ...
- 55.6k
13
votes
0
answers
327
views
Can a Cohen real add a Kurepa tree?
If $V$ has no Kurepa tree and $G$ is $\mathrm{Add}(\omega,1)$-generic over $V$, can $V[G]$ have a Kurepa tree? More generally, can a forcing of size $\kappa$ create a $\kappa^+$-Kurepa tree?
This is ...
- 661
13
votes
0
answers
306
views
Is $\kappa \rightarrow [\kappa]^2_3$ the same as $\kappa \rightarrow [\kappa]^2_2$ for inaccessible $\kappa$
The principle $\kappa \rightarrow [\kappa]^2_\alpha$ states that whenever we have a coloring $c:[\kappa]^2\rightarrow \alpha$ there is $H \subset \kappa$ of size $\kappa$ s.t. $|c"[H]^2|<\alpha$.
...
- 500
13
votes
0
answers
334
views
Does $2^{\aleph_0}\rightarrow [\aleph_1]^2_3$ require that the continuum is weakly inaccessible?
A classic result of Sierpiński shows that $2^{\aleph_0}\nrightarrow [\aleph_1]^2_2$, that is, there is a coloring of pairs of real numbers using two colors such that both colors appear on any ...
- 7,527
13
votes
0
answers
1k
views
Hrushovski's Construction
Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s).
Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following:
(a) Trivial (...
- 1,882
12
votes
0
answers
296
views
Is there any known application of abstract tangle theory in logic or set theory?
In the last few years, graph theorists have taken Seymour/Robertson's notion of a tangle and generalized it to an abstract version based on the definition of a 'separation system' - a set with a ...
- 695
12
votes
0
answers
370
views
Cardinal characteristic cofinalities
This question is motivated by a recent answer of mine to another question here. Generally I would like to know which problems regarding the cofinalities of cardinal characteristics are open, including,...
- 1,172
12
votes
0
answers
234
views
Can the nowhere dense sets be more complicated than the meager sets?
Suppose $X$ is a completely metrizable space with no isolated points. Let $\mathcal{ND}_X$ denote the ideal of nowhere dense subsets of $X$, and let $\mathcal{M}_X$ denote the ideal of meager subsets ...
- 20.3k
11
votes
0
answers
437
views
CH-preserving powerfully ccc forcing of size $2^{\aleph_1}$
Is it consistent with, or even implied by, CH that there is a CH-preserving, powerfully ccc complete Boolean algebra $\mathbb{B}$ of size $2^{\aleph_1}$? (Powerfully ccc means that ccc holds in every ...
- 9,876
11
votes
0
answers
628
views
$\Sigma^2_1$ and the Continuum Hypothesis
This is a follow up to Will Brian's answer to this recent question. In particular, quoting Brian:
"In fact, Paul Larson has pointed out to me that the statement "$\phi$ and $\phi^{-1}$ are conjugate"...
- 7,527
11
votes
0
answers
292
views
Preservation of chain condition under strategically closed forcing
It is well-known that $\kappa$-closed forcing preserves $\kappa$-c.c. posets. The same argument works for $\kappa$-strategically closed forcing. Here is the definition:
A poset $\mathbb P$ is $\...
- 21.4k
11
votes
0
answers
557
views
Is there a model of set theory in which $\mathfrak p< \mathfrak b < \mathfrak q$?
Is there a model of set theory in which $\mathfrak p< \mathfrak b < \mathfrak q$?
Here $\mathfrak p$, $\mathfrak b$, $\mathfrak q$ are small uncountable cardinals:
$\mathfrak p$ is the ...
- 1,248
11
votes
0
answers
364
views
Combinatorial Hilbert spaces
Any closed subspace $V\subset {\ell}^2(\omega)$ has associated to it a subset ${\cal S}_V$ of ${\cal P}(\omega)$, call it a combinatorial Hilbert space, namely the set of all supports of all vectors ...
- 17.8k