Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.
0
votes
1answer
70 views

Can the union of difference sets in towers equal $\omega$?

We write $A\subseteq^* B$ if $A\setminus B$ is finite. Let $(A_n)_{n\in\omega}$ be a sequence of subsets of $\omega$ such that for all $n\in\omega$ we have $A_n \subseteq^* A_{n+1}$ and $A_{n+1}\not\...
3
votes
1answer
120 views

On filters possessing a countable network

Let $\mathcal F$ be a free filter on $\omega$ and $$\mathcal F^+:=\{E\subset \omega:\forall F\in\mathcal F\;E\cap F\ne\emptyset\}.$$ A family $\mathcal N$ of subsets of $\omega$ is called a network ...
4
votes
1answer
115 views

Minimal covers in hypergraphs with finite edges

Let $H=(V,E)$ be a hypergraph. We say that $C\subseteq E$ is a cover if $\bigcup C = V$. Let $H$ be a hypergraph with the following properties: $\bigcup E = V$, all members of $E$ are finite, and $d,...
2
votes
1answer
148 views

Maximality with respect to the splitting property

Let $X$ be a set and ${\cal P}(X)$ its powerset. We say that ${\cal F} \subseteq {\cal P}(X)$ has the splitting property (SP) if there is $A\in {\cal P}(X)$ such that for all $F\in {\cal F}$ we have $$...
2
votes
1answer
60 views

Example of self-dual hypergraph with infinite edges

What is an example of a hypergraph $H=(V,E)$ with $|e|\geq \aleph_0$ for all $e\in E$ and the property that $H\cong H^*$ where $H^*$ is the dual hypergraph of $H$?
5
votes
1answer
142 views

“König's theorem” for $T_2$-spaces?

For any topological space $(X,\tau)$ we define a matching to be a collection of non-empty and pairwise disjoint open sets. We define the matching number $\nu(X,\tau)$ to be the smallest cardinal $\...
1
vote
2answers
159 views

Bipartite subgraphs with lots of edges

Suppose $G=(V,E)$ is a simple, undirected graph with $|V|,|E|$ infinite. Is there $B\subseteq E$ with $|B| = |E|$ such that $(V,B)$ is bipartite?
2
votes
1answer
157 views

Infinite graph with lots of non-isomorphic induced subgraphs

Given an infinite cardinal $\kappa$, is there a graph on $\kappa$ vertices that contains $2^\kappa$ pairwise non-isomorphic induced subgraphs?
4
votes
1answer
160 views

Indecomposable ordinals and pseudointersection

