# Questions tagged [infinite-combinatorics]

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

447
questions

2
votes

1
answer

79
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

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

0
votes

1
answer

98
views

### Hadwiger number of the Hadwiger-Nelson graph on $\mathbb{R}^2$

If $G =(V,E)$ is a simple, undirected graph (finite or infinite), and $\kappa \neq \emptyset$ is a cardinal, we say that the complete graph $K_\kappa$ is a minor of $G$ if there is a collection ${\...

0
votes

1
answer

207
views

### Is there a lop-sided permutation $\pi:\mathbb{N}\to\mathbb{N}$? [closed]

For any $A\subseteq \mathbb{N}$ we let the (lower) density of $A$ be defined by $$d(A) = \liminf_{n\to\infty}\frac{|A\cap\{0,\ldots,n\}|}{n+1}.$$
If $\pi:\mathbb{N}\to\mathbb{N}$ is a permutation (...

0
votes

1
answer

42
views

### Minimal dominating sets in flat graphs

Suppose that $G=(V,E)$ is a simple, undirected graph. We say that $D\subseteq V$ is dominating if for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$. We say $D$ is minimal ...

4
votes

0
answers

141
views

### The monochromatic principle and the axiom of choice

For any set $A\neq\emptyset$, denote by $[A]^A$ the collection of sets $B\subseteq A$ such that there is a bijection $\varphi:B\to A$. If ${\cal S}\subseteq [A]^A$, we say that $B\in[A]^A$ is ...

2
votes

2
answers

54
views

### Does $(\omega, E)$ with the cycle condition have an $\omega$-path?

Let $G = (V,E)$ be a simple, undirected graph. We say that $v\neq w\in V$ lie on a common cycle if there is an integer $n\geq 3$ and an injective graph homomorphism $f: C_n\to V$ such that $v,w\in \...

2
votes

1
answer

60
views

### Possible chromatic numbers of a hypergraph on $\omega$ with a deck of edges

Let $\omega$ denote the first infinite ordinal (also known as the set of natural numbers). We call a set $E\subseteq {\cal P}(\omega)$ a deck if for all $n\in \omega$, the set $E$ contains exactly one ...

10
votes

1
answer

246
views

### A notion of support for nonabelian infinite groups

Every Abelian group $G$ of infinite size $\kappa$ embeds into a product $\bigoplus_{\alpha<\kappa}G_\alpha$ of countable (divisible) groups. By looking at the map $s$ that sends a group element $g\...

9
votes

0
answers

286
views

### Are infinite Ramsey numbers completely known?

I vaguely remember reading somewhere that Erdős did some work in infinitary combinatorics in the hope that it would be easier than finite combinatorics, since infinite is the limit of finite. This is ...

1
vote

0
answers

127
views

### Infinite Steiner systems

Let $\kappa<\lambda$ be cardinals where $\lambda \geq \aleph_0$ and $\kappa>1$. Is there necessarily a set ${\cal S}\subseteq {\cal P}(\lambda)$ with the following properties?
${|\cal S}| > ...

5
votes

1
answer

185
views

### Uniformization of almost disjoint families

Suppose $\mathcal{F} \subseteq \mathcal{P} (\omega) $ is an almost disjoint family and $\aleph_0 < \vert \mathcal{F} \vert = \kappa < 2^{\aleph_0} $. Is it consistent that for some such cardinal ...

0
votes

1
answer

202
views

### Does $\mathbb{Z}\times\mathbb{Z}$ have an aperiodic monotile?

For any set $S\subseteq \mathbb{Z}\times\mathbb{Z}= \mathbb{Z}^2$ and $a\in \mathbb{Z}^2$, we set $a+S = \{a+s: s\in S\}$, where $+$ is the componentwise addition in $\mathbb{Z}^2$. Moreover, for any ...

1
vote

1
answer

114
views

### Is the chromatic number of hypergraphs downward continuous?

Let $H=(V,E)$ be a hypergraph. The chromatic number $\chi(H)$ is the smallest cardinal $\kappa \leq |V|$ such that there is a map $c:V\to \kappa$ such that for all $e\in E$ having more than one ...

-3
votes

1
answer

90
views

### Order-embeddability of ${\frak b}$ and ${\frak d}$ in $\mathbb{R}$ [duplicate]

The starting point of this question is the observation that in ${\sf (ZFC)}$, all ordinals $\alpha < \omega_1$ can be order-embedded in $\mathbb{R}$.
Let $\omega^\omega$ denote the set of all ...

2
votes

1
answer

150
views

### Inspired by a card game: finding a path through $[\mathbb{N}]^n$

Motivation. Today my sons played a card game, in which a fixed number $n$ of cards was lying on the table. A move consists of adding an unused card to the cards on the table, and removing a card from ...

4
votes

1
answer

227
views

### Cofinal rectangles in poset

Suppose $(P, <)$ is a poset of cofinality $\aleph_2$ and additivity (least cardinality of an unbounded subset) $\aleph_1$. Can we conclude the existence of a cofinal subset of order-type $\omega_1 \...

1
vote

0
answers

92
views

### A two-colouring of a complete graph over the set of incompressible strings

A two-coloring is done over the (infinite) set all incompressible strings (in some chosen alphabet); such that, an edge between two strings is blue if and only if, the strings are of equal lengths and ...

5
votes

1
answer

180
views

### Are the completeness Games $G_{\lambda+1}(P)$ and $G_{\lambda^+}(P)$ equivalent for INC?

The completeness game $G_{\gamma}(P)$ for a partial order $P$ has players COM and INC play alternatingly and descendingly elements of $P$ with player INC playing first and player COM playing at limit ...

2
votes

1
answer

258
views

### Strongly uniform infinite binary strings

For $A\subseteq \omega$ we let the lower and upper density be defined as $$\mu^-(A):= \lim\inf_{n\to\infty}\frac{|A\cap n|}{n+1} \text{ and } \mu^+(A):= \lim\sup_{n\to\infty}\frac{|A\cap n|}{n+1}$$ ...

16
votes

0
answers

295
views

### Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?

My question is
Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must
$G$ have the following substructures?
i) a leafless spanning
tree;
ii) a spanning forest consisting ...

