# Questions tagged [infinite-combinatorics]

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

371
questions

4
votes

1
answer

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

4
votes

1
answer

117
views

### Strongly minimal covers for clique hypergraphs of graphs

$\DeclareMathOperator\Cliq{Cliq}$A hypergraph $H$ is a pair consisting of a set $V$ of vertices and a family of subsets of $V$ called edges.
One class of examples is obtained by taking a graph $G=(V,E)...

2
votes

1
answer

40
views

### Maximal matchable set in hypergraph with finite edges

Let $H=(V,E)$ be a hypergraph. A set $M\subseteq E$ consisting of mutually disjoint members of $E$ is said to be a matching. We say $S\subseteq V$ is matchable if there is a matching $M$ such that $\...

5
votes

2
answers

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

11
votes

1
answer

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

1
answer

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

9
votes

1
answer

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

4
votes

1
answer

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$?

-1
votes

1
answer

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

0
votes

1
answer

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

3
votes

2
answers

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

4
votes

0
answers

132
views

### Existence of a large family of sets with big differences

Let $\lambda\leq\kappa$ be two cardinals and $\Gamma$ be a set with $|\Gamma|=\kappa$.
Question. Does there exist a family $\mathscr{A}\subseteq \{A\subseteq \Gamma: |A|=\lambda\}$ with $|\mathscr{A}|...

3
votes

1
answer

195
views

### Is normalcy preserved under the swapping operation?

Let $\mathbb{N}$ denote the set of non-negative integers. We say that a sequence $f:\mathbb{N}\to \{0,1\}$ is normal if every finite $\{0,1\}$-sequence appears in $f$.
Let the swapping operation $\...

5
votes

1
answer

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

2
votes

0
answers

133
views

### Binary operation approximating "addition" on $2^\omega$

