Questions tagged [infinite-combinatorics]
Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.
475
questions
0
votes
1
answer
184
views
Are hypergraphs $H=(V,E)$ with $|E|=|V|$ $2$-colorable?
A hypergraph $H=(V,E)$ consists of a set $V$ and a collection of subsets $E \subseteq {\cal P}(V)$. A coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal, such that for ...
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 $\...
10
votes
1
answer
222
views
Is there a topological group with the small index property that does not have automatic continuity?
Here are the exact definitions of the terms:
Let $G$ be a topological group.
Then $G$ has the small index property if every subgroup of countable (including finite) index is open in $G$. Furthermore,...
1
vote
1
answer
63
views
Minimally connected hypergraphs
Let $H=(V,E)$ be a hypergraph, where $V\neq \emptyset$ is a set, and $E\subseteq {\cal P}(V)$. We say that $H$ is connected if whenever $S\subseteq V$ with $\emptyset \neq S \neq V$, there is $e\in E$ ...
5
votes
1
answer
77
views
Sizes of matchings and transversals in hypergraphs
Let $H=(V,E)$ be a hypergraph. We call $H$ proper if $E\neq\emptyset, \emptyset \notin E$ and for no $e_1\neq e_2\in E$ we have $e_1\subseteq e_2$. A matching is a set $M$ of pairwise disjoint edges (...
1
vote
2
answers
160
views
Clutters with no maximum-size matchings
A clutter is a pair $C=(V,E)$ where $V\neq\emptyset$ is a set, and $E\subseteq {\cal P}(V)$ such that no member of $E$ is included in another member of $E$. A matching in $C$ is a collection of ...
2
votes
1
answer
133
views
Is $S_\omega/F_\omega$ embeddable to $S_\omega$?
Let $S_\omega$ be the group of bijections $f:\omega\to\omega$, and let $F_\omega = \{\pi\in S_\omega: \exists N\in \omega(\pi(k) = k \text{ for all } k\geq N)\}$. It is easy to see that $F_\omega$ is ...
2
votes
1
answer
114
views
Ramsey type properties of $F_\sigma$ ideals
Let $I \subseteq 2^\omega$ be any $F_\sigma$ ideal containing every finite sets :
$\forall X \in I\ \forall Y \subseteq X\ \text{ we have } Y \in I$
$\forall k\ \forall X_1,\dots,X_k \in I\ X_1 \cup \...
3
votes
1
answer
70
views
Connected hypergraphs
We say that a hypergraph $H=(V,E)$ is connected if the following condition holds:
for all $S\subseteq V$ with $\emptyset\neq S \neq V$ there is $e\in E$ that meets both $S$ and $V\setminus S$, i.e. ...
2
votes
1
answer
82
views
Chromatically rigid hypergraphs
If $H=(V,E)$ is a hypergraph and $\kappa$ is a cardinal, then $c:V\to\kappa$ is a coloring if for every $e\in E$ with $|e|>1$, the restriction $c|_e:e \to \kappa$ is non-constant. By $\chi(H)$ we ...
5
votes
1
answer
117
views
Generalization of Menger's theorem to infinite graphs
Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets $A$ and $B$, there is a family $F$ of disjoint paths from $A$ to $B$ and a set separating $B$ from $...
0
votes
2
answers
204
views
Collection $\cal{C}$ of uncountable subsets of $\mathbb{R}$ such that every countable subset is contained in exactly one member of $\cal{C}$
If $\kappa$ is a cardinal and $X$ is a set, let $[X]^\kappa$ denote the collection of subsets of $X$ that have cardinality $\kappa$.
Let $\beta>\omega$ and $\beta \leq 2^{\omega}$. Is there ${\cal ...
1
vote
1
answer
61
views
Induced subgraphs of the line graph of a dense linear hypergraph
Given a hypergraph $H=(V,E)$ we associate to it its line graph $L(H)$ given by $V(L(H)) =E$ and $$E(L(H)) = \big\{\{e_1,e_2\}: e_1\neq e_2 \in E \text{ and } e_1\cap e_2 \neq \emptyset \big\}.$$
We ...
3
votes
2
answers
121
views
Avoiding multiply covered vertices in graph edge coverings
Let $G=(V,E)$ be a simple, undirected graph with $\bigcup = E$ (that is, there are no isolated vertices). We say that $C\subseteq E$ is an edge cover of $G$ if $\bigcup C = V$. For any edge cover $C$ ...
0
votes
1
answer
58
views
Dominating vertex sets in hypergraphs
Let $H=(V,E)$ be a hypergraph such that $\bigcup E = V$. For $D\subseteq V$ we set $N_D = \bigcup\{e\in E: D\cap e\neq \emptyset\}$. We say that $D\subseteq V$ is dominating if $N_D = V$.
...
3
votes
0
answers
348
views
Almost disjoint families on $\omega_1$
Suppose there is a family of $\aleph_3$ unbounded subsets of $\omega_1$ in which no set is contained in a countable union of other sets. Must there exist a (mod countable) almost disjoint family of ...
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: \...
4
votes
2
answers
580
views
"Rocket elements" in bijections $f:\mathbb{N}\to \mathbb{N}$
Let $\mathbb{N}$ denote the set of non-negative integers. If $f:\mathbb{N}\to\mathbb{N}$ is a map, we set for $k\in \mathbb{N}$:
$f^{(0)}(k) = k$, and
$f^{(n+1)}(k) = f(f^{(n)}(k))$ for all $n\in\...
3
votes
1
answer
93
views
Induced subgraphs of $\text{Exp}(G, K_2)$
If $G, H$ are simple, undirected graphs, we define the exponential graph $\text{Exp}(G,H)$ to be the following graph:
the vertex set is the set of all maps $f:V(G)\to V(H)$
two maps $f\neq g: V(G)\to ...
3
votes
1
answer
328
views
Infinite group generated by a single coset
Let $G$ be an infinite countable group having a core-free subgroup $H$ such that the interval $[H,G]$ in the subgroup lattice $\mathcal{L}(G)$ is ACC of infinite length, and for every $K \in (H,G]$, $...
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 ...
5
votes
1
answer
216
views
"Uniformly continuous" environment sum of a bijection $\varphi:\mathbb{Z}\times \mathbb{Z} \to \mathbb{Z}$
Given any function $f: \mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$ we define the environment sum of $(x,y)\in\mathbb{Z}\times \mathbb{Z}$ with respect to $f$ by
$$\text{es}_f(x,y) = \sum\{f(x', y'): |(...
3
votes
0
answers
208
views
Nowhere Baire spaces
Studying the article "Barely Baire spaces" of W. Fleissner and K. Kunen, using stationary sets, they show an example of a Baire space whose square is nowhere Baire (we call a space $X$ nowhere Baire ...
2
votes
1
answer
131
views
Chromatic number of the linear graph on $[\omega]^\omega$
Let $[\omega]^\omega$ denote the set of infinite subsets of $\omega$. Let $$E = \{\{a,b\}: a,b\in [\omega]^\omega\text{ and } |a\cap b| = 1\}.$$
It is clear that $G = ([\omega]^\omega, E)$ has no ...
1
vote
0
answers
49
views
Minimizing the set of multiply covered elements in a linear hypergraph
We say that a hypergraph $H=(V,E)$ is a linear hypergraph if it has the following properties:
if $e_1\neq e_2\in E$ then $|e_1\cap e_2|\leq 1$, and
$\bigcup E = V$.
We say that $C\subseteq E$ is a ...
2
votes
1
answer
139
views
Injective choice function for "lines" in an infinite cardinal
Let $\lambda$ be an infinite cardinal and suppose ${\cal L}$ is a collection of subsets of $\lambda$ such that
$|k| = \lambda$ for all $k\in {\cal L}$ and,
if $k_1\neq k_2\in {\cal L}$ then $|k_1\cap ...
8
votes
2
answers
421
views
Relations between two tower numbers
A tower is a subset $T\subset [\omega]^\omega$ of the family $[\omega]^\omega$ of all infinite subsets of $\omega$ such that $T$ is well-ordered by the relation $\supset^*$ of almost inclusion and has ...
2
votes
1
answer
91
views
Dense subfilter of selective ultrafilter
Given selective ultrafilter $\mathcal{U}$ on $\omega$ and dense filter $\mathcal{F_1}=\{A\subset\omega~|~\rho(A)=1\}$, where $\rho(A)=\lim_{n\to\infty}\frac{|A\cap n|}{n}$ if the limit exists. Let $\...
3
votes
1
answer
153
views
Dense filter and selective ultrafilter
We say that $\rho(A)=\lim_{n\to\infty}\frac{|A\cap n|}{n}$ is the density of subset $A\subset\omega$ if the limit exists. Let us define the filter $\mathcal{F_1}=\{A\subset\omega~|~\rho(A)=1\}$.
...
1
vote
1
answer
117
views
Some kind of idempotence of dense filter
In discussion of following questions question1, question2, question3 became clear (see definitions in question3 ) that for the Frechet filter $\mathcal{N}$ we have $\mathcal{N}\nsim\mathcal{N}\otimes\...
0
votes
1
answer
190
views
Maximal elements in the Rudin-Keisler ordering
Let $\text{NPU}(\omega)$ be the set of non-principal [ultafilters][1] on $\omega$. The Rudin-Keisler preorder on $\text{NPU}(\omega)$ is defined by
$${\cal U} \leq_{RK} {\cal V} :\Leftrightarrow (\...
3
votes
0
answers
127
views
Covering numbers - looking for a more combinatorial proof
For cardinals $\mu$, $\kappa$, $\theta$, and $\sigma$, the covering number $cov(\mu,\kappa,\theta,\sigma)$ is defined to be the minimum cardinality of a set $P\subseteq [\mu]^{<\kappa}$ such that ...
4
votes
1
answer
239
views
Minimal cardinality of a filter base of a non-principal uniform ultrafilters
Let $\kappa$ be an infinite cardinal. An ultrafilter ${\cal U}$ on $\kappa$ is said to be uniform if $|R|=\kappa$ for all $R\in{\cal U}$. If ${\cal U}$ is a non-principal ultrafilter on $\kappa$, ...
1
vote
1
answer
84
views
Maximizing "happy" vertices in splitting an infinite graph
This question is motivated by a real life task (which is briefly described after the question.)
Let $G=(V,E)$ be an infinite graph. For $v\in V$ let $N(v) = \{x\in V: \{v,x\}\in E\}$. If $S\subseteq ...
4
votes
1
answer
117
views
The example of the idempotent filter or subsets family with finite intersections property
From the answer of Andreas Blass and comments of Ali Enayat on my question Selective ultrafilter and bijective mapping it became clear that for any free ultrafilter $\mathcal{U}$ we have $\mathcal{U}\...
5
votes
1
answer
347
views
Graphs with minimum degree $\delta(G)\lt\aleph_0$
Let $G=(V,E)$ be a graph with minimum degree $\delta(G)=n\lt\aleph_0$. Does $G$ necessarily have a spanning subgraph $G'=(V,E')$ which also has minimum degree $\delta(G')=n$ and is minimal with that ...
6
votes
1
answer
284
views
On infinite combinatorics of ultrafilters
Let $\mathcal{U}$ be (selective) ultrafilter and $\omega = \coprod_{i<\omega}S_i$ be partition of $\omega$ with small sets $S_i\notin\mathcal{U}$. All $S_i$ are infinite. Does there exist a system ...
4
votes
1
answer
155
views
Are two "perfectly dense" hypergraphs on $\mathbb{N}$ necessarily isomorphic?
We say that a hypergraph $(\mathbb{N}, E)$ where $E\subseteq {\cal P}(\mathbb N)$ is perfectly dense if
$\mathbb{N}\notin E$,
all $e\in E$ are infinite,
$e_1, e_2 \in E$ implies $|e_1\cap e_2| = 1$,...
12
votes
1
answer
480
views
Selective ultrafilter and bijective mapping
For arbitrary (selective) ultrafilter $\mathcal{F}$ does there exist bijection $\phi:[\omega]^2\to\omega$ with the property: $\forall B\in\mathcal{F} : \phi([B]^2)\in\mathcal{F}$ ?
2
votes
1
answer
89
views
$T_1$-spaces vs $T_1$-hypergraphs
Let us say that a hypergraph $H=(V,E)$ is $T_1$ if for $x\neq y$ there is $e\in E$ such that $e\cap\{x,y\} = \{x\}$.
Note that for any $T_1$-space $(X,\tau)$ the topology $\tau$ contains the ...
0
votes
1
answer
70
views
Maximizing set systems with property $\mathbf{B}$
Let $X$ be an infinite set, and let ${\cal E}$ be a collection of non-empty subsets of $X$. We say that ${\cal E}$ has property $\mathbf{B}$ if there is $B\subseteq X$ such that $B\cap E\neq \emptyset$...
0
votes
1
answer
43
views
Connected subgraph of infinite graph with surjective homormophism, but no graph isomorphism
For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$.
What is an example of a connected graph $G=(V,E)$ and a subset $S\subseteq V$ such that the subgraph $$G[S]:=(S, E\cap [S]^2)$$ is ...
0
votes
1
answer
85
views
Linear intersection number and chromatic number for infinite graphs
Given a hypergraph $H=(V,E)$ we let its intersection graph $I(H)$ be defined by $V(I(H)) = E$ and $E(I(H)) = \{\{e,e'\}: (e\neq e'\in E) \land (e\cap e'\neq \emptyset)\}$.
A linear hypergraph is a ...
0
votes
1
answer
51
views
Minimizing the set of "faulty" edges in a map between the vertex sets of $2$ graphs
The starting point of this question is the fact that for some simple, undirected graphs $G, H$ there is no graph homomorphism $f:G\to H$. This is the case for instance if $\chi(G)>\chi(H)$.
...
1
vote
1
answer
48
views
Tightly knit graphs on $\omega$
We say that a simple, undirected graph $G = (\omega, E)$ on the vertex set $\omega$ is tightly knit if there is a positive integer $n>2$ such that for all $v,w\in \omega$ there is a cycle $C$ of ...
3
votes
1
answer
267
views
Does every directed graph have a directed coloring with $4$ colors?
Every finite directed graph has a majority coloring with $4$ colors. (The notion of majority coloring is defined below.)
Question. Can every infinite directed graph be majority-colored with $4$ ...
6
votes
1
answer
270
views
Does every bijective graph endomorphism restrict to a full-cardinality isomorphism?
Given a graph $G$, and a bijective endomorphism $f$ (that is, a graph homeomorphism $f : G \to G$ that establishes a bijection on the vertices), it is true that $f$ is an automorphism whenever $|G|$ ...
6
votes
2
answers
893
views
Poset dimension and width (Dilworth's theorem)
For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \...
1
vote
1
answer
60
views
Hypergraph colorings with small fibers
Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the ...
0
votes
1
answer
104
views
Size of edge set of infinite hypergraphs with $\chi(H) = |V(G)|$
Let $H=(V,E)$ be a hypergraph such that for every $e\in E$ we have $|e|\geq 2$. A map $c:V\to \kappa$, where $\kappa$ is a cardinal, is said to be a (hypergraph) coloring if for all $e\in E$ the ...