The infinite-combinatorics tag has no usage guidance.

**0**

votes

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**2**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**3**answers

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

**1**answer

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

**1**answer

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

**1**answer

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 ...