# Questions tagged [infinite-combinatorics]

Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.

494
questions

3
votes

1
answer

545
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 ...

4
votes

0
answers

154
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}$.
...

38
votes

2
answers

1k
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\...

9
votes

1
answer

362
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 $$\...

3
votes

1
answer

116
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 ...

2
votes

1
answer

87
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 ...

7
votes

2
answers

457
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 ...

4
votes

1
answer

200
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 ...

2
votes

1
answer

237
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?

5
votes

0
answers

191
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, ...

3
votes

1
answer

93
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 \...

10
votes

1
answer

253
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 $|...

5
votes

1
answer

157
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 ...

0
votes

0
answers

93
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 ...

6
votes

1
answer

532
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 ...

4
votes

1
answer

95
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| \...

2
votes

1
answer

70
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) ...

6
votes

1
answer

172
views

### Strengthening of a classical set mapping theorem of Lázár

We are writing a paper in which we need to use the following theorem to prove that a certain poset satisfies c.c.c. As far as I remember I learned this theorem from András Hajnal.
Theorem 1: If $\...

2
votes

1
answer

321
views

### Transversal of $\mathbb{N}\times\mathbb{N}$

Motivation. I am trying to make an interesting infinite version out of this fascinating problem from the Russian mathematical olympiad:
There are $c$ flavours of cookies, we are given $n$ cookies of ...

2
votes

0
answers

271
views

### On $(k,\ell)$-sumfree sets

