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 ...
- 43.6k
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 ...
- 43.6k
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 ${\...
- 43.6k
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 (...
- 43.6k
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 ...
- 43.6k
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 ...
- 43.6k
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 \...
- 43.6k
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 ...
- 43.6k
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\...
- 1,156
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 ...
- 333
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}| > ...
- 43.6k
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 ...
- 505
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 ...
- 43.6k
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 ...
- 43.6k
-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 ...
- 43.6k
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 ...
- 43.6k
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 \...
- 505
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 ...
- 841
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 ...
- 1,058
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}$$ ...
- 43.6k
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 ...
- 1,854
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 ...
- 2,968
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}$, ...
- 505
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\...
- 43.6k
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 ...
- 43.6k
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$ ...
- 17k
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 $\...
- 966
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\...
- 43.6k
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}...
- 43.6k
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 $\...
- 43.6k
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\...
- 43.6k
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\...
- 977
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 ...
- 6,588
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 ...
- 43.6k
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 {\...
- 43.6k
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 ...
- 43.6k
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]...
- 966
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$-...
- 11
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 ...
- 1,194
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 ...
- 43.6k
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\...
- 43.6k
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 ...
- 43.6k
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,...
- 966
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\}...
- 43.6k
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 ...
- 281
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 \...
- 966
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 ...
- 390
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 ...
- 111
-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?
- 657
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,...
- 43.6k