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

Questions tagged [infinite-combinatorics]

4
votes
0answers
118 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 ...
2
votes
2answers
117 views

Infima and suprema in the “transfer” function ordering

Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the ...
0
votes
0answers
38 views

Partitioning an infinite set into fixed number of sets [closed]

Suppose we have a set of size $\kappa$, and want to partition it into $\mu$ sets, where $\kappa$ is an infinite cardinal, and $1<\mu\leq\kappa$. I am aware that it can be done in $2^\kappa$ ways (...
5
votes
1answer
210 views

On the “infinitely often in” relation between subsets of $\mathbb{N}$

Let ${\mathbb N}$ denote the set of positive integers, let $A,B\subseteq \mathbb{N}$. For $n\in\mathbb{N}$ we set $n+A:=\{n+a: a\in A\}$. We say that $A$ is infinitely often in $B$ if the set $$\big\{...
3
votes
1answer
130 views

Induced minors of $\{0,1\}^\omega$

Let $G=(V,E)$ be a simple, undirected graph. Suppose that ${\cal S}$ is a collection of non-empty, connected, and pairwise disjoint subsets of $V$. Let $G({\cal S})$ be the graph with vertex set ${\...
1
vote
1answer
60 views

Enumerating isomorphic subgraphs

For digraphs $G$ and $H$ if we can partition $V(G)$ into a family $\{Q_t\}_{t\in V(H)}$ indexed by $V(H)$ such that $E(G)=\bigcup_{(u,v)\in E(H)}Q_u\times Q_v$, then is every subgraph of $G$ ...
0
votes
1answer
71 views

Finding a good transversal basis

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...
1
vote
1answer
136 views

On a combinatorial set covering property

Let $\kappa < \lambda < \mu$ be infinite cardinals. Is there a collection ${\cal U}\subseteq {\cal P}(\mu)$ of subsets of $\mu$ with the following properties? for all $U\in {\cal U}$ we have $|...
4
votes
0answers
106 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 ...
1
vote
1answer
36 views

Does $G$ with $\delta(G)\geq \aleph_0$ contain $k$-regular sub-edge-sets?

Let $G=(V,E)$ be an infinite, simple, undirected graph, such that for all $v\in V$ we have $\text{deg}(v) \geq \aleph_0$. Given an integer $k\geq 1$, is there always $E^{(k)}\subseteq E$ such that $(V,...
7
votes
1answer
400 views

Destroying Suslin, nothing special

Recall that a tree on $\omega_1$ is called Suslin if every chain and antichain are countable. If every level is countable and there are no cofinal branches, then it is called Aronszajn (in particular ...
4
votes
1answer
60 views

Optimal pseudotransversals

A hypergraph $H=(V,E)$ consists of an non-empty set $V$ and a collection $E\subseteq {\cal P}(V)\setminus \{\emptyset\}$ of non-empty subsets of $V$. A transversal of $H$ is a set $T\subseteq V$ such ...
0
votes
1answer
70 views

Minimizing the set of “wrong” edges in $K_\omega$ with $\{0,1\}$-weights

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in X\big\}$. Let $f:[\omega]^2\to\{0,1\}$ be a function. The principal goal is to find a partition of $\omega$ such that if $m\neq n\in \omega$ ...
3
votes
0answers
152 views

On Khelif's example of a group of countable cofinality having the Bergman property

A group $G$ is defined to have the Bergman property if for any subset $X=X^{-1}$ generating $G$ there exists $n$ such that $X^n=G$. By a result of Bergman, the permutation group of any set has the ...
8
votes
1answer
312 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
195 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 ...
11
votes
3answers
374 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
65 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$). ...
8
votes
2answers
274 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
81 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
386 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
330 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
272 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
80 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
155 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
207 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
176 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
152 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
73 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
151 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
167 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?
3
votes
1answer
166 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
163 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
93 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
240 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
61 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
83 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
234 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
161 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
73 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
143 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
353 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
92 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
186 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
106 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
338 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
158 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
213 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
57 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 ...