Motivation. In computer science, addition of integers $a+b$ can be approximated by a very fast operation: $(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$, where $\oplus$ denotes bitwise XOR, $\...

2
votes

0
answers

176
views

### A question about infinite product of Baire and meager spaces

Proposition 1: For any space $X$ and an infinite cardinal $\kappa$, the product $X^{\kappa}$ is either meager or a Baire space.
Does anyone have any suggestions to demonstrate Proposition 1?
I was ...

3
votes

0
answers

176
views

### A form of Hadwiger's conjecture for hypergraphs

A hypergraph $H=(V,E)$ consists of a
set $V$ and $E\subseteq {\mathcal P}(V)$. If $S\subseteq V$, we define
$$E|_S = \{e\cap S: (e\in E) \land (e\cap S \neq \emptyset)\}$$
and call $(S, E|_S)$ the ...

3
votes

1
answer

298
views

### Dehornoy's proof that the application of two elementary embeddings is an elementary embedding

What is meant by the statement and the proof of Lemma 3.2 in Chapter XII of Dehornoy's book Braids and Self-Distributivity?
That lemma states "Assume that $j_1$ and $j_2$ are elementary ...

1
vote

1
answer

196
views

### Chromatic number of duals of uniform hypergraphs with large edges

Let $H=(V,E)$ be a hypergraph. If $\kappa>0$ is a cardinal, we say that $H$ is $\kappa$-uniform if $|e|=\kappa$ for all $e\in E$.
If $X$ is a non-empty set, then a map $c:V\to X$ is said to be a ...

1
vote

1
answer

117
views

### Chromatic number and taking duals of hypergraphs

If $H=(V,E)$ is a hypergraph and $\kappa\neq \emptyset$ is a cardinal, then a map $c:V\to \kappa$ is said to be a colouring if for every edge $e\in E$ with $|e|\geq 2$ the restriction $c\restriction_e:...

8
votes

1
answer

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

2
votes

1
answer

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

2
votes

2
answers

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

2
votes

0
answers

72
views

### A convex version of the small uncountable cardinal $\mathfrak b$

Let us recall that $\mathfrak b$ is the smallest cardinality of a subset of $\omega^\omega$, which cannot be covered by countably many compact subsets of $\omega^\omega$.
The definition of $\mathfrak ...

6
votes

1
answer

262
views

### Are the following two "tree properties" equivalent?

Let $\kappa$ and $\lambda$ be cardinals. A thin $(\kappa,\lambda)$-list is a function $L:[\lambda]^{<\kappa}\longrightarrow [\lambda]^{<\kappa}$ such that for all $x\in[\lambda]^{<\kappa}$, $...

0
votes

1
answer

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

1
answer

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

0
answers

89
views

### Group graphs and Ramsey theory. Sub-question 1

Question: Find/compute relations between the classical Ramsey numbers and their variations (described below) -- exact or asymptotic.
A graph is a set $\ X\ $ together with a (coloring) function
$\ c:\...

0
votes

1
answer

92
views

### Can this fixed point theorem generalize to infinite structures?

Suppose that $n$ is a natural number, $X$ is a set, and $S\subseteq X^{2}$ is a subset such that if $x,y\in X$, then there is a unique tuple $(x_{0},\dots,x_{n})$ where $x_{0}=x,x_{n}=y$ and $(x_{i},...

5
votes

1
answer

143
views

### Can the Boolean group $C_2^\omega$ be covered by less than $\mathfrak b$ nowhere dense subgroups?

Let $\mathrm{cov}_H(C_2^\omega)$ be the smallest cardinality of a cover of the Boolean group $C_2^\omega=(\mathbb Z/2\mathbb Z)^\omega$ by closed subgroups of infinite index. It can be shown that
$$\...

2
votes

1
answer

159
views

### Include each point of continuum in a subset so that each subset gets finitely many points

Let $S$ be a set with $\lvert S\rvert=\lvert\mathbb{R}\rvert$. Suppose it has subsets $S_x$ indexed by $x\in \mathbb{R}$ with $\lvert S_x\rvert=\lvert\mathbb{R}\lvert$ for each $x\in \mathbb{R}$. ...

1
vote

1
answer

74
views

### Self-dual hypergraph on $\omega$

Let $H=(V,E)$ be a hypergraph. For $v\in V$ we let $v^* = \{e\in E:v\in e\}$. We define the dual of $H$ by $H^*= (E, V^*)$ where $V^* = \{v^*: v\in V\}$. We say that a $H$ is self-dual if $H \cong H^*$...

5
votes

0
answers

281
views

### A question on infinite arithmetic progressions

I was working on a problem that consisted of deciding if the language a finite automaton (the alphabet of which is $\{0,1\}$ and the words accepted are binary encoded positive integers) contains an ...

4
votes

3
answers

211
views

### Putting $\omega$ into $\alpha$ boxes where $\alpha \in \big(\omega\cup\{\omega\}\big)\setminus\{0,1\}$

This is a follow-up question to an older question.
Let $\alpha \in \big(\omega\cup\{\omega\}\big) \setminus \{0,1\}$ be an ordinal. We say that a function $f: \omega \to \alpha$ is fair if $$|f^{-1}(\{...

10
votes

2
answers

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

8
votes

2
answers

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

2
votes

1
answer

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

0
votes

2
answers

95
views

### Edge-adding conjecture for graphs

For any set $X$ we let $[X]^2 = \big\{\{x, y\}: x\neq y \in X\big\}$. Consider the following statement:
(S) : If $G =(V,E)$ is a simple, undirected graph such that $E \neq [X]^2$, then there is $e^* \...

3
votes

5
answers

331
views

### Graph $G$ such that removing an edge leaves $G$ "unchanged"

Is there an infinite simple, undirected graph $G = (V,E)$ such that there is $e\in E$ such that $G \cong (V, E\setminus\{e\})$?
(There cannot be a finite graph with that property because removing an ...

11
votes

1
answer

297
views

### Uncountable homogeneous rectangles for subsets of $\omega_2\times\omega_2$

The background theory here is at least ZFC and probably ZFC+MA+$\neg$CH, if it matters. Here's the question:
Suppose that $C\subseteq\omega_2\times\omega_2$. Must there exist uncountable sets $A,B\...

4
votes

1
answer

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

5
votes

0
answers

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

1
answer

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

1
answer

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

16
votes

2
answers

594
views

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

1
vote

1
answer

154
views

### Graph $G=(V,E)$ with $\chi(G)$ finite and $\text{Col}(G)$ infinite

Let $G = (V,E)$ be a simple, undirected graph. For $v\in V$ we let $N(v) = \{w \in V: \{v,w\} \in E\}$.
We define the coloring number $\text{Col}(G)$ of the graph $G$ to be the smallest cardinal $\...

1
vote

1
answer

84
views

### Large chromatic number in hypergraphs with large edges

Let $H=(V,E)$ be a hypergraph. If $\kappa \neq \emptyset$ is a cardinal, we call a map $c:V\to \kappa$ a coloring if for each $e\in E$ with $|e|>1$ the restriction $c\restriction_e$ is non-constant....

6
votes

1
answer

143
views

### a filter of subsets intersecting the cartesian power of each infinite subset

Is the following filter known in set theory, and does it have a name ?
For $k=1$ it is the filter of cofinite subsets.
Fix a natural number $k$ and a linear order $I$.
Define a filter on the set of ...

8
votes

3
answers

745
views

### Sunflowers in maximal almost disjoint families

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. We say ${\cal A}\subseteq [\omega]^\omega$ is almost disjoint if $A \cap B$ is finite whenever $A\neq B \in {\cal A}$. Zorn'...

2
votes

2
answers

165
views

### Sunflowers in $\omega$ consisting of infinite sets

If $X\neq\emptyset$ is a set, then ${\cal S}\subseteq {\cal P}(X)$ with ${\cal S}\neq \emptyset$ is said to be a sunflower if there is $K\subseteq X$ such that whenever $A\neq B\in{\cal S}$ ten $A\cap ...