Questions tagged [infinite-combinatorics]
Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.
475
questions
1
vote
0
answers
193
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 $...
5
votes
1
answer
205
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 ...
4
votes
1
answer
192
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
votes
0
answers
214
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) \...
1
vote
3
answers
160
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\}$ ...
5
votes
1
answer
188
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]^...
12
votes
1
answer
368
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 ...
2
votes
1
answer
112
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
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 ...
2
votes
1
answer
221
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 ...
-8
votes
2
answers
367
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 \...
2
votes
1
answer
95
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 $\...
3
votes
2
answers
120
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 $...
0
votes
0
answers
108
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(...
1
vote
1
answer
130
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}\...
6
votes
3
answers
779
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 ...
10
votes
0
answers
206
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$.
...
3
votes
1
answer
264
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 ...
6
votes
1
answer
350
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 $\,^{\...
1
vote
0
answers
100
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 ...
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\...
2
votes
1
answer
196
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 ...
1
vote
0
answers
68
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) \...
16
votes
2
answers
960
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$. ...
10
votes
0
answers
152
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 ...
4
votes
1
answer
121
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 ...
4
votes
1
answer
164
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 ...
10
votes
2
answers
910
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 ...
4
votes
1
answer
148
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 ...
2
votes
1
answer
86
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
176
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
100
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
213
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
48
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
146
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
61
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
65
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
256
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
297
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
130
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
191
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
208
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
124
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
96
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
164
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
235
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
94
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
191
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
273
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
335
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 ...