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
4 votes
1 answer
189 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
2 votes
0 answers
123 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
3 votes
0 answers
204 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
153 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
5 votes
1 answer
183 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
363 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,415
2 votes
1 answer
110 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 votes
1 answer
979 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 $\color{red}{\text{red}}$ and Bob's color is $\color{blue}{\text{blue}}$. In each step, for each $s\in S$,...
Alma Arjuna's user avatar
2 votes
1 answer
219 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
365 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
94 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
  • 40.7k
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 $...
Dominic van der Zypen's user avatar
0 votes
0 answers
107 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
129 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
777 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
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$. ...
Jiachen Yuan's user avatar
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 ...
Command Master's user avatar
6 votes
1 answer
349 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
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 ...
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
195 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
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) \...
HumbleStudent's user avatar
16 votes
2 answers
956 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
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 ...
Will Brian's user avatar
  • 17.4k
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 ...
Dominic van der Zypen's user avatar
4 votes
1 answer
163 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
900 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
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 ...
Dominic van der Zypen's user avatar
2 votes
1 answer
85 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
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 ...
Dominic van der Zypen's user avatar
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 ${\...
Dominic van der Zypen's user avatar
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 (...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 \...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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\...
saf's user avatar
  • 1,156
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 ...
n901's user avatar
  • 415
1 vote
0 answers
129 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}| > ...
Dominic van der Zypen's user avatar
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 ...
Matteo Casarosa's user avatar
0 votes
1 answer
207 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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
-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 ...
Dominic van der Zypen's user avatar
2 votes
1 answer
163 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 ...
Dominic van der Zypen's user avatar
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 \...
Matteo Casarosa's user avatar
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 ...
ARi's user avatar
  • 841
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 ...
Hannes Jakob's user avatar
  • 1,602
2 votes
1 answer
272 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}$$ ...
Dominic van der Zypen's user avatar
16 votes
0 answers
333 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 ...
Agelos's user avatar
  • 1,844
5 votes
1 answer
128 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 ...
Boaz Tsaban's user avatar
  • 3,102

1
2 3 4 5
10