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
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 ...
user avatar
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)...
user avatar
  • 1,064
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 $\...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 18.8k
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$...
user avatar
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 ...
user avatar
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$?
user avatar
-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-...
user avatar
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 ...
user avatar
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 ...
user avatar
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}|...
user avatar
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 $\...
user avatar
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 ...
user avatar
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, $\...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 235
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 ...
user avatar
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:...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
  • 32.9k
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}$, $...
user avatar
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$ ...
user avatar
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 ...
user avatar
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:\...
user avatar
  • 3,379
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},...
user avatar
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 $$\...
user avatar
  • 32.9k
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}$. ...
user avatar
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^*$...
user avatar
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 ...
user avatar
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}(\{...
user avatar
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 ...
user avatar
  • 49.2k
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$? ...
user avatar
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 ...
user avatar
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^* \...
user avatar
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 ...
user avatar
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\...
user avatar
  • 2,709
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 ...
user avatar
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 ...
user avatar
  • 369
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(...
user avatar
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 ...
user avatar
  • 11
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 ...
user avatar
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 $\...
user avatar
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....
user avatar
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 ...
user avatar
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'...
user avatar
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 ...
user avatar

1
2 3 4 5
8