# Questions tagged [infinite-combinatorics]

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

260
questions

**2**

votes

**2**answers

99 views

### Are complete regular linear hypergraphs on $\omega$ isomorphic?

If $H_i = (V_i, E_i)$ are hypergraphs for $i=1,2$ then we say they are isomorphic if there is a bijection $f: V_1 \to V_2$ such that for $A \subseteq V_1$ we have $$A\in E_1 \text{ if and only if } f(...

**-1**

votes

**1**answer

65 views

### Subset of $[\kappa]^{<\kappa}$ with linear intersection

For any cardinal $\kappa$, let $[\kappa]^{<\kappa}$ denote the collection of subsets of $\kappa$ with cardinality $<\kappa$. Is there an infinite cardinal $\kappa$ and ${\cal C}\subseteq [\kappa]...

**-2**

votes

**1**answer

66 views

### Infinite complete linear hypergraphs with edges of different sizes

Is there an infinite cardinal $\kappa$ with a collection of subsets ${\cal E}$ of $\kappa$ with the following properties?
$\bigcup {\cal E} = \kappa$,
$e \neq f \in {\cal E}$ implies $|e \cap f|=1$
$|...

**2**

votes

**0**answers

74 views

### Generalized partitions

Let $\kappa>0$ be a cardinal and $X$ be a set. We set $[X]^\kappa = \{A \in {\cal P}(X): |A| = \kappa\}$.
If ${\cal A}\subseteq {\cal P}(X)$ we say that ${\cal B} \subseteq {\cal P}(X)$ is an ${\...

**5**

votes

**2**answers

190 views

### Slicing up $\mathbb{N}\setminus\{1\}$

Let $\mathbb{N}$ denote the set of positive integers. For any prime $p\in\mathbb{N}$ let $p\mathbb{N} = \{np: n\in \mathbb{N}\}$. Is there a partition ${\cal P}$ of $\mathbb{N}\setminus\{1\}$ such ...

**3**

votes

**0**answers

38 views

### Maximum partite subset of edges of a hypergraph

If $X\neq \varnothing$ is a set we say that ${\frak P} \subseteq {\cal P}(X)$ is a partition of $X$ if
$\bigcup{\frak P} = X$, and
$P\neq Q \in {\frak P} \implies P\cap Q = \varnothing$.
Let $H = (V,...

**3**

votes

**1**answer

74 views

### Graph structure on $S_\omega$ induced by fixed points on compositions

Let $S_\omega$ denote the collection of bijections $f:\omega\to\omega$. We say that $f \in S_\omega$ has a fixed point if there is $x\in \omega$ with $f(x) = x$.
It is a short exercise to show that ...

**10**

votes

**0**answers

211 views

### How wealthy are canonical inner models?

One of the way a person shows their wealth is by having many diamonds. The same can be said about models of $\sf ZFC$. We can add generic diamond sequences, while preserving the old ones, so in some ...

**8**

votes

**1**answer

248 views

### On the utility of Silver machines

This question arises out of having Devlin's Constructibility [1] in my collection of books at home during the lockdown. Chapter IX of the book deals with Silver machines, which are presented as ...

**2**

votes

**1**answer

156 views

### Collection of pairwise non-isomorphic infinite self-complementary graphs

For any set $X$ let $[X]^2 = \big\{\{a,b\}: a\neq b\in X\big\}$. We say that a graph $G$ is self-complementary if $G\cong \bar{G}$ where $\bar{G} = (V, [V]^2\setminus E)$.
Given an infinite cardinal ...

**4**

votes

**1**answer

140 views

### What is the smallest cardinality of a maximal ultrafamily of infinite subsets of $\omega$?

A family $\mathcal U$ of infinite subsets of $\omega$ is called an ultrafamily if for any sets $U,V\in\mathcal U$ one of the sets $U\setminus V$, $U\cap V$ or $V\setminus U$ is finite.
By the ...

**1**

vote

**1**answer

170 views

### Borel hierarchy and tail sets

Let $A$ be a finite set, and let $A^\infty$ be the set of all sequences $(a_n)_{n=1}^\infty$ of elements of $A$.
A set $B \subseteq A^\infty$ is a tail set if for every two sequences $\vec a, \vec b \...

**-1**

votes

**1**answer

65 views

### Minimal covering sets of continuous endomorphisms

For any topological space $(X,\tau)$, let $\text{End}(X)$ denote the set of continuous functions $f:X\to X$. We say that ${\cal C}\subseteq \text{End}(X)$ covers $\text{End}(X)$ if for every $f\in \...

**5**

votes

**1**answer

146 views

### Strong chains in $[\omega_2]^{\omega_2}$ mod finite of length $\omega_3$

Probing a bit the difference between $[\omega_1]^{\omega_1}$ and $[\omega_2]^{\omega_2}$ modulo the finite sets:
Question
Can there exist a family $\langle X_\alpha:\alpha<\omega_3\rangle$ ...

**10**

votes

**0**answers

231 views

### Monotone subsets of uncountable plane sets

Let $S$ be an uncountable set of points in the Euclidean plane. Define a subset of $S$ to be upward-monotone if every two points determine a line with non-negative slope, and downward-monotone if ...

**3**

votes

**1**answer

89 views

### Continuous function covers in connected $T_2$-spaces

If $X$ is a topological space, we let $\text{End}(X)$ be the collection of continuous functions $f:X\to X$. We say that $f,g\in \text{End}(X)$ meet if there is $x\in X$ with $f(x) = g(x)$. We say that ...

**2**

votes

**1**answer

137 views

### Increasing the “shuffling distance” by iterating a permutation $\varphi: \omega \to \omega$

Motivation. I was wondering about the following when playing a card-shuffling game with my elder son.
If $\varphi: \omega \to \omega$ is a bijection, we define the shuffling distance of $\varphi$ by $...

**9**

votes

**0**answers

128 views

### Strong Chains in $^{\omega_1}\omega_1$ of length $\omega_3$

In a previous question, I asked about the impact of strong chains in $^{\omega_1}\omega_1$ (e.g., sequences of functions $\langle f_\alpha:\alpha<\kappa\rangle$ in $^{\omega_1}\omega_1$ that are ...

**6**

votes

**1**answer

148 views

### Minimal generating set for $S_\omega$

If $G$ is a group and $S\subseteq G$, let $\langle S \rangle$ be the intersection of all subgroups of $G$ containing $S$.
Let $S_\omega$ denote the group of all bijections $f:\omega\to\omega$ with ...

**0**

votes

**1**answer

150 views

### A nonprincipal ultrafilter that is not a $p$-point

On pg 76 of Jech's Set Theory, he proves the existence of a nonprincipal ultrafilter on $\omega$ that is not a $p$-point.
Given a partition $\{A_n\}$ of $\omega$ into $\aleph_0$ infinite pieces, ...

**1**

vote

**1**answer

138 views

### A converse of the Erdős-De Bruijn Theorem?

For the chromatic number $\chi(G)$ of a simple, undirected graph, there is a "compactness" theorem by Erdős and De Bruijn stating that if an infinite graph $G$ has finite chromatic number, then there ...

**5**

votes

**0**answers

122 views

### Strong chains of uncountable functions and cardinal characteristics

A family of functions $\langle f_\alpha:\alpha<\kappa\rangle$ from $\omega_1$ to $\omega_1$ is called a strong chain if $\alpha<\beta<\kappa\Longrightarrow \{\xi<\omega_1: f_\beta(\xi)\leq ...

**7**

votes

**0**answers

151 views

### $\Sigma^2_2$ absoluteness and $\diamondsuit$

This question touches on recent questions concerning the role of $\diamondsuit$ and the Continuum Hypothesis. In particular, I would like to know more information about a conjecture of Woodin on the ...

**9**

votes

**0**answers

311 views

### On the role of $\diamondsuit$

The well-known axiom $\diamondsuit$ states that there is a sequence $\langle A_\alpha:\alpha<\omega_1\rangle$ (a $\diamondsuit$-sequence) of countable sets with the property that for any $A\...

**11**

votes

**0**answers

293 views

### $\Sigma^2_1$ and the Continuum Hypothesis

This is a follow up to Will Brian's answer to this recent question. In particular, quoting Brian:
"In fact, Paul Larson has pointed out to me that the statement "$\phi$ and $\phi^{-1}$ are conjugate"...

**1**

vote

**1**answer

120 views

### Coloring $\mathbb{N}$ such that $\{a, b, a+b\}$ is not monochromatic

Let $\mathbb{N}:=\omega \setminus \{0\}$. Is there $k\in \mathbb{N}$ and a map $c:\mathbb{N}\to \{1,\ldots,k\}$ such that for all $a,b\in\mathbb{N}$ the restriction $c|_{\{a,\,b,\,a+b\}}$ is non-...

**5**

votes

**1**answer

302 views

### Calculate the $\downarrow$, $\downarrow\uparrow$ and $\uparrow\downarrow$ cofinalities of the poset of nontrivial finitary partitions of $\omega$

Let $(P,\le)$ be a poset. For a point $x\in P$ let
$${\downarrow}x=\{p\in P:p\le x\}\quad\text{and}\quad{\uparrow}x=\{p\in P:x\le p\}$$be the lower and upper sets of the point $x$, and for a subset $...

**1**

vote

**1**answer

91 views

### Bounding and dominating numbers for preordering $\leq^*$ on bijections $f:\omega\to\omega$

For functions $f, g:\omega\to\omega$ we write $f \leq^* g$ if $\{x\in\omega: f(x)> g(x)\}$ is finite.
Let $S_\omega$ denote the collection of bijections $\varphi:\omega\to\omega$ Similarly to the ...

**1**

vote

**1**answer

70 views

### Thinning directed sets ${\frak P}$ of partitions of $\omega$ with no ${\frak P}$-discrete subsets

This question branches from Taras Banakh's recent question on a cardinal characteristic connected to families of partitions that are directed in the ordering of partition refinement.
A partition $\...

**14**

votes

**2**answers

335 views

### Consequences of existence of a certain function from $\omega_1$ to $\omega_1$

In his book [1], Paul Larson remarks (Remark 1.1.22) that in L there is a function $h:\omega_1\rightarrow\omega_1$ such that for any countable elementary submodel $X$ of $V_\gamma$ (where $\gamma$ is ...

**3**

votes

**1**answer

144 views

### Suslin representation of sets and limits to Shoenfield's Absoluteness

For any natural number $k \in \omega$ and any set $X$ the set $$T \subseteq \bigcup_{m \in \omega} (\omega^m)^k \times X^m $$ is a tree on $\omega^k \times X$ iff
$$(t_o, \ldots, t_k) \in T \: \...

**3**

votes

**1**answer

88 views

### Meetability of $\pm 1$-functions on $\omega$

If ${\cal S}$ is a collection of functions $f:\omega\to\omega$ we say that ${\cal S}$ is meetable if there is a "global function" $g:\omega\to \omega$ such that for every $f\in {\cal S}$ there is $n\...

**5**

votes

**1**answer

185 views

### Relationship between “infinitely unequal” and “eventually different”

Suppose that $\kappa$ has the property that for every family $A\subseteq\omega^{\omega}$, if $|A|<\kappa$, then there exists some $g\in\omega^{\omega}$ such that for any $f\in A, \exists^{\infty}n\;...

**1**

vote

**1**answer

142 views

### A balancing property of infinite subsets of $\mathbb{N}$

Let $\omega$ denote the set of non-negative integers and let $[\omega]^\omega$ be the collection of infinite subsets of $\omega$.
If $S\in [\omega]^\omega$ and $A\subseteq \omega$ we say that $A$ is ...

**1**

vote

**1**answer

173 views

### Subset of $[\omega]^\omega$ that can be “colored” with $3$, but not $2$ colors

Let $[\omega]^\omega$ denote the set of infinite subsets of $\omega$.
Let $S\subseteq [\omega]^\omega$. We say that a map $c:\omega \to \{0,\ldots,n-1\}$ is a coloring for $S$ with $n$ colors if ...

**5**

votes

**0**answers

161 views

### Cardinals realizable by the chromatic number of a regular hypergraph

For any set $X$ and cardinal $\kappa$, we denote by $[X]^\kappa$ the collection of subsets of $X$ having cardinality $\kappa$.
If $H=(V,E)$ is a hypergraph, and $\kappa$ is a cardinal, we say that a ...

**7**

votes

**1**answer

165 views

### Aronszajn Trees when AC fails

This question may be easy and indicative of my ignorance about the failure of the axiom of choice. If so, I apologize. Below assume $\mathsf{DC}$ but not $\mathsf{AC}$. Suppose we have a partial order ...

**0**

votes

**1**answer

134 views

### Are hypergraphs $H=(V,E)$ with $|E|=|V|$ $2$-colorable?

A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal, such that for ...

**11**

votes

**0**answers

217 views

### Preservation of chain condition under strategically closed forcing

It is well-known that $\kappa$-closed forcing preserves $\kappa$-c.c. posets. The same argument works for $\kappa$-strategically closed forcing. Here is the definition:
A poset $\mathbb P$ is $\...

**10**

votes

**1**answer

125 views

### Is there a topological group with the small index property that does not have automatic continuity?

Here are the exact definitions of the terms:
Let $G$ be a topological group.
Then $G$ has the small index property if every subgroup of countable (including finite) index is open in $G$. Furthermore,...

**1**

vote

**1**answer

39 views

### Minimally connected hypergraphs

Let $H=(V,E)$ be a hypergraph, where $V\neq \emptyset$ is a set, and $E\subseteq {\cal P}(V)$. We say that $H$ is connected if whenever $S\subseteq V$ with $\emptyset \neq S \neq V$, there is $e\in E$ ...

**4**

votes

**1**answer

54 views

### Sizes of matchings and transversals in hypergraphs

Let $H=(V,E)$ be a hypergraph. We call $H$ proper if $E\neq\emptyset, \emptyset \notin E$ and for no $e_1\neq e_2\in E$ we have $e_1\subseteq e_2$. A matching is a set $M$ of pairwise disjoint edges (...

**1**

vote

**2**answers

122 views

### Clutters with no maximum-size matchings

A clutter is a pair $C=(V,E)$ where $V\neq\emptyset$ is a set, and $E\subseteq {\cal P}(V)$ such that no member of $E$ is included in another member of $E$. A matching in $C$ is a collection of ...

**3**

votes

**1**answer

58 views

### Is $S_\omega/F_\omega$ embeddable to $S_\omega$?

Let $S_\omega$ be the group of bijections $f:\omega\to\omega$, and let $F_\omega = \{\pi\in S_\omega: \exists N\in \omega(\pi(k) = k \text{ for all } k\geq N)\}$. It is easy to see that $F_\omega$ is ...

**2**

votes

**1**answer

82 views

### Ramsey type properties of $F_\sigma$ ideals

Let $I \subseteq 2^\omega$ be any $F_\sigma$ ideal containing every finite sets :
$\forall X \in I\ \forall Y \subseteq X\ \text{ we have } Y \in I$
$\forall k\ \forall X_1,\dots,X_k \in I\ X_1 \cup \...

**3**

votes

**1**answer

48 views

### Connected hypergraphs

We say that a hypergraph $H=(V,E)$ is connected if the following condition holds:
for all $S\subseteq V$ with $\emptyset\neq S \neq V$ there is $e\in E$ that meets both $S$ and $V\setminus S$, i.e. ...

**2**

votes

**1**answer

71 views

### Chromatically rigid hypergraphs

If $H=(V,E)$ is a hypergraph and $\kappa$ is a cardinal, then $c:V\to\kappa$ is a coloring if for every $e\in E$ with $|e|>1$, the restriction $c|_e:e \to \kappa$ is non-constant. By $\chi(H)$ we ...

**4**

votes

**0**answers

42 views

### Generalization of Menger's Theorem to Infinite Graphs

Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets A and B, there is a family F of disjoint paths from A to B and a set separating B from A consisting ...

**0**

votes

**2**answers

187 views

### Collection $\cal{C}$ of uncountable subsets of $\mathbb{R}$ such that every countable subset is contained in exactly one member of $\cal{C}$

If $\kappa$ is a cardinal and $X$ is a set, let $[X]^\kappa$ denote the collection of subsets of $X$ that have cardinality $\kappa$.
Let $\beta>\omega$ and $\beta \leq 2^{\omega}$. Is there ${\cal ...

**1**

vote

**1**answer

40 views

### Induced subgraphs of the line graph of a dense linear hypergraph

Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$
We ...