# Questions tagged [infinite-combinatorics]

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

447 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
98 views

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 ...
246 views

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 ...
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
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 ...
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 ...
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 ...
227 views

1 vote
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 ...
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$ ...
89 views

1 vote
161 views

58 views

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 ...
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 ...
156 views

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