Call a set $\mathcal S \subset \mathbb N$ to be $(k,\ell)$-sumfree if there are no non-trivial solutions to the equation
$$x_1+\dots +x_k = y_1+\dots +y_\ell$$
in the set (for distinct $x_i$'s and $...

5
votes

1
answer

210
views

### Is the partition tiling relation transitive?

The following is motivated by an (as of yet) unanswered question on optimal colorings of graphs. I am convinced that the question below has a positive answer in $\newcommand{\ZF}{{\sf (ZF)}}\ZF$, but ...

4
votes

1
answer

206
views

### Simplified method of building an Aronszajn tree

There is a very interesting method to build an Aronszajn tree in Judith Roitman's "Introduction to Modern Set Theory", on pages 100-102. In short, we build a tree $T$ in which the nodes are ...

4
votes

0
answers

225
views

### Optimal colorings

If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...

1
vote

3
answers

175
views

### Graph on $\mathbb{N}$ where almost every vertex is shy

The following question is loosely based on the friendship paradox.
Let $G=(V,E)$ be a simple, undirected graph. For $v\in V$, we let the neighborhood of $v$ be $N(v) = \big\{w\in V:\{v,w\}\in E\big\}$ ...

6
votes

1
answer

201
views

### Chromatic number of the infinite Erdős–Hajnal shift-graph

For any set $X$, let $[X]^2= \big\{\{x,y\}: x\neq y \in X\big\}$. Let $\kappa$ be an infinite cardinal. Let $G_\kappa = ([\kappa]^2, E_\kappa)$ where $E_\kappa = \big\{\{a,b\}\in \big[[\kappa]^2\big]^...

12
votes

1
answer

370
views

### Partition into antichains

I've read that the following statement is a result of Balcar, but I am unable to find a reference or a proof:
Theorem: If $\kappa\ge \lambda$ are infinite cardinals, then $[\kappa]^{<\lambda}$ can ...

2
votes

1
answer

123
views

### Closed unbounded sets and partitions

Let $\kappa$ be a regular, uncountable cardinal. Let $S\subseteq \kappa$ be a closed and unbounded set. Suppose that we partition $S$ into $<\kappa$ pieces. Does one of those pieces contain a ...

18
votes

1
answer

1k
views

### Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$

Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$.
Alice's color is red and Bob's color is blue. In each step, for each $s\in S$, a player will choose finitely many ...

3
votes

1
answer

249
views

### A possible ${\sf (ZF)}$-theorem in the spirit of the $3$-set-lemma

The number $3$ plays an interesting role in the following statement:
$\newcommand{\S}{\sf(S_3)}\S$ Let $X$ be a non-empty set and let $f:X \to X$ be fixpoint-free (that is $f(x) \neq x$ for all $x\in ...

-8
votes

2
answers

378
views

### Infinite set intersection with arithmetic progressions

Let $\mathcal{A}$ be the set of all arithmetic progressions in $\mathbb{N}$ i.e
\begin{align*}
\mathcal{A} = \{a + b\mathbb{N} : a,b\in\mathbb{N}, b\neq 0\}.
\end{align*}
Does there exist a set $X \...

2
votes

1
answer

96
views

### Is every Cartesian biaffine plane affine?

This question concerns the (synthetic) geometry of linear spaces.
Definition 1. A linear space is a pair $(P,\mathcal L)$ consisting of a set $P$ whose elements are called points and a family $\...

3
votes

2
answers

121
views

### Set sizes in linear set systems on $\mathbb{N}$ containing some disjoint sets

Is there a set $E\subseteq {\cal P}(\mathbb{N})$ of subsets of $\mathbb{N}$ with the following properties?
$|e| > 2$ for all $e\in E$,
$e_1\neq e_2 \in E$ implies $|e_1 \cap e_2| \leq 1$,
for all $...

0
votes

0
answers

109
views

### "Infima" and "suprema" in the homomorphism preorder on hypergraphs on $\omega$

$\newcommand{Po}{{\cal P}(\omega)}$
$\newcommand{lh}{\leq_{\text{hom}}}$
If $H_i = (V_i, E_i)$ are hypergraphs for $i = 1,2$, then a map $f:V_1 \to V_2$ is said to be a (hypergraph) homomorphism if $f(...

1
vote

1
answer

139
views

### Strongly regular binary sequences

Let $\mathbb{N} = \{0,1,2,\ldots\}$ denote the set of non-negative integers. If $n\in\mathbb{N}$ we let $[n] = \{0,\ldots,n-1\}$. For $A
\subseteq \mathbb{N}$ we let $$\mu^+(A) = \lim\sup_{n\to\infty}\...

6
votes

3
answers

783
views

### Connected graphs isomorphic to their own contraction

Let $G = (V, E)$ be a simple, undirected graph with $|V|>2$, and let $S\subseteq V$ be a set with more than $1$ element. By $G/S$ we denote the graph obtained by collapsing $S$ to one point. More ...

10
votes

0
answers

209
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$.
...

3
votes

1
answer

270
views

### When is an upper bound on the longest irreducible program outputting something computable?

Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program is irreducible if no subsequence of it has the ...

6
votes

1
answer

352
views

### Large subgroups of Knuth's non-associative "group" on ${\cal P}(\mathbb{N})$

Donald Knuth introduced a fast, bit-wise approximation to integer addition by $$(a,b) \mapsto a \, ^{\land} \, b \, ^{\land} \, ((a \text{ & } b) \ll 1)$$
where $a,b$ are given in binary and $\,^{\...

1
vote

0
answers

108
views

### Higman's lemma and well-quasi-ordering theory [closed]

Higman's Lemma is basic to well-quasi-ordering (WQO) theory, but has many specific forms, for example: the Cartesian product of two WQOs is a WQO. Any new extensions?
Usually proved by minimal bad ...

2
votes

1
answer

74
views

### Finite pair-splitting family of $\mathbb{N}$

This is a kind of "dual" of an older question.
Is there a finite family ${\frak F}\subseteq {\cal P}(\mathbb{N})$ such that for all $a\neq b\in\mathbb{N}$ there is $S\in{\frak F}$ with $|S\...

2
votes

1
answer

197
views

### Finite $k$-set-respecting splitting of $\mathbb{N}$

Motivation. My sons participated in a large football tournament recently; everyone wanted to be in a team with everyone else at least once. Tricky!
Formulation of the question. For any positive ...

1
vote

0
answers

70
views

### subsets of $\mathbb{N}$ whose shifts have finite intersection property in density

I am interested in proving the statement:
Let $S\subseteq\mathbb{N}$ such that for every $r\in\mathbb{N}$ and for every $k_{1}$, $k_{2}$, $\ldots$, $k_{r}\in\mathbb{N}$, the set $\big(S-k_{1}\big) \...

16
votes

2
answers

983
views

### The Stable Set Conjecture

A set $\mathcal S$ of positive integers is called stable if for every fixed positive integer $d$, the relation
$$n\in \mathcal S \iff dn\in \mathcal S$$
holds for almost all positive integers $n$. ...

10
votes

0
answers

157
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 ...

4
votes

1
answer

123
views

### $\aleph_0$-uniform non-bipartite linear hypergraph

A hypergraph $H= (V,E)$ is said to be bipartite if there is $S\subseteq V$ such that for all $e\in E$ with $|e|>1$ we have $$S\cap e\neq \emptyset\neq (e\setminus S).$$ A hypergraph is said to be ...

4
votes

1
answer

168
views

### Maximal intersecting families on $\omega$ that are not ultrafilters

A family ${\cal S}\subseteq{\cal P}(\omega)$ is intersecting if any two members of ${\cal S}$ have non-empty intersection. Zorn's Lemma implies that every intersecting family is contained in a maximal ...

10
votes

2
answers

952
views

### Size of maximal intersecting families

Let $X$ be a non-empty set, and let ${\cal S}\subseteq {\cal P}(X)$ be family of non-empty subsets of $X$. We say that ${\cal S}$ is intersecting if any two members of ${\cal S}$ have non-empty ...

4
votes

1
answer

151
views

### How much can we "shrink" intersecting families

Motivation. An intersecting family is a collection of subsets ${\cal S}\subseteq {\cal P}(X)$ of a set $X\neq \emptyset$ such that $A\cap B\neq \emptyset$ for all $A,B\in {\cal S}$. The intersections ...

2
votes

1
answer

87
views

### Is the Hadwiger-Nelson graph restricted to $\mathbb{Q}\times\mathbb{Q}$ bipartite?

Consider the graph on $\mathbb{Q}\times\mathbb{Q}$ where two members of $\mathbb{Q}\times\mathbb{Q}$ form an edge if and only if their distance is $1$. Is that graph bipartite? If not, what is its ...

0
votes

0
answers

178
views

### A perfect shuffle on $\mathbb{N}$

Motivation. This weekend I was playing the pair-matching game Memory (also called Concentration in other parts of the world) against my youngest son, and wondered about what constitutes a "good ...