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
2
votes
2answers
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
1answer
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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 ...

1
2 3 4 5 6