# Questions tagged [infinite-combinatorics]

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

494 questions
Filter by
Sorted by
Tagged with
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 ...
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}$. ...
1k views

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 ...
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 ...
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 ...
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 ...
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?
• 33
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, ...
• 151
93 views

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 ...
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 ...
• 101
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 ...
• 18.3k
95 views

172 views

• 781
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 ...
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,697
225 views

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 ...
• 1,467
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.3k
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 ...
• 389
249 views

96 views