5
votes

1
answer

116
views

### Is it consistent that the additivity of Lebesgue null sets is greater than $\frak h$?

This question concerns combinatorial cardinals of the continuum.
Some of these are listed in the following diagram, from Blass's survey on the topic.
There are some additional cardinals, related to ...

6
votes

1
answer

117
views

### Cofinal trees in $({}^\omega \omega , \leq^\ast )$

So, I know that the existence of a scale (that is, a linear cofinal set in $({}^\omega \omega , \leq^\ast )$, where $\leq^\ast $ is eventual domination, is equivalent to $\mathfrak{b} = \mathfrak{d}$, ...

1
vote

1
answer

60
views

### Uniform hypergraphs with small edge intersections and propery ${\bf B}$

We say that a hypergraph $H=(V,E)$ has property ${\bf B}$ if there is $S\subseteq V$ such that for all $e\in E$ with $|e|\geq 2$ we have $$(e\cap S) \neq \emptyset \neq (e\cap (V\setminus S)).$$
If $k\...

1
vote

1
answer

64
views

### Can $\omega$ be parity-separated with finitely many bijections?

We say that a bijection $\varphi:\omega\to\omega$ parity-separates $a\neq b\in \omega$ if $\varphi(a)$ is even and $\varphi(b)$ is odd, or vice versa.
Is there a finite set $\Phi$ of bijections such ...

14
votes

1
answer

245
views

### Is there a countably infinite closed interval in the lattice of topologies?

Is there an interval of the form $[\sigma,\tau]$ in the lattice of topologies on some set $X$ such that $|[\sigma,\tau]| = \aleph_0$?
In other words, do there exist two topologies $\sigma$ and $\tau$ ...

3
votes

1
answer

89
views

### Extending almost disjoint family in a maximal set

Call a family of sets $\mathcal{F} \subseteq [\omega]^\omega$ maximal if there does not exist some $X \in [\omega]^\omega \setminus \mathcal{F}$ such that $X$ is almost disjoint with all elements of $\...

1
vote

0
answers

70
views

### Shuffling $\omega$ fairly for a fixed partition

Let ${\frak P}\subseteq {\cal P}(\omega)$ be a partition such that every block $B\in {\frak P}$ contains at least two integers.
Is there a countable set ${\cal F}$ of bijections $\varphi:\omega\to\...

1
vote

1
answer

161
views

### Partitioning $\mathbb R$ into sets such that no mutual points have distance $1$ [closed]

I was trying to partition $\mathbb R$ into two sets $A, B$ such that for all $a\in A, b\in B$ we have $|a-b|\neq 1$. An obvious way to do it is to take $\mathbb Z$ and ${\mathbb R}\setminus {\mathbb Z}...

0
votes

1
answer

89
views

### Can the absolute difference of bijections on $\omega$ also be a bijection?

For $\alpha,\beta\in \omega$ we set the absolute difference of $\alpha,\beta$ to be $$\lVert\alpha - \beta\rVert := |(\alpha\setminus\beta)\cup (\beta\setminus\alpha)|.$$ The absolute difference $\...

0
votes

0
answers

58
views

### Hadwiger numbers of (-1)-isomorphic graphs

We say that simple, undirected graphs $G, H$ are (-1)-isomorphic if there is a bijection $\varphi:V(G)\to V(H)$ such that for all $v\in V$ we have that the induced subgraphs $G\setminus\{v\}$ and $H\...

4
votes

0
answers

123
views

### An uncountable Baire γ-space without an isolated point exists?

An open cover $U$ of a space $X$ is:
• an $\omega$-cover if $X$ does not belong to $U$ and every finite subset of $X$ is contained in a member of $U$.
• a $\gamma$-cover if it is infinite and each $x\...

21
votes

2
answers

855
views

### Seymour's second neighborhood conjecture for infinite graphs

Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only ...

4
votes

1
answer

252
views

### Supremum of infimum of measure of members of a free ultrafilter

For a set $A\subseteq \omega$ we let the upper density of $A$ be defined as $d^+(A) := \lim\sup_{n\to\infty}\frac{|A\cap(n+1)|}{n+1}$. Let $\text{FrU}(\omega)$ be the collection of free ultrafilters ...

3
votes

2
answers

156
views

### Property ${\bf B}$ for families of large sets with small intersection

Let $\kappa\geq \aleph_0$ be a cardinal. If $X\neq \emptyset$ is a set, we say that a family ${\cal C}\subseteq {\cal P}(X)$ has property ${\bf B}$ if there is $S\subseteq X$ such that for all $C\in {\...

1
vote

2
answers

138
views

### Does $\{0,1\}^{<\omega}$ have a Hamiltonian path?

Let $\{0,1\}^{<\omega}$ be the collection of $x \in \{0,1\}^\omega$ such that there is $N\in\omega$ with $x(k) = 0$ for all $k\geq N$. We say that $ x, y\in \{0,1\}^{<\omega}$ form an edge if ...

5
votes

1
answer

219
views

### Minimum number of dense sets to make a filter an ultrafilter

$\newcommand{\U}{\mathcal{U}}$
$\newcommand{\F}{\mathcal{F}}$
$\newcommand{\D}{\mathcal{D}}$
$\newcommand{\C}{\mathcal{C}}$
For any infinite $X \subseteq \omega$, we define:
$$
\D_X := \{Y \in [\omega]...

1
vote

0
answers

89
views

### Rado graph and linear algebra

Let $V = \mathbb{Z}_{\geq 0}$ be the set of integers and let $\mathcal{G} = (V, E)$ be an (undirected) Rado graph on $V$. Let $W = \bigoplus_{i = 0}^{\infty} \mathbb{F}_2$ and write $x_i$ for the $i$-...

7
votes

2
answers

220
views

### Two questions on infinite hypergraphs

The famous De Bruijn–Erdős theorem and its hypergraphs generalization states the following.
Theorem. Let $V$ be a set, and $E\subset2^V$ be a family of its subsets. Assume that every $e \in E$ is ...

3
votes

1
answer

146
views

### Cycling through a general combinatorial design on $\omega$

This is a generalisation of an older question inspired by a football tournament (which does not have an answer yet).
Let $\frak P$ be a partition of $\omega$ into blocks, that is, pairwise disjoint ...

3
votes

1
answer

97
views

### Property $\mathbf{B}$ for maximal linear set systems on $\omega$ with finite members

Let $X\neq\emptyset$ be a set. A family ${\cal S}\subseteq {\cal P}(X)$ has property $\mathbf{B}$ if there is $T\subseteq X$ such that for all $S\in{\cal S}$ we have $S\cap T\neq \emptyset$ and $S\not\...

2
votes

1
answer

137
views

### De Bruijn–Erdős theorem for hypergraphs

The De Bruijn–Erdős theorem states that when all finite subgraphs of a graph $G$ can be colored with $n$ colors, the same is true for the whole graph.
There is a natural notion of coloring for ...

2
votes

0
answers

94
views

### Does every ordered-union coideal contain an ordered-union ultrafilter?

$\newcommand{\FU}{\operatorname{FU}}$
$\newcommand{\H}{\mathcal{H}}$
Recall that an ordered-union ultrafilter is an ultrafilter on $\omega$ with a base of sets of the form $\FU(A)$. Here, $A = \{a_0,...

7
votes

2
answers

459
views

### Counterexample for Chvatal's conjecture in an infinite set

Let $X \neq \emptyset$ be a set. We say that ${\cal F} \subseteq {\cal P}(X)$ is a down-set if ${\cal F}$ is closed under taking subsets. Whenever $a \in X$, we let ${\cal F}_a = \{ S \in F : a \in S\}...

5
votes

1
answer

226
views

### Question about a family of nested countable subsets of $\mathbb{R}$

Let $\mathcal{F}$ denote a family of countable subsets of $\mathbb{R}$, such that for each $U, V\in\mathcal{F}$ we have that $U\subseteq V$, or $V\subseteq U$. Let $(\mathcal{F}, \preceq)$ denote the ...

5
votes

1
answer

192
views

### Non-trivial examples of selective coideals of $\omega$

$\newcommand{\H}{\mathcal{H}}$
$\newcommand{\A}{\mathcal{A}}$
Recall that a coideal $\H$ over $\omega$ is selective if for every $\{A_n : n < \omega\} \subseteq \H$, where $i < j \implies A_i \...

5
votes

1
answer

85
views

### Searching for cofinal subsets of directed sets subject to finite constraints

Let $(P,\leq)$ be a directed set with uncountable cofinality. For every element $p\in P$, we are given a finite set $c_p\subset P\smallsetminus \{p\}$ of "incompatible elements". We say that ...

5
votes

0
answers

108
views

### Large set of almost disjoint functions on a product space

Given an increasing sequence of cardinals $\langle\kappa_\alpha\mid \alpha\in\kappa\rangle$, let $K=\prod_{\alpha\in\kappa} \kappa_\alpha$, then we call $f,g\in K$ eventually different if there exists ...

-4
votes

1
answer

187
views

### All group structures on a set with cardinality $\aleph_0$

Assume we consider the additive group $(\mathbb{Z}, 0, +)$. I am wondering what other group structures are there with neutral element 0 fixed? Is there a way to classify them or find them all?

2
votes

1
answer

236
views

### "Rule 30" in the infinite setting

This question tries to get right what went wrong in an earlier question.
Let $\{0,1\}^\mathbb{Z}$ denote the set of all functions $x:\mathbb{Z}\to \{0,1\}$. Let $+$ denote addition modulo $2$ on $\{0,...