Questions tagged [infinite-combinatorics]
Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.
88
questions with no upvoted or accepted answers
16
votes
0
answers
337
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 ...
13
votes
0
answers
1k
views
Hrushovski's Construction
Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s).
Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following:
(a) Trivial (...
12
votes
0
answers
226
views
Does $2^{\aleph_0}\rightarrow [\aleph_1]^2_3$ require that the continuum is weakly inaccessible?
A classic result of Sierpiński shows that $2^{\aleph_0}\nrightarrow [\aleph_1]^2_2$, that is, there is a coloring of pairs of real numbers using two colors such that both colors appear on any ...
11
votes
0
answers
458
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"...
11
votes
0
answers
265
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 $\...
11
votes
0
answers
303
views
Combinatorial Hilbert spaces
Any closed subspace $V\subset {\ell}^2(\omega)$ has associated to it a subset ${\cal S}_V$ of ${\cal P}(\omega)$, call it a combinatorial Hilbert space, namely the set of all supports of all vectors ...
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$.
...
10
votes
0
answers
155
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 ...
10
votes
0
answers
269
views
Martin's Maximum implies stationary/club Chang's conjecture?
Chang's Conjecture (CC) states: for any $f: [\omega_2]^{<\omega} \to \omega_1$, there exists a set $X\subset \omega_2$ of order type $\omega_1$ such that $|f''[X]^{<\omega}|\leq \aleph_0$.
...
10
votes
0
answers
273
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 ...
10
votes
0
answers
283
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 ...
10
votes
0
answers
493
views
Is there a model of set theory in which $\mathfrak p< \mathfrak b < \mathfrak q$?
Is there a model of set theory in which $\mathfrak p< \mathfrak b < \mathfrak q$?
Here $\mathfrak p$, $\mathfrak b$, $\mathfrak q$ are small uncountable cardinals:
$\mathfrak p$ is the ...
9
votes
0
answers
304
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 ...
9
votes
0
answers
242
views
Distributivity of certain infinite products
Suppose we have a sequence of posets $\{\mathbb P_n : n\in\omega\}$ such that for each $n$, $\mathbb P_{n+1}$ is $|\mathbb P_n|^+$-distributive. Is $\prod_{n>0} \mathbb P_n$ necessarily $|\mathbb ...
9
votes
0
answers
160
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 ...
9
votes
0
answers
250
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
372
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\...
8
votes
0
answers
203
views
ladder system uniformization at successors of singulars
Shelah proved (paper 667) that if GCH holds and $\lambda$ is singular, then for every stationary $S \subseteq \{ \alpha < \lambda^+ : \text{cf}(\alpha) = \text{cf}(\lambda) \}$, there is a ladder ...
8
votes
0
answers
239
views
Topological applications of $\mathfrak{p}=\mathfrak{t}$
I'm working on the Malliaris-Shelah's recent result of $\mathfrak{p}=\mathfrak{t}$, but I'm more interested in what possible topological applications can derivate from this equality.
Searching in ...
8
votes
0
answers
190
views
Specializing fat trees
The discussion is about trees of height $\omega_1$ that are not necessarily thin, namely, no cardinality constraints on the size of each level. A classcial theorem of Baumgartner states that it is ...
8
votes
0
answers
435
views
The minimum cardinality of an almost disjoint reaping family
The following cardinal arose in the discussion surrounding the question posed here by Dominic van der Zypen:
Define $\kappa$ to be the minimum cardinality of a family $\mathcal{A}$ of infinite ...
8
votes
0
answers
285
views
Higher dimensional $\Delta$-system lemma
Consider the following statement (called $\Delta^d(\kappa^+, \lambda)$ where $d\in \omega$ and $\kappa<\lambda$ are cardinals): For every $A': [\lambda]^d\to [\lambda]^{\leq \kappa}$, there exist $...
8
votes
0
answers
369
views
Baire category of tall ideals
Problem. Is it consistent with ZFC that $\mathfrak t=\omega_1$ and each $\omega_1$-generated tall $P$-ideal is of the second Baire category?
(Asked 01.10.2016 by David Chodounsky at page 20 of Volume ...
7
votes
0
answers
130
views
Better scales and Failures of SCH
Assume $\mu$ is a singular cardinal of countable cofinality. Recall that a scale for $\mu$ consists of an increasing sequence $\vec{\mu}$ of regular cardinals $\langle \mu_n:n<\omega\rangle$ ...
7
votes
0
answers
150
views
A non-special Aronszajn tree with a stationary set that is non-stationary with respect to the tree
Is there any example of a ($\omega_1$-)Aronszajn tree $T$ that is non-special and there exists a stationary subset $S\subset \omega_1$ such that $S$ is not stationary with respect to $T$?
A tree ...
6
votes
0
answers
145
views
Combinatorial characterizations of potentially countably chromatic graphs
Is there a combinatorial characterization of (uncountably chromatic) graphs that are "potentially" countably chromatic? By this I mean: $G=(V,E)$ is a graph such that there exists a cardinal ...
6
votes
0
answers
238
views
A possible characterization of weakly compact cardinals
Aside from the well-known characterization of weakly compact cardinals in terms of the usual partition calculus, I've been wondering if there are other characterizations that are variants of the ...
5
votes
0
answers
113
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 ...
5
votes
0
answers
143
views
Ramsey-theoretic properties of Erdős cardinals
The $\beta$-Erdős cardinal is defined as the least ordinal $\eta$ such that $\eta \to (\beta)^{\lt \omega}_2$, that is for every function $f: [\eta]^{\lt \omega} \to 2$, there is an $f$-homogeneous ...
5
votes
0
answers
145
views
Existence of a large family of sets with big differences
Let $\lambda\leq\kappa$ be two cardinals and $\Gamma$ be a set with $|\Gamma|=\kappa$.
Question. Does there exist a family $\mathscr{A}\subseteq \{A\subseteq \Gamma: |A|=\lambda\}$ with $|\mathscr{A}|...
5
votes
0
answers
304
views
A question on infinite arithmetic progressions
I was working on a problem that consisted of deciding if the language a finite automaton (the alphabet of which is $\{0,1\}$ and the words accepted are binary encoded positive integers) contains an ...
5
votes
0
answers
168
views
Can maximal filters of nowhere meager subsets of Cantor space be countably complete?
Let $X$ denote Cantor space. A subset $A\subseteq X$ is nowhere meager if for every non-empty open $U\subseteq X$, we have $A\cap U$ non-meager. We call $\mathcal{F}\subseteq \mathcal{P}(X)$ a maximal ...
5
votes
0
answers
178
views
Graph of number pairs summing to a square number
Consider the set $\mathbb{Z}_+$ of positive integers and set $E = \big\{\{a,b\}: a\neq b\in\mathbb{Z}_+ \text{ and there is } n\in\mathbb{Z}_+: a+b = n^2\big\}$.
Does the graph $G=(\mathbb{Z}_+,E)$ ...
5
votes
0
answers
159
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 ...
5
votes
0
answers
166
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 ...
5
votes
0
answers
156
views
Consistency of monochromatic uniformization at an inaccessible cardinal
Let $\kappa$ be an inaccessible cardinal, is the following uniformization principle at $\kappa$ consistent (is it consistent with GCH?): there exists a ladder system $\langle A_\alpha\subset \alpha: \...
5
votes
0
answers
118
views
A question about the products of power set sigma algebras
Let $\kappa$ be the least cardinal for which the sigma algebra generated by $\{A \times B: A,B \subseteq \kappa\}$ does not contain every subset of $\kappa \times \kappa$. It is known that $\kappa$ is ...
5
votes
0
answers
135
views
Almost-disjoint sequence of sets at singular cardinals and stationary reflection
Let $\mu$ be a singular cardinal of countable cofinality. Let $ADS_\mu$ be the assertion that there exists $\langle A_\alpha\subset \mu: \alpha<\mu^+\rangle$ such that for all $\beta<\mu^+$, ...
4
votes
0
answers
219
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) \...
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 ...
4
votes
0
answers
124
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\...
4
votes
0
answers
193
views
Bailey's lemma in number theory
A pair of sequences $(α_n,β_n)$ is called a Bailey pair if they are related by
$$\beta_n=\sum_{r=0}^n\frac{\alpha_r}{(q;q)_{n-r}(aq;q)_{n+r}}$$
or equivalently
$$\alpha_n = (1-aq^{2n})\sum_{j=0}^n\...
4
votes
0
answers
177
views
Okada-Schur functions and the Martin boundary of the Young-Fibonacci lattice
This question is related to three earlier posts addressing properties of the Young-Fibonacci lattice $\Bbb{YF}$, namely:
Differential posets, the Plancherel state $\varphi_\mathrm{P}$, and minimality
...
4
votes
0
answers
127
views
Graphs without maximal vertex-transivite subgraphs
The axiom of choice is of no use when trying to prove that every vertex-transitive subgraph is contained in a maximal vertex-transitive subgraph, because a union of an ascending chain of vertex-...
4
votes
0
answers
161
views
Tileability and computabilty
Let $n>2$ be an integer. We consider $n$ pairs $(x_1,y_1),\dotsc,(x_n,y_n)$ in $\mathbb{N}^2$, and the polygon defined by drawing a straight line from $(x_k, y_k)$ to $(x_{k+1},y_{k+1})$ and from $(...
4
votes
0
answers
116
views
Infinite $3$-chromatic hypergraphs
Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say the hypergraph $H$ is $\kappa$-chromatic if there is a function $c:V\to\kappa$ such that for all $e\in E$ the restriction $c|_e$ ...
4
votes
0
answers
166
views
Partial orders with separable linear extensions
Is the following consistent?
CH fails and there is a partial order $\preceq$ on $\omega_2$ such that for every $\alpha < \omega_2$, $(\alpha, \preceq)$ can be extended to a separable linear order $...
4
votes
0
answers
189
views
Status of the dense-set version of the Halpern–Läuchli theorem
The Halpern–Läuchli theorem theorem of dimension $d\in \omega+1$ is the following strong Ramsey theoretic statement:
Given $k\in \omega$ and $d$ perfect finitely branching subtrees $T_i, i<d$ ...
3
votes
0
answers
150
views
A p-point game with infinitely many ultrafilters
The following game-theoretic characterization of p-points is well known:
Theorem A. An ultrafilter $D$ on the set $\omega$ of natural numbers is a p-point if and only if player I does not have a ...
3
votes
0
answers
119
views
Greatly Erdős and Erdős cardinals
Sharpe and Welch 2011 define $\alpha$-weakly Erdős and greatly Erdős cardinals as follows:
Let $\kappa$ have uncountable cofinality, and let $\mathcal{A}$ be a $\kappa$-structure, $X \subseteq \kappa$...