Skip to main content

Questions tagged [infinite-combinatorics]

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

Filter by
Sorted by
Tagged with
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 ...
Dominic van der Zypen's user avatar
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}$. ...
Dominic van der Zypen's user avatar
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\...
Saúl RM's user avatar
  • 10.3k
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 $$\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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?
E. Z. L.'s user avatar
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, ...
hzy's user avatar
  • 151
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 \...
Dominic van der Zypen's user avatar
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 $|...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
3m0o's user avatar
  • 101
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 ...
Pace Nielsen's user avatar
  • 18.3k
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| \...
Dominic van der Zypen's user avatar
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) ...
Dominic van der Zypen's user avatar
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 $\...
Lajos Soukup's user avatar
  • 1,467
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 ...
Dominic van der Zypen's user avatar
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 $...
Sayan Dutta's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Mike Battaglia's user avatar
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) \...
Dominic van der Zypen's user avatar
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\}$ ...
Dominic van der Zypen's user avatar
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]^...
Dominic van der Zypen's user avatar
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 ...
Lajos Soukup's user avatar
  • 1,467
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 ...
Pace Nielsen's user avatar
  • 18.3k
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 ...
Alma Arjuna's user avatar
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 ...
Dominic van der Zypen's user avatar
-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 \...
Family Values's user avatar
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 $\...
Taras Banakh's user avatar
  • 41.1k
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 $...
Dominic van der Zypen's user avatar
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(...
Dominic van der Zypen's user avatar
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}\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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$. ...
Jiachen Yuan's user avatar
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 ...
Daniel Weber's user avatar
  • 3,009
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 $\,^{\...
Dominic van der Zypen's user avatar
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 ...
michael fellows's user avatar
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\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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) \...
HumbleStudent's user avatar
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$. ...
Sayan Dutta's user avatar
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 ...
Will Brian's user avatar
  • 17.6k
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar

1
2 3 4 5
10