Questions tagged [infinite-combinatorics]
Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.
580 questions
9
votes
2
answers
153
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 ...
- 695
10
votes
1
answer
352
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 ...
- 55.6k
3
votes
0
answers
59
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 ...
- 695
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
11
votes
1
answer
322
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 ...
- 55.6k
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
8
votes
3
answers
919
views
$(\mathbb{Q}\times\mathbb{Q})$-sudoku
Is there a map $s: \mathbb{Q}\times\mathbb{Q} \to \mathbb{N}$ with the following properties?
For all $z\in\mathbb{Z}$, the restriction $s|_{[z,z+1)\times [z,z+1)}: [z,z+1)\times [z,z+1) \to \mathbb{N}...
- 55.6k
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
1
vote
1
answer
82
views
Chromatic number of the singleton-intersection graph on ${\cal P}(\omega)$
We endow $\newcommand{\Po}{{\mathcal P}(\omega)}\Po$ with a graph structure by letting
$E = \big\{\{a,b\}: a, b\subseteq \omega \land a \neq b \land (\exists n\in \omega(a\cap b = \{n\})\big\}$.
Every ...
- 55.6k
-2
votes
1
answer
141
views
Infinite fibers in $K$-continuous maps $f:\mathbb{Z}\times \mathbb{Z} \to \mathbb{N}$
If $\newcommand{\Z}{\mathbb{Z}}\newcommand{\N}{\mathbb{N}}f:\Z\times\Z \to \N$ we let $${\rm I}(f)=\{n\in\N : f^{-1}(\{n\}) \text{ is infinite}\}$$ be the set of natural numbers with infinite pre-...
- 55.6k
3
votes
0
answers
129
views
Order-universal permutation numbers
Inspired by Dominic van der Zypen's question and Ilya Bogdanov's answer I wonder what to make of two cardinal characteristics. To define them, let $e_U$ be the increasing enumeration of an infinite ...
- 1,172
13
votes
1
answer
540
views
Order-universal permutation $\alpha:\omega\to\omega$
For the set $\omega$ of non-negative integers, we let $\newcommand{\oo}{[\omega]^\omega}\oo$ be the collection of infinite subsets of $\omega$. If $U\in \oo$, there is a unique order-preserving ...
- 55.6k
17
votes
1
answer
564
views
Chains of nulls sets: on a question of Elkies (sort of)
Noam Elkies maintains a page of mathematical miscellany on his website. The last entry on this page is a problem he proposed to the American Mathematical Monthly, rejected on the advice of both ...
- 20.3k
5
votes
3
answers
496
views
Cardinal arithmetic inequalities according to ZF
Suppose $\kappa$, $\lambda$, $\mu$, and $\nu$ are cardinals which may or may not be ordinals. Can we prove without resorting to the axiom of choice either of the following:
$\kappa + \lambda \...
- 1,172
3
votes
1
answer
119
views
Cardinality of fibers in a $T_2$-hypergraph with large edges
We say that a hypergraph $H=(V,E)$ is $T_2$ if for all $v, w\in V$ with $v\neq w$, there are disjoint sets $e_1, e_2\in E$ with $v\in e_1, w\in e_2$.
For $v\in V$, let $e_v= \{e\in E: v\in e\}$.
Given ...
- 55.6k