Is the following claim correct (Chapter 13 before Theorem 87 of Todorcevic's book: Notes on forcing axioms): Let $\alpha$ be an infinite countable indecomposable ordinal and $U$ be an uniform ...
3
votes
0answers
83 views

Hall's Marriage Theorem When the Set of Men Has Singular Cardinality $\kappa$ and Each Man Knows at Most $\kappa$ Women

Let $\cal F=(A_i)_{i\in\kappa} $ be a family of sets indexed by a set $\kappa$. A $transversal$ is a one-to-one function $f$ from $\kappa$ to $\bigcup_{i\in\kappa} A_i$ such that for all $i\in\kappa$,...
8
votes
1answer
230 views

Is there a function from a Suslin tree to itself which send compatible elements to incompatible elements?

We say $S$ is a Suslin forest if adding a minimum to $S$ we have a Suslin tree. So a Suslin Forest is essentially a Suslin tree $S$ in which we drop the requirement for $S$ to have a single root. ...
1
vote
1answer
51 views

Infinite connected $k$-regular graphs

Is it true that for any integer $k\geq 3$ there are $\aleph_0$ many connected countably infinite, pairwise non-isomorphic $k$-regular graphs?
1
vote
1answer
80 views

Infinite connected graphs isomorphic to their line graph

For any simple, undirected graph $G$, let $L(G)$ denote its line graph. $G=(\mathbb{Z}, E)$ with $E = \{\{k, k+1\}:k\in \mathbb{Z}\}$ has the property that $G\cong L(G)$. Is there a connected ...
3
votes
2answers
222 views

Orientability of $\mathbb{Z}^n$

For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are ...
2
votes
1answer
97 views

$\omega$-Hamilton paths in $\mathbb{Z}^n$

For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are ...
5
votes
1answer
154 views

Negation of CH implied by lots of special subtrees?

In the following, I focus on trees of height $\omega_1$: if there exists a nonspecial tree any of whose $\aleph_1$-subtrees is special, must CH fail? Some neither consistent nor coherent thoughts: ...
2
votes
1answer
71 views

Minimal cutting sets in connected graphs

Let $G=(V,E)$ be a simple, undirected and connected graph. We say that $S\subseteq V$ is a cutting set if $S\neq V$ and the induced subgraph on $V\setminus S$ is not connected any more. If $S \...
2
votes
2answers
141 views

Injective, but no bijective neighborhood map

The concept of neighborhood maps was looked at in a previous question. Let $G= (V,E)$ be a simple, undirected graph. For $v\in V$ we set $N(v) = \{w\in V: \{v,w\} \in E\}$. Note that we always have $...
9
votes
0answers
338 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 ...
3
votes
0answers
89 views

Singular compactness for stationary reflection?

Let $\lambda\geq \omega_2$ be a regular cardinal. The weak reflection principle for $[\lambda]^\omega$ ($WRP([\lambda]^\omega)$) asserts that for any stationary $S\subset [\lambda]^\omega$ there ...
8
votes
1answer
171 views

Is there a non-atomic finite positive measure in the plane, of which uncountably many projections have atoms?

I would like to know whether or not there exists a finite probability measure $\mu$ on $\mathbb R^2$ which has no atoms, but such that there exists an uncountable set $A\subset \mathbb S^1$, such that ...
4
votes
0answers
101 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-...
-2
votes
1answer
330 views

Infinite graphs with large degree but no perfect matching [duplicate]

Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ ...
7
votes
0answers
149 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 ...
5
votes
1answer
205 views

Simultaneous failure of weak diamond

Let $\lambda$ be an infinite cardinal. Recall that Weak diamond $\Phi_S$ on $S\subseteq\lambda^+$ is the following principle: For every function $F:2^{<\lambda^+}\rightarrow 2$, there exists $g\in ...
1
vote
1answer
51 views

Strong and weak chromatic number of infinite bounded hypergraphs

This is a follow-up of an older question. Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak ...
1
vote
1answer
58 views

Strong and weak chromatic number of infinite hypergraphs of finite rank

Let $H = (V, E)$ be a hypergraph such that every member of $E$ has more than $1$ element. Let $\kappa$ be a cardinal. We say that $c: V\to \kappa$ is a weak coloring if for all $e \in E$ the ...
7
votes
1answer
231 views

PCF theory and good points in scales

If $\kappa$ is a singular cardinal, a scale for $\kappa$ consists of an increasing sequence $\langle \kappa_i : i < \mathrm{cf}(\kappa) \rangle$ converging to $\kappa$ and a sequence of functions $\...
4
votes
0answers
146 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 $(...
19
votes
1answer
659 views

On Erdos-Kakutani like Equivalents of the Failure of Continuum Hypothesis

Among all mysterious equivalents of the Continuum Hypothesis and its negation, there is an algebraic combinatorial equivalent of the $\neg CH$ by Erdos and Kakutani (MR0008136) as follows: ...
5
votes
0answers
115 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^+$, ...
3
votes
2answers
304 views

Graph of functions sharing a point

This is a variation of an older question in a more general setting. Let $V$ denote the set of all functions $f:\omega\to \omega$. We say $f,g\in V$ share a point if there is $x\in X$ such that $f(x) =...
6
votes
0answers
130 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 ...
10
votes
2answers
490 views

Does $\diamondsuit(\kappa)$ provably hold at Woodins or inaccessible Jónssons $\kappa$?

Usually the question whether the diamond principle $\diamondsuit(\kappa)$ holds for some large cardinal $\kappa$ only concerns large cardinal notions of very low consistency (among the weakly compacts)...
15
votes
3answers
506 views

Dominating families in bigger cardinals

A dominating family on $\omega^\omega$ is a set $\mathcal D \subset \omega^\omega$ such that for every $f \in \omega^\omega$ there exists $g \in \mathcal D$ such that $f<^* g$ (that is, $f(n)<g(...
9
votes
1answer
458 views

“Towers” on singular cardinals with countable cofinality

Let $\lambda$ be a singular cardinal of countable cofinality. Is there necessarily a sequence $\{A_\alpha\mid\alpha<\lambda^+\}$ of countable subsets of $\lambda$, such that $\alpha<\beta$ if ...
10
votes
1answer
251 views

Ways to add Aronszajn trees which are neither Souslin nor special

By an Aronszajn tree, I mean a tree of height $\omega_1$ with countable levels and no branch. Such a tree is Souslin if it has no uncountable antichains and special if it can be written as the ...
7
votes
1answer
220 views

Iterated forcing and the super tree property at $\omega_2$

It is a theorem of Baumgartner and Laver that iterating Sacks forcings of weakly compact length gives rise to the tree property at $\omega_2$. Natural questions (at least for me) are: do we get ...
6
votes
1answer
340 views

Historical question about the $\aleph_2$-Souslin hypothesis

For an uncountable regular cardinals $\kappa,$ let $\kappa$-Souslin hypothesis, denoted $SH(\kappa)$ be the assertion that there are no $\kappa$-Souslin trees. By a result of Jensen, $GCH+SH(\aleph_1)...
17
votes
1answer
415 views

Is there an infinite set $X$ such that for every isotone $f\colon[X]^\omega\to[X]^\omega$ there is a free decreasing sequence?

(Pierre Gillibert asked me this question and I post it with his permission.) Let $X$ be an infinite set, and $f\colon[X]^\omega\to[X]^\omega$. We say that $\{x_n\mid n<\omega\}\subseteq X$ is a ...
7
votes
2answers
309 views

Infinite projective plane with small edges

Let $\kappa$ be an infinite cardinal. We say $E\subseteq {\cal P}(\kappa)$ is an infinite projective plane on $\kappa$ if $e_1\neq e_2\in E$ implies $|e_1\cap e_2| = 1$, and whenever $n\neq m\in \...
-4
votes
1answer
118 views

Connected infinite graph $G$ with $\delta(G)\geq 2$ and no perfect matching [closed]

Is there a connected infinite graph $G=(V,E)$ such that $\text{deg}(v) \geq 2$ for all $v\in V$, and $G$ possesses no perfect matching?
-2
votes
1answer
80 views

Partitioning finite hypergraphs with edges [closed]

Let $H=(V,E)$ be a hypergraph such that $|V|$ is infinite, and the following statements hold: if $a\neq b\in E$ then $|a\cap b|\leq 1$, and every vertex $v\in V$ is contained in at least $2$ members ...
1
vote
1answer
71 views

Matchings in graphs with infinite chromatic number

Is there a simple, undirected graph $G= (V,E)$ with $\chi(G) \geq \aleph_0$, and if $M\subseteq E$ is a matching then $|M|<\chi(G)$?
1
vote
1answer
67 views

Choice sets in covers with small intersections

Let $X\neq \emptyset$ be a set. We say ${\cal C} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ is a cover of $X$ if $\bigcup {\cal C} = X$. A subset $S\subseteq X$ is a choice set for ${\cal C}$ if $|S\...
-2
votes
1answer
57 views

Edge covers of graphs with $\chi(G) \geq \aleph_0$

If $G=(V,E)$ is a simple, undirected graph, then $C\subseteq V$ is an edge cover if $C\cap e \neq \emptyset$ for all $e\in E$. Let $G=(V,E) $ be a graph with infinite chromatic number. Is every edge ...
2
votes
3answers
131 views

Infinite strongly rigid graphs

Is there an infinite connected simple undirected graph $G=(V, E)$ such that the identity map $\text{id}_V: V\to V$ is the only graph self-homomorphism from $G$ to itself? (A graph self-homomorphism ...
2
votes
1answer
84 views

Edge covers in infinite graphs

If $G=(V,E)$ is a simple, undirected graph, then $C\subseteq V$ is an edge cover if $C\cap e \neq \emptyset$ for all $e\in E$. The "best" covers in some sense are subsets $C\subseteq V$ that meet ...
3
votes
1answer
143 views

Subcovers without a choice set

Let $X\neq \emptyset$ be a set. We say ${\cal C} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ is a cover if $\bigcup {\cal C} = X$. A subset $D\subseteq X$ is a choice set for ${\cal C}$ if $|D\cap c| ...
1
vote
1answer
131 views

Choice sets in “thick” sets of sets

Let $X\neq \emptyset$ be a set and let ${\cal S} \subseteq {\cal P}(X)\setminus\{\emptyset\}$ be a collection of non-empty subsets of $X$. We say $C\subseteq X$ is a choice set for ${\cal S}$ if for ...