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
7
votes
1answer
295 views

A combinatorial property of uncountable groups, II

Problem 1. Is it true that each uncountable group $G$ contains two subsets $A,B\subset G$ such that 1) for any $x,y\in G$ the intersection $xA\cap yB$ is finite and 2) for any function $\...
6
votes
1answer
181 views

A combinatorial property of uncountable groups

Let $A,B$ be two uncountable sets in a group $G$ such that for any elements $x,y\in G$ the intersection $xA\cap yB$ is finite. Let $\Phi:G\to 2^G$ be a function assigning to each element $x\in G$ some ...
10
votes
3answers
302 views

Cardinality of families of subsets of $\mathbb{N}$ whose intersections are finite

Does there exist an uncountable $P \subset \mathcal{P}(\mathbb{N}) $ with the property that for any distinct $x,y \in P$, $|x \cap y|$ is prime? A more general, but likely harder, question: is it ...
3
votes
1answer
60 views

$|V|$ and $|E|$ in hypergraphs with a separation property

Let $H=(V,E)$ be a hypergraph. We call it $T_0$ if for all $x\neq y \in V$ there is $e\in E$ with $\{x,y\}\not\subseteq E$ and $\{x,y\}\cap e\neq \emptyset$ (i.e., $e$ contains exactly one of $x,y$). ...
7
votes
2answers
261 views

Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$

Let $X$ be a set, and let $\text{Part}(X)$ denote the collection of all partitions of $X$. For $A, B\in \text{Part}(X)$ we set $A\leq B$ if $A$ refines $B$, that is for all $a\in A$ there is $b\in B$ ...
0
votes
1answer
75 views

Connected infinite graphs in which all matchings are “small”

Is there a countable, simple, connected graph $G=(\omega, E)$ such that $\text{deg}(v)$ is infinite for all $v\in \omega$, and for all matchings $M\subseteq E$ the set $V\setminus (\bigcup M)$ is ...
7
votes
5answers
368 views

Ideals on $\mathbb N$ and large sets that have small intersection

Let $\mathcal I$ be a (non-principal) ideal of subsets of $\mathbb N$. Suppose that every family $\mathcal{A} \subset \wp(\mathbb N)\setminus \mathcal I$ with the following property is countable: $$A,...
5
votes
1answer
302 views

Countable version of Erdös-Lovasz-Faber conjecture

Let $X$ be an infinite set, and let $(A_n)_{n\in\omega}$ be a collection of subsets of $X$ with the following properties: $|A_m\cap A_n| \leq 1$ for $m\neq n\in \omega$, and $|A_n|=\aleph_0$ for all $...
4
votes
2answers
264 views

Problem understanding a passage of the proof of $\mathfrak{p}=\mathfrak{t}$ involving forcing

I've a problem with a passage of the proof of Claim 14.7 of the paper "Cofinality spectrum theorems in model theory, set theory, and general topolgy" by Malliaris and Shelah, or equivalently ...
2
votes
1answer
78 views

Compactness of Hadwiger number

Is there an infinite, simple, undirected graph $G=(V,E)$ such that there is $n\in\mathbb{N}$ with the following properties? $K_n$ is a minor of $G$, but $K_{n+1}$ is not a minor of $G$, and if $F$ ...
0
votes
1answer
132 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\...
5
votes
1answer
186 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
174 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
151 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
67 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
148 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
163 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
161 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
162 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
91 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
237 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
55 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
82 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
230 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
158 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
72 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
344 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
91 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
178 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
102 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
332 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
152 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
207 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
52 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
234 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
147 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
668 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
499 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
516 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
467 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 ...
11
votes
1answer
256 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
223 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
342 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
417 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 ...