Questions tagged [infinite-combinatorics]
Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.
568 questions
5 votes
0 answers
112 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 ...
- 19.8k
5 votes
3 answers
317 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,010
2 votes
1 answer
79 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 ...
- 53.3k
5 votes
1 answer
217 views
Chromatic number of the antichain hypergraph on $\mathcal P(\omega)$
If $H=(V, E)$ is a hypergraph, the its chromatic number $\chi(H)$ is the smallest non-empty cardinal $\kappa$ such that there is a map $c:V \to \kappa$ such that for every $e\in E$ containing more ...
- 53.3k
7 votes
1 answer
245 views
Ascending chains in $\mathcal{P}(\kappa)/I_{\mathrm{NS}}$
$\newcommand{\NS}{\mathrm{NS}}\mathcal{P}(\kappa)/I_{\NS}$ is the Boolean algebra of subsets of $\kappa$ under nonstationary symmetric difference, with $\mathbf{0} = [\emptyset] = I_{\NS}$, $\mathbf{1}...
- 2,033
3 votes
1 answer
252 views
Chromatic number of the maximal chain hypergraph on ${\cal P}(\omega)$
If $H=(V, E)$ is a hypergraph, the its chromatic number $\chi(H)$ is the smallest non-empty cardinal $\kappa$ such that there is a map $c:V \to \kappa$ such that for every $e\in E$ containing more ...
- 53.3k
10 votes
0 answers
337 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 ...
- 8,161
3 votes
0 answers
318 views
A proof by Woodin of the Kunen Theorem
Akihiro Kanamori in his book ''The higher infinity'', in the page 320 when presented the second proof of the Kunen inconsistency Theorem, states that there are a function $S:\kappa\rightarrow P(\...
- 391
5 votes
2 answers
251 views
Relationship between tower number ($\mathfrak{t}$) and splitting number ($\mathfrak{s}$)
Recall that a tower is an infinite family $T$ of subsets of $\omega$ such that $T$ is well-ordered by the relation $\supset^*$ of almost inclusion and has no infinite pseudointersections. So, the ...
- 267
7 votes
0 answers
304 views
Is $2^\kappa\rightarrow(\kappa^+)^2_2$ possible in $\mathsf{ZF}$?
It is a classical result of Sierpiński that $2^\kappa\not\rightarrow(\kappa^+)^2_2$ in $\mathsf{ZFC}$. The proof goes by picking a well-ordering $(2^\kappa,\prec)$ and comparing it with the ...
- 1,409
12 votes
0 answers
336 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,010
1 vote
2 answers
236 views
Minimal separating subsets of $[\omega]^\omega$
Let $\newcommand{\om}{[\omega]^\omega}\om$ denote the collection of infinite subsets of the set of non-negative integers $\omega$. We say $A\subseteq\om$ is separating if for all $n,m\in\omega$ with $...
- 53.3k
0 votes
0 answers
104 views
Is there a way to visualize the Stone space of a Boolean algebra - i.e., via its corresponding lattice?
It is a little frustrating to me that I'm not able to 'see' clearly what the Stone space of a Boolean algebra is supposed to be - specially because we have a very visual object representing the ...
- 447
0 votes
1 answer
151 views
Absolute derivative of a bijection $\varphi:\omega_+\to\omega_+$
Let $\newcommand{\ome}{\omega_+}\ome=\omega\setminus\{0\}$ denote the set of positive integers. For $a,b\in \ome$ we let $$||a-b|| = |(a\setminus b)\cup(b\setminus a)|$$ be the absolute difference of $...
- 53.3k
2 votes
1 answer
686 views
Why Catalan numbers appear
Let $(x_1,x_2,...,x_{2n+1 })$ be a sequence from 0 and 2, whose members satisfy all conditions $$ \begin{align} x_1&\le 1 \\ x_1&+x_2\le 2\\ \vdots &\qquad\vdots\\ x_1&+x_2+\ldots+x_{...
- 37
17 votes
4 answers
2k views
Uniquely representing finite sets of integers by an intersection of infinite sets
$\def\N{\mathbb{N}}$Is there a set ${\cal C} \subseteq {\cal P}(\N)$ consisting of infinite subsets of $\N$, such that for every finite subset $A\subseteq \N$ there are two distinct and unique members ...
- 53.3k
10 votes
1 answer
350 views
What are the possible probabilities that a "close-to-uniform random permutation" of $\mathbb{N}$ will be a derangement?
This question builds upon a Math.SE post What is the probability that a geometric random permutation of $\mathbb{N}$ has no fixed points?. In this post $\mathbb{N}$ excludes $0$. As discussed in a ...
- 902
2 votes
1 answer
219 views
Infinite additive partition of $\mathbb{N}$
$\def\N{\mathbb{N}}$For any set $S\subseteq\N$ and $a\in \N$, we let $a+S =\{a+s: s\in S\}$. Are there infinite sets $A, S\subseteq \N$ such that $\{a+S: a\in A\}$ is an infinite partition of $\N$?
- 53.3k
2 votes
0 answers
136 views
Partitioning a cube into cuboids of different dimensions
This is how I have tried: Initial stage: One triplet of the form $(n,n,n)$. Second stage: Decompose original triplet into two triplets by splitting one of the elements of $(x,y,z)$ into two parts at ...
- 221
19 votes
2 answers
1k views
Is the powerset graph construction injective?
$\def\Pow{\text{Pow}}$Let $G = (V,E)$ be a simple, undirected graph with $V\neq\varnothing $. We define the powerset graph of $G$ by the following: the set of vertices is ${\cal P}(V)\setminus\{\...
- 53.3k
13 votes
0 answers
318 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 ...
- 541
3 votes
0 answers
172 views
How to show that the independence number $\mathfrak{i}(\kappa)$ is well-defined for some cardinal $\kappa$?
At the moment I am reading about cardinal characteristics of $\kappa$ for some uncountable $\kappa$. Here a lot of definitions can be generalised from the countable easily. For example for the pseudo-...
- 31
5 votes
1 answer
273 views
Minimal full edge sets making a family of functions into graph homomorphisms
If $V$ is a set, we define $V^V$ to be the collection of all functions $f:V\to V$. If $(V_i, E_i)$ are simple, undirected graphs for $i=0,1$, that is $E\subseteq {V\choose 2}$, we say that a map $f:...
- 53.3k
10 votes
1 answer
223 views
Is the partition relation $\omega^\alpha\to(\omega^\alpha,\omega)$ true?
The partition relation $\beta\to(\gamma,\delta)$ means that for every function $f:[\beta]^2\to2$, either there is a subset $H$ of $\beta$ of order type $\gamma$ such that $f$ is $0$ on $[H]^2$, or ...
- 2,442
5 votes
1 answer
418 views
Reverse Chang's conjecture
The two-cardinal transfer property $(\kappa,\lambda)\rightarrow(\kappa',\lambda')$ says "any structure of type $(\kappa,\lambda)$ has an elementarily equivalent structure of type $(\kappa',\...
- 541
1 vote
1 answer
220 views
Minimal cardinality of families in $[\omega]^\omega$ dominating from below
For $A, B\subseteq \omega$ we write $A\subseteq^*B$ if $A\setminus B$ is finite. Let $[\omega]^\omega$ be the collection of infinite subsets. We say that ${\cal D}\subseteq [\omega]^\omega$ is ...
- 53.3k
5 votes
0 answers
196 views
Failures of $\square$ from Chang-type reflection
For infinite cardinals $\nu \leq \lambda, \mu \leq \kappa$, let $\langle \kappa, \mu \rangle \twoheadrightarrow \langle \lambda, \nu \rangle$ be the assertion that, whenever $\langle f_i: i < \...
- 2,033
0 votes
1 answer
263 views
Lengths of arithmetical sequences and arithmetical images for bijections $\varphi:\mathbb{N}\to\mathbb{N}$
We call a finite subset $S\subseteq \mathbb{N}$ arithmetical if there are $n, k\in\mathbb{N}$ with $k>1$ such that $S = \{n+j: 0 \leq j\leq k\}$. Given an integer $\ell>0$ and a bijection $\...
- 53.3k
0 votes
0 answers
104 views
What are the uncountable homogenous graphs?
A graph is homogenous if every isomorphism between two induced finite subgraphs extends to an automorphism of the whole graph. All finite and countable homogenous graphs are known, forming a small ...
- 447
1 vote
0 answers
94 views
For infinitely generated groups, is there a known relationship between its Specker ends and the combinatorial ends of its Cayley graphs?
Ends for groups are usually defined for finitely generated groups, where a lot of different definitions (Freudenthal's topological, combinatorial, metric, by covering spaces, etc) coincide. Specker ...
- 447
8 votes
1 answer
421 views
Interchanging limits
The following definition is by Sinclair, G.E. A finitely additive generalization of the Fichtenholz–Lichtenstein theorem. Transactions of the American Mathematical Society. 1974;193:359-74. A function ...
1 vote
0 answers
90 views
Covering the positive integer point lattice in $\mathbb{R}^2$ with sublattices
Let $P$ be the positive integer point lattice on the plane, that is, all points $(x,y)\in\mathbb{R}^2$ such that $x,y\in\mathbb{N}, x,y>0$. Take $a_i,b_i,c_i\in P$ such that $b_i=(b_{i,x},b_{i,y}) \...
- 1,068
8 votes
0 answers
193 views
Degrees in infinite graphs $G$ with $G\cong L(G)$
Motivation. For any graph $G$, let $L(G)$ denote its line graph. A graph $G$ with $G\cong L(G)$ is said to be line-graph (LG)-invariant. It turns out that the only finite connected LG-invariant graphs ...
- 53.3k
5 votes
0 answers
185 views
Generalized club of elementary submodels
This is a follow-up question to this previous question. A positive answer within ZFC would lead directly to a ZFC-proof of the main result of this paper. Let $ \kappa $ and $ \varTheta $ be ...
- 111
7 votes
1 answer
252 views
Polynomially normal binary sequences
Motivation. When we try to construct a (pseudo-)random sequence $s:\newcommand{\N}{\mathbb{N}}\N\to\{0,1\}$ we often want $s$ itself, and some of its subsequences, to be normal. Question. Is there a ...
- 53.3k
10 votes
0 answers
288 views
Do Suslin forests exist in $L$?
A $(\kappa,\lambda)$-forest is a collection $\mathcal{F}$ of functions such that: for every $f\in\mathcal{F}$, we have $\mathrm{dom}(f)\in\mathcal{P}_\kappa(\lambda)$ and $\mathrm{ran}(f)\subseteq\{0,...
- 541
4 votes
0 answers
234 views
Generalized clubs and clubs
I am looking for connections between Jech's version of the generalized club filter and the usual club filter. My motivation and ultimate goal is to turn this consistency result into a ZFC-proof. Let $ ...
- 111
1 vote
1 answer
112 views
Surjective hash functions $h:\{0,1\}^* \to \{0,1\}^{2n}$ with avalanche effect
Motivation. In computer science, hash functions are maps that convert binary strings of arbitrary length to a fixed-length binary string. In symbols, we have a map $h:\{0,1\}^* \to \{0,1\}^n$ for some ...
- 53.3k
5 votes
1 answer
257 views
Diamonds on supercompact $\kappa$ after a $\kappa$-c.c. forcing
Let $\kappa$ be supercompact. Then the (supercompact) Laver diamond holds at $\kappa$: There is $f:\kappa\to V_\kappa$ such that for all $\lambda\geq \kappa$ and $x\in H(\lambda^+)$ there is $j:V\to M$...
- 101
5 votes
1 answer
276 views
Diamonds at $\omega_2$ under PFA
Let $\lambda$ be a cardinal, and $S\subset \lambda^+$ be stationary. A $\diamondsuit^+(S)$-sequence is a sequence $\langle \mathcal{A}_\alpha\mid \alpha\in S\rangle$ such that each $\mathcal{A}_\alpha\...
- 101
4 votes
1 answer
341 views
Maximum density of sum-free sets with respect to Knuth's "addition"
A subset $S\subseteq\mathbb{N}$ is said to be sum-free if whenever $s,t\in S$, then $s+t\notin S$. For instance the set of odd numbers is sum-free and has (lower and upper) asymptotic density 1/2. ...
- 53.3k
5 votes
2 answers
2k views
Shifting an irrational binary sequence
Let $\newcommand{\tn}{\{0,1\}^\mathbb{N}}\tn$ be the collection of all infinite binary sequences. For $s\in\tn$ and $k\in\mathbb{N}$ let the left-shift of $s$ by $k$ positions, $\ell_k(s)\in \tn$, be ...
- 53.3k
1 vote
1 answer
156 views
Image and pre-image integer choice function
Let $\newcommand{\Nplus}{\mathbb{N}^+}\Nplus$ denote the set of positive integers. Is there a function $f:\Nplus\to\Nplus$ with the following property? For all $(a,b)\in \Nplus\times\Nplus$ there is ...
- 53.3k
0 votes
2 answers
142 views
Is there an uncountable extension of the Ramsey set $[\omega]^2$?
We say that a family ${\cal A}\subseteq {\cal P}(\omega)$ is Ramsey if for every map $c:{\cal A}\to\{0,1\}$ there is an infinite set $X\subseteq \omega$ with the following properties: ${\cal A}\cap {\...
- 53.3k
3 votes
2 answers
849 views
Is there a sparse almost disjoint family over $\omega$ of cardinality $2^{\aleph_0}$?
Is there an almost disjoint family $\mathcal{F}$ of subsets of $\omega$ of cardinality $2^{\aleph_0}$ satisfying the following property? For all $A,B\in\mathcal{F}$ with $A\neq B$ and every $k\in\...
- 2,442
8 votes
1 answer
305 views
Maximal Ramsey families
We say that a family $\mathcal R\subseteq \mathcal P(\omega)$ is Ramsey if $\bigcup \mathcal R = \omega$, and for every map $f:\mathcal R \to \{0,1\}$ there is an infinite set $X\subseteq \omega$ ...
- 53.3k
-3 votes
1 answer
117 views
Non-Ramsey function $f:[\omega]^{<\omega}\to\{0,1\}$ [closed]
Let $\newcommand{\o}{\omega}\o$ be the set of non-negative integers, and for any set $X$, let $\newcommand{\oo}{[\o]^{<\o}}X^{<\o}$ denote the collection of all finite subsets of $X$. What is an ...
- 53.3k
2 votes
1 answer
114 views
"Gray code" for $[\omega]^{<\omega}$
Let $\newcommand{\oo}{[\omega]^{<\omega}}\oo$ denote the collection of finite subsets of the set of non-negative integers $\newcommand{\o}{\omega}\o$. If $A,B$ are any sets, let $A \,\triangle \, B ...
- 53.3k
5 votes
1 answer
357 views
Partition induced by a cover
Let $X$ be a set and let $(Y_i)_{i \in I}$ be a family of (not necessarily pairwise disjoint) subsets covering $X$, $$ X = \bigcup_{i\in I} Y_i.$$ For any subset $J \subseteq I$, we then define $$ Y_J ...
- 10.1k
6 votes
1 answer
220 views
$\omega$-de-Bruijn sequences
Let $\omega$ denote the set of non-negative integers. For which integers $n>1$ is there a sequence $b_n: \omega\to\omega$ with the following property? Whenever $v\in\omega^n$ there is a unique $...
- 53.3k