# Questions tagged [infinite-combinatorics]

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

371 questions
Filter by
Sorted by
Tagged with
116 views

### Gaps in cardinalities of MAD families

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. We say $a,b\in [\omega]^\omega$ are almost disjoint if $a\cap b$ is finite. A subset $A\subseteq [\omega]^\omega$ is said ...
117 views

234 views

### Properties of Jech's hierarchy of stationary sets (Exercise 8.13, 8.14 of Jech)

I must first preface that while this is indeed a question on an exercise, I believe this is advanced enough for MathOverflow. Let $\kappa$ be a regular uncountable cardinal. Recall that the notion of ...
213 views

### Infinite vertex-transitive graph where every automorphism has a fixed vertex

This is a follow-up to the question Connected vertex-transitive graph with the fixed-point property. In particular, it is based on a comment by user bof. Let $G = (V,E)$ be a graph with $V$ infinite. ...
1 vote
59 views

### Edge sets on $\omega$ maximal with respect to chromatic number

If $H=(V,E)$ is a hypergraph, and $\kappa \neq \emptyset$ is a cardinal, a map $c: V\to \kappa$ is said to be a coloring if the restriction $c|_e: e\to \kappa$ is non-constant whenever $e\in E$ and $e$...
424 views

### Does "$X \not\to (\omega)^\omega_2$ for every infinite $X$" imply ${\sf AC}$?

For any set $X$ and cardinal $\mu \neq \emptyset$, we denote by $[X]^\mu$ the collection of subsets of cardinality $\mu$. If $\kappa, \mu \neq \emptyset$ are cardinals and $f: [X]^\mu\to \kappa$ is a ...
84 views

### Non-isomorphic connected vertex-transitive graphs on $\omega$

Are there $2^{\aleph_0}$ pairwise non-isomorphic connected vertex-transitive graphs $G$ with $V(G) = \omega$?
76 views

### Hamiltonian $\mathbb{Z}$-paths in connected countably infinite vertex-transitive graphs [closed]

A simple, undirected graph $G=(V,E)$ is said to be vertex-transitive if for all $a,b\in V$ there is a graph isomorphism $\varphi:G\to G$ such that $\varphi(a) = b$. If $G = (\omega, E)$ is vertex-...
41 views

### Conflict-free coloring of linear hypergraphs on $\omega$

This question is motivated by considerations on conflict-free colorings, which arose while studying assignment problems for frequencies in cellular networks. A hypergraph $H=(V,E)$ is said to be ...
273 views

### Conflict-free coloring of $\mathbb{R}$ with the Euclidean topology

A hypergraph $H =(V, E)$ consists of a set $V$ and a set $E \subseteq {\cal P}(V)$ of subsets of $V$. A hypergraph coloring is a map $c: V\to \kappa$, where $\kappa \neq \emptyset$ is a cardinal and ...
132 views

177 views

### On the chromatic number of an analytic graph

Let $X$ be a Polish space and let $G\in\mathbf{\Sigma}^1_1(X^2)$ be a graph on $X$, that is an irreflexive and symmetric relation on $X$. Given a cardinal $\kappa$ we say that $G$ has chromatic number ...
133 views

308 views

### Is the set of powerful numbers piecewise syndetic?

Recall that a subset $A \subset \mathbb Z_+$ of positive integers syndetic if there exists a $d>0$ such that every positive integer has distance at most $d$ to an element of $A$. It is called ...
41 views

### Minimal vertex-covering set

If $G=(V,E)$ is a simple, undirected graph, $C\subseteq V$ is said to be a vertex cover if for every $e\in E$ we have $C\cap e \neq \emptyset.$ If $G=(V,E)$ is infinite, is there necessarily a vertex ...
75 views

### Matching number in infinite hypergraphs

If $H= (V,E)$ is a hypergraph, a matching is a set $M\subseteq E$ such that $e_1\cap e_2 = \emptyset$ whenever $e_1\neq e_2 \in M$. The matching number $\mu(H)$ of a hypergraph $H=(V,E)$ with $V$ ...
72 views

50 views

### Are strongly complete regular linear hypergraphs on $\omega$ isomorphic?

This is a related question to an older one. If $H_i = (V_i, E_i)$ are hypergraphs for $i=1,2$ then we say they are isomorphic if there is a bijection $f: V_1 \to V_2$ such that for $A \subseteq V_1$ ...
1 vote
109 views

### Non-summable subsets of $[\omega]^{<\omega}$

Let $[\omega]^{<\omega}$ denote the collection of finite subsets of the integers, and let us call $E\subseteq [\omega]^{<\omega}$ non-nested if $a\not\subseteq b$ whenever $a\neq b\in E$. Is ...
1 vote
89 views

143 views

274 views

### Which abelian groups are $\aleph_1$-filtered colimits of finitely-generated abelian groups?

Observation: Every $\aleph_1$-directed colimit $\varinjlim_i X_i$ of finite sets is finite. Proof: Because the $X_i$'s are finite, the Mittag-Leffler condition holds, so by passing to the diagram of ...
594 views

### Induced subgraphs of any given smaller chromatic number

Let $G = (V,E)$ be a simple, undirected graph with $\chi(G)$ infinite. Given a cardinal $\kappa$ with $0 < \kappa < \chi(G)$, is there an induced subgraph $S$ of $G$ with $\chi(S) = \kappa$? ...
153 views

### Is the union of a chain of $\kappa$-colorable subgraphs $\kappa$-colorable?

Motivation. I was trying to prove that whenever $G$ is a simple, undirected graph and $\kappa< \chi(G)$ is a cardinal, then there is an induced subgraph with chromatic number exactly $\kappa$. This ...
95 views

315 views

### Non-associative commutative "group"

When dealing with some hash functions that I was trying to speed up, I toyed with a binary operation with the goal to "approximate" the addition on $\{0,1\}^*$ when seen as binary ...
166 views

### Can maximal filters of nowhere meager subsets of Cantor space be countably complete?

Let $X$ denote Cantor space. A subset $A\subseteq X$ is nowhere meager if for every non-empty open $U\subseteq X$, we have $A\cap U$ non-meager. We call $\mathcal{F}\subseteq \mathcal{P}(X)$ a maximal ...
1 vote
166 views

### Coloring infinite graph made out of copies of a finite graph

I have an infinite graph $G^\infty$ constructed out of sequence $G_t$ of copies of some finite graph $G$. More specifically: Vertex set of $G^\infty$ is V(G^\infty) = \bigcup_{i \in \mathbb{Z}} V(...
1 vote
117 views

### Pronunciation: the Erdős–Rado partition notation

The Erdős–Rado notation $a \rightarrow (b)^c_d$ is common in partition calculus / combinatorial set theory, as well as its negation $a \not\rightarrow (b)^c_d$. In that field, is there a standard way ...
### Diagonalizing against $\omega_1$-sequences of functions mod finite
The following statement is a direct consequence of the Continuum Hypothesis: There exists a sequence $\langle f_\alpha:\omega_1\rightarrow\omega_1 ~ \vert ~ \alpha<\omega_1\rangle$ of functions ...