Questions tagged [infinite-combinatorics]

Combinatorial properties of infinite sets. This is a corner-point of set theory and combinatorics.

Filter by
Sorted by
Tagged with
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 ...
Dominic van der Zypen's user avatar
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 $\...
Monroe Eskew's user avatar
  • 18.1k
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,...
Yann Peresse's user avatar
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$ ...
Dominic van der Zypen's user avatar
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 (...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 \...
Archimondain's user avatar
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. ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 $...
Tri's user avatar
  • 1,366
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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$ ...
Dominic van der Zypen's user avatar
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$. ...
Dominic van der Zypen's user avatar
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 ...
Ashutosh's user avatar
  • 9,771
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: \...
Otto's user avatar
  • 1,006
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\...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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]$, $...
Sebastien Palcoux's user avatar
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 ...
Monroe Eskew's user avatar
  • 18.1k
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'): |(...
Dominic van der Zypen's user avatar
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 ...
Gabriel Medina's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Taras Banakh's user avatar
  • 40.8k
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 $\...
ar.grig's user avatar
  • 1,133
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\}$. ...
ar.grig's user avatar
  • 1,133
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\...
ar.grig's user avatar
  • 1,133
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 (\...
Dominic van der Zypen's user avatar
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 ...
Todd Eisworth's user avatar
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$, ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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}\...
ar.grig's user avatar
  • 1,133
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 ...
bof's user avatar
  • 11.5k
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 ...
ar.grig's user avatar
  • 1,133
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$,...
Dominic van der Zypen's user avatar
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}$ ?
ar.grig's user avatar
  • 1,133
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 ...
Dominic van der Zypen's user avatar
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$...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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)$. ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar
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$ ...
Dominic van der Zypen's user avatar
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|$ ...
Alex Meiburg's user avatar
  • 1,193
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 = \...
Otto's user avatar
  • 1,006
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 ...
Dominic van der Zypen's user avatar
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 ...
Dominic van der Zypen's user avatar

1
4 5
6
7 8
10