All Questions
Tagged with combinatorial-set-theory or infinite-combinatorics
527 questions
5
votes
2
answers
706
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 ...
- 48.8k
0
votes
1
answer
81
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 ...
- 48.8k
0
votes
2
answers
99
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 {\...
- 48.8k
3
votes
2
answers
158
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\...
- 1,782
8
votes
1
answer
255
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$
...
- 48.8k
-3
votes
1
answer
73
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 ...
- 48.8k
1
vote
1
answer
73
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 ...
- 48.8k
5
votes
1
answer
297
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 ...
- 9,853
6
votes
1
answer
173
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 $...
- 48.8k
5
votes
1
answer
156
views
Intersection cardinalities in MAD families
Let $\newcommand{\o}{[\omega]^\omega}\o$ denote the collection of infinite subsets of the set of nonnegative integers $\omega$. We say ${\cal A}\subseteq \o$ is almost disjoint if $A\cap B$ is finite ...
- 48.8k
4
votes
1
answer
154
views
Minimal dominating sets in thin hypergraphs
Let $H=(V,E)$ be a hypergraph. We say that $H$ is thin if for every $v\in V$ the set $E_v=\{e\in E:v\in e\}$ is finite.
A subset $D\subseteq V$ is dominating if
$\bigcup \{e\in E:e\cap D \neq \...
- 48.8k
10
votes
1
answer
314
views
Magic-square type arrangement of rational numbers in $(0, 1)$ on $\mathbb Z\oplus\mathbb Z$
For this question, define a line $L$ in $\mathbb Z\oplus\mathbb Z$ as any subset of the form
$$L = L(u,v) = \{x = u + n v ∈ \mathbb Z\oplus\mathbb Z \mid n \in \mathbb Z\},$$
where $u \in\mathbb Z\...
- 2,858
0
votes
1
answer
99
views
Countable graph with $2^{\aleph_0}$ non-isomorphic induced minors
Let $G=(V,E)$ be a simple, undirected graph. If $S, T\subseteq V$ are disjoint sets, we say that $S,T$ are connected to each other if there are $s\in S, t\in T$ such that $\{s,t\}\in E$. We say a ...
- 48.8k
4
votes
1
answer
270
views
Jónsson functions for arbitrary ordinals
Kanamori, in his book The Higher Infinite, says that there exists a Jónsson function for an ordinal $\gamma$ if and only if there exists a Jónsson function for $|\gamma|$, where $|\gamma|$ is the ...
- 143
4
votes
1
answer
190
views
Is the transpose of an infinite Hadamard matrix also Hadamard?
Let $\omega$ be the set of non-negative integers. If $f,g:\omega\to\{-1,1\}$ are maps, then we say $f,g$ are almost orthogonal if there is a positive integer $C_0\in \omega$ such that for all $n\in\...
- 48.8k
5
votes
2
answers
307
views
Majority voting on $\{0,1\}^\mathbb{Z}$
Motivation. Sometimes in life, people seem to do what the majority of their friends are doing. Do we all become more similar over time? Do we split up into pockets of similarity? This post aims to ...
- 48.8k
6
votes
0
answers
162
views
Who wins the Scrambler-Solver game for infinitary Rubik's cubes?
Given a suitable infinitary analogue $\mathcal Q$ of the Rubik's cube (as developed below), consider the two player game played between the Scrambler and the Solver wherein the Scrambler scrambles the ...
20
votes
1
answer
556
views
Almost orthogonal maps $f:\omega \to \{-1,1\}$
Let $\omega$ denote the set of non-negative integers. For sets $A,B$, let $B^A$ denote the set of maps $f:A\to B$. For $f,g\in\{-1,1\}^\omega$ we say that $f,g$ are almost orthogonal if there is $C_0\...
- 48.8k
4
votes
1
answer
230
views
$\omega\times\omega$-Hadamard matrices
In the following, we define infinite Hadamard matrices.
Let $\omega$ be the set of non-negative integers. If $f,g:\omega\to\{-1,1\}$ are maps, then we say $f,g$ are approximately orthogonal if $$\...
- 48.8k
3
votes
1
answer
199
views
Mutually equal Hamming distance of members of ${\cal P}(\mathbb{N})$
This is inspired by an older, as of yet unanswered question.
If $X$ is a set and $A,B\subseteq X$, we let the Hamming distance of $A, B$ be defined as $d_H:=\text{card}\big((A\setminus B)\cup (B\...
- 48.8k
5
votes
1
answer
167
views
Cardinality of separating families on an infinite cardinal $\kappa$
Let $\kappa$ be an infinite cardinal. We say ${\cal S}\subseteq {\cal P}(\kappa)$ is separating if whenever $a\neq b\in \kappa$ there is $T\in {\cal S}$ such that $|T\cap\{a,b\}| = 1$. Let $\...
- 48.8k
3
votes
1
answer
96
views
Consistency of PSR for general stationary sets $S\subset [H_\kappa]^\omega$
Feng-Jech's Projective-Stationary Reflection (PSR): For every regular $\kappa\geq\omega_2$, if $S\subset[H_\kappa]^\omega$ is projective-stationary, then there is an increasing continuous $\in$-chain $...
- 335
6
votes
1
answer
186
views
Can $\square_{\kappa,\kappa}$ fail everywhere?
A theorem in Cummings-Magidor, Martin's Maximum and weak square:
Theorem. Assume MM. Then we have, for $\lambda>\omega$,
$\square_{\omega_1,\omega_1}$ fails.
If $\mathrm{cf}(\lambda)=\omega$, then ...
- 335
-1
votes
1
answer
145
views
Bijection $f:\mathbb{N}\to\mathbb{N}$ such that $f(S)\neq S$ for $S\subseteq \mathbb{N}$ infinite and co-infinite [closed]
Is there a bijection $f:\newcommand{\N}{\mathbb{N}}\N\to\N$ such that $f(S)\neq S$ whenever $S\subseteq \N$ is infinite and $\N\setminus S$ is infinite?
- 48.8k
1
vote
1
answer
90
views
$|S\cap f(S)|$ for bijections $f:\omega\to\omega$ and $S\subseteq \omega$
Is there a bijection $f:\omega\to\omega$ with the following property?
Whenever $S\subseteq \omega$ is infinite such that $\omega\setminus S$ is infinite as well, then $S\cap f(S)$ is finite.
- 48.8k
5
votes
1
answer
212
views
Image-catching families in $\omega$
Let $[\omega]^\omega$ be the collection of infinite subsets of the set of nonnegative integers $\omega$, and let $\newcommand{\I}{\cal{I}}\I=$ $\{S\in[\omega]^\omega: (\omega\setminus S)\in[\omega]^\...
- 48.8k
2
votes
1
answer
169
views
Smallest ${\mathbf B}$-function $f:\omega\to( \omega\setminus\{0\})$
Motivation. Every hypergraph $(\omega, E)$ where $E$ is countable and consists of infinite sets has property $\newcommand{\B}{\mathbf{B}}\B$. On the other hand, if the members of $E$ are allowed to be ...
- 48.8k
3
votes
1
answer
151
views
Large almost disjoint family on $\mathbb{N}$ with property $\mathbf{B}$
Let
$\newcommand{\oo}{[\omega]^\omega}\oo$ denote the collection of all infinite subsets of the set of nonnegative integers $\omega$. We say that $\newcommand{\ss}{{\cal S}}\S\subseteq \oo$ ...
- 48.8k
0
votes
1
answer
80
views
Infinite complete minor in $\min,\max$-graph on $\mathbb{N}$
Let $[\omega]^2 =\big\{\{x,y\}:x\neq y \in \omega\big\}$ denote the collection of all 2-element subsets of the non-negative integers. Let $$E=\big\{\{p,q\} : p,q \in [\omega]^2 \text{ and } \max(p)=\...
- 48.8k
1
vote
1
answer
81
views
Sieve for an infinite array of sets, resulting in an array of the same size of pairwise disjoint sets
Let $\lambda$ be an infinite cardinal. For each $\nu<\lambda$, let $(E_\xi^\nu:\xi<\lambda^+)$ be a family of pairwise disjoint sets each of cardinality at most $\lambda$.
Assume that for every ...
- 1,644
3
votes
2
answers
157
views
Modification of Lemma 0 in Hajnal's paper "Embedding finite graphs into graphs colored with infinitely many colors"
I am looking for a proof of the following lemma.
Let $E_0$ be the set of edges of an undirected graph with no loops with vertex set a cardinal $\kappa$. Let $E_1$ be the family of two-element subsets ...
- 1,644
1
vote
1
answer
86
views
Isomorphic hypergraph duals
Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
We say hypergraphs $H_i=(V_i, E_i)$ for ...
- 48.8k
3
votes
0
answers
187
views
Frankl's conjecture for infinite lattices
Given a poset $L$, call it trivial if $\left|L\right| < 2$ and let $\mathcal I\left(L\right)$ be its poset of ideals, $\mathcal C\left(L\right)$ be its set of chains, and $\mathcal M\left(L\right)$ ...
- 31
3
votes
1
answer
595
views
Euro2024-inspired scoring problem
Motivation. The Euro 2024 soccer football championship is in full swing, and the male part of my family are avid watchers. Right now the championship is in the group stage where every group member ...
- 48.8k
6
votes
0
answers
254
views
Maximal bijection-dodging families on $\mathbb{N}$
We say that a family ${\cal S}\subseteq{\cal P}(\mathbb{N})$ is bijection-dodging if there is a bijection $\varphi:\mathbb{N}\to\mathbb{N}$ with $\varphi(T)\notin {\cal S}$ for all $T\in{\cal S}$.
...
- 48.8k
42
votes
2
answers
2k
views
How decreasing can a bijection $f:\mathbb{N}\to\mathbb{N}$ be?
This is a follow-up to this question by
Dominic van der Zypen. For each bijection $f:\mathbb{N}\to\mathbb{N}$, let
$$\operatorname{rc}(f) := \liminf_{N\to\infty} \frac{\left|\left\{(m,n)\in\{1,\dots,N\...
- 10.6k
9
votes
1
answer
460
views
Min–max reversing bijections $f:\mathbb{N}\to\mathbb{N}$
For any set $X$, let $\newcommand{\N}{\mathbb{N}}[X]^2 = \big\{\{x,y\}:x\neq y \in X\big\}$ and set $[n]^2 = [\{0,\dotsc,n-1\}]^2$ for any positive integer $n$. For $A\subseteq [\N]^2$ we set $$\...
- 48.8k
3
votes
1
answer
131
views
Sparse "bijection-proof" subsets of $[\mathbb{N}]^2$
We call a collection ${\cal S}\subseteq {\cal P}(\newcommand{\N}{\mathbb{N}}\N)$ bijection-proof if for any bijection $\varphi:\N\to\N$ there is $T\in{\cal S}$ with $\varphi(T) \in {\cal S}$.
For any ...
- 48.8k
2
votes
1
answer
105
views
"Spanning trees" for connected linear hypergraphs
Starting point. For every simple, undirected graph $G=(V,E)$ there is $E_0\subseteq E$ such that $(V,E_0)$ is minimally connected: the spanning tree. The goal of this question is to find out whether ...
- 48.8k
8
votes
2
answers
509
views
Bijection $\varphi:\mathbb{N}\to\mathbb{N}$ that distorts every finite arithmetic progression
Let $\mathbb{N}$ denote the set of non-negative integers. We say $A\subseteq \mathbb{N}$ is a finite arithmetic progression if there are $a, n, d\in\mathbb{N}$ with $d \geq 1$ and $n \geq 2$ such that ...
- 48.8k
4
votes
1
answer
224
views
Shrinking and expanding pairs in bijections $\varphi:\mathbb{N}\to\mathbb{N}$
Motivation. If we consider any bijection $\varphi:\newcommand{\N}{\mathbb{N}} \N \to \N$, we say integers $m\neq n$ are shrinking with respect to $\varphi$ if $|m-n|>|\varphi(m) - \varphi(n)|$, and ...
- 48.8k
2
votes
1
answer
284
views
Size of antichains in powerset of $\mathbb N$
Take a countably infinite set $S$, say $\mathbb N$. Is it possible for there to be an antichain in $\mathcal P(S)$ (with the inclusion ordering) of continuum cardinality?
- 33
6
votes
0
answers
315
views
Can Gomoku(five in a row) draw on an infinite board? What about other m,n,k-games?
My question: how to prove or disprove the following two conjectures?
Conjecture 1: (Gomoku large conjecture) there is no draw on infinite board for Gomoku with any initial opening with finite stones, ...
- 631
3
votes
1
answer
104
views
Cardinality of splitting families
For any set $X$, let $[X]^2 = \big\{\{a,b\}:a\neq b\in X\big\}$. If $\kappa>1$ is a cardinal, then a splitting family is a collection ${\cal S} \subseteq {\cal P}(\kappa)$ such that for every $Q \...
- 48.8k
10
votes
1
answer
262
views
Does every linear cover contain a minimal cover?
This is a follow-up question to an older question.
Let $X\neq \emptyset$ be a set. We say that ${\cal C}\subseteq {\cal P}(X)$ is a cover if $\bigcup {\cal C} = X$, and we call ${\cal C}$ linear if $|...
- 48.8k
5
votes
1
answer
158
views
(Weakly) minimal subcovers of linear covers
Motivation. The starting point of this question is the trivial observation that if we cover $\mathbb{N}$ with $$\big\{\{0,\ldots n\}: n\in \mathbb{N}\big\},$$ then this cover doesn't have a minimal ...
- 48.8k
0
votes
0
answers
124
views
When $G$ is amenable is true that for a set $A \in p$ which is left piecewise syndetic then $\{ x: Ax^{-1} \in p \}$ is both sided syndetic?
Let be $G$ be a discrete group. I recall the definition of syndetic sets, thick sets and piecewise syndetic sets.
Definitions:
A set $A$ is left syndetic if there exist a finite $H \subset G$ such ...
- 101
6
votes
1
answer
545
views
Balancing act for infinite walks
Think of a one-dimensional infinite walk as a map $$w\colon \mathbb{N}\to \{-1,1\}.$$ (If it is more convenient, you can think of a walk as a subset of $\mathbb{N}$, or as a binary word, or as any ...
- 18.7k
4
votes
1
answer
97
views
Chromatic numbers realised by almost disjoint subsets of $\omega$
If $H=(V,E)$ is a hypergraph then the chromatic number $\chi(H)$ is defined to be the least cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ with $|e| \...
- 48.8k
2
votes
1
answer
86
views
Pseudo-partitions of $\mathbb{N}$
This question is loosely inspired by the exact cover / partition problem in computer science.
Let $X\neq \emptyset$ be a set and let ${\cal E}\subseteq {\cal P}(X)$. For $x\in X$ we let $c_{\cal E}(x) ...
- 48.8k