Questions tagged [infinite-combinatorics]
Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.
590 questions
0
votes
0
answers
17
views
Finitely flexible graphs on $\omega$
We say that a simple, undirected graph $(\omega, E)$ is finitely flexible if whenever $S, T\subseteq \omega$ are finite and $b:S\to T$ is a bijection, then there is a graph isomorphism $\varphi:(\...
- 56.5k
10
votes
1
answer
552
views
Compact Hausdorff space with more homeomorphisms than Borel measures
Does there exist a compact Hausdorff space $X$ of weight $\mathfrak{c}$ with ccc such that $|\text{Homeo}(X)|>|M(X)|$, where $M(X)$ is the space of complex-valued finite regular Borel measures on $...
- 245
3
votes
1
answer
148
views
Two definitions of indecomposability for binary relations
Let $X$ be a set. If $A\subseteq X$ and $R\subseteq (X\times X)$, we say that the relation $R$ is shrinkable to $A$ if there is an injection $\iota: X \to A$ such that $$(x,y) \in R \text{ if and only ...
- 56.5k
-3
votes
1
answer
132
views
Graphs on $\omega$ with $2^{\aleph_0}$ automorphisms
Is there a connected graph $G= (\omega,E)$ with the following properties?
There are $2^{\aleph_0}$ isomorphisms $\varphi:G\to G$, and
$K_\omega$ does not embed in $G$ (equivalently: there is no ...
- 56.5k
11
votes
2
answers
448
views
Pairwise incompatible connected graphs on $\omega$
For any set $X$, let $[X]^2 = \big\{\{x,y\}: x\neq y \in X\big\}$.
Is there an uncountable set ${\cal E} \subseteq {\cal P}([\omega]^2)$ with the following properties?
For every $E\in {\cal E}$, the ...
- 56.5k
3
votes
2
answers
221
views
Sociable partitions on $\omega$
Motivation. Football training starts again for my sons, which means the year has begun in earnest. Training often includes splitting the players into small teams for certain exercises. This inspires ...
- 56.5k
11
votes
1
answer
285
views
Existence of limit intersection in an $\omega_1$-chain of almost decreasing subsets of $\omega$
Is it consistent that there exists a $\subseteq^*$-decreasing chain $(X_\alpha)_{\alpha<\omega_1}$ of infinite subsets of $\omega$ such that for all ordinals $\alpha_0 < \alpha_1 < \cdots <...
- 1,917
16
votes
1
answer
646
views
A "simple" property of boundedness
Here's the setup:
Let $f: \mathbb{N}^2 \rightarrow \mathbb{N}$ be a function. Consider the family $\mathcal{D}$ of sets $D \subset \mathbb{N}$ such that $f|_{D \times D}$ is bounded. Assume that $\...
- 375
9
votes
0
answers
306
views
A weak $\lozenge$ principle
(This is probably unrelated to Devlin-Shelah's weak diamond principle $\Phi$, but I didn't know what else to call it.)
Say a sequence $\vec{A} = \langle A_\alpha: \alpha < \kappa \rangle$ ...
- 2,344
10
votes
2
answers
250
views
How small can a set $X \subset 2^\omega$ be if it is able to distinguish any ultrafilter on $\omega$? And can I take $X$ to be a tree set?
Let's take an $X \subset 2^\omega$ such that for any two distinct ultrafilters on $\omega$ there is a set $A \in X$ such that $A$ is in one ultrafilter but not the other.
Can $X$ have cardinality less ...
- 715
12
votes
1
answer
662
views
Fixed-point free shrinking bijection
Let $J\subseteq {\cal P}(\omega)$ be the collection of infinite subsets whose complement is also infinite.
Is there a fixed-point free bijection $\varphi:J\to J$ such that $\varphi(j)\subseteq j$ for ...
- 56.5k
3
votes
0
answers
60
views
Is there a natural topology on the set of d-fibers of a graph?
Jung and Niemeyer define an equivalence relation on the set of rays of an infinite graph
where $T_p(X)$ is the set of vertices at a distance less or equal than $p$ from some vertex at $X$. (distance ...
- 715
13
votes
0
answers
325
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 ...
- 715
11
votes
1
answer
329
views
Are complete linear ordered sets decomposable?
The starting point of this question is bof's classification in this comment of indecomposable ordinals. In particular, every complete well-ordering on more than $1$ point is decomposable. Also, the ...
- 56.5k
15
votes
0
answers
835
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 ...
- 56.5k