On colorings of hypergraphs embeddable in $\mathbb{R}^d$

Imagine you are a city planner trying to organize a massive, multi-dimensional city. In this city, the "buildings" are not just single houses, but groups of people (called hyperedges) who need to work together. Your job is to assign each person a "uniform color" (like Red, Blue, or Green) for their shirt.

The Golden Rule of your city is: No group of people working together can all wear the same color shirt. If a group of 3 people is a team, they can't all be Red. At least one must be Blue or Green.

The Chromatic Number is simply the minimum number of shirt colors you need to make sure this rule is never broken.

Now, imagine this city has a very strict architectural rule: The city must be built inside a specific shape.

If the city is 3D, it must fit inside a 3D room.
If it's 4D, it must fit inside a 4D room, and so on.

The big question this paper asks is: If we force our city to fit inside a specific shape (like a 3D room), is there a limit to how many colors we might need? Or, could the city get so complicated that we would need an infinite number of colors to keep the groups from matching?

The Main Discovery: "The Infinite Color Problem"

The authors, Seunghun Lee and Eran Nevo, discovered that for many types of these cities, the answer is YES: you might need an infinite number of colors.

Here is the breakdown of their findings using simple analogies:

1. The "Straight Line" City (Linear Embedding)

Imagine you are trying to build your city inside a room, but you are only allowed to place the people on a straight, rigid wire (like a string of beads) that runs through the room. This is called "linear embedding."

The Old Belief: Mathematicians thought that if the groups (hyperedges) were small enough compared to the size of the room, you could always get away with a finite number of colors.
The New Discovery: The authors proved that even if the groups are small, if the room is big enough (dimension $d \ge 3$ $d \geq 3$ ), you can construct a city so twisted and tangled that no matter how many colors you have, you will eventually run out. You would need an infinite supply of shirt colors to keep the groups from matching.
- Analogy: It's like trying to untangle a knot on a string. No matter how many different colored markers you have, the knot is so complex that you can't color it without two touching parts having the same color.

2. The "Folded Paper" City (PL Embedding)

Now, imagine you are allowed to build the city using folded paper (Piecewise Linear, or PL). You can bend the wire, make corners, and create flat surfaces, as long as the city doesn't tear or pass through itself.

The Discovery: Even with this extra flexibility (bending the wire), if you have a room of dimension $d$ and your groups have size $d+1$ , you can still build a city that requires infinite colors.
Analogy: Even if you are allowed to fold a piece of paper into a complex origami shape, you can still create a pattern on it that is so chaotic that you can't color it with a finite set of crayons without breaking the rules.

3. The "Odd-Numbered" Mystery

There is one tricky case left. What if the room is 3D, 5D, 7D (odd numbers), and the groups are size $d+1$ ?

The authors proved that in these specific "odd" dimensions, you definitely need at least 3 colors.
They couldn't prove it needs infinite colors yet, but they proved it's impossible to do it with just 2.
Analogy: It's like a puzzle where you know 2 colors definitely won't work, but you haven't yet figured out if you need 100 or infinity.

Why Does This Matter? (The "Manifold" Application)

The paper also applies this to Manifolds. Think of a manifold as a smooth, curved surface, like the skin of a balloon (2D) or the surface of a donut (3D).

The authors showed that if you try to triangulate (break down) the surface of a balloon or a donut into tiny triangles, and you look at the groups of points that form those shapes, you can create a surface so complex that you need infinite colors to color its faces.

This answers a long-standing question: "Can we build a 3D sphere (like a perfect ball) made of triangles where you can't color the faces with just 2 colors?" The answer is a resounding YES. In fact, for higher dimensions, you might need an infinite number of colors.

Summary of the "Magic"

The Setup: We are coloring groups of points in a geometric space.
The Constraint: The points must fit inside a specific geometric shape (a room of dimension $d$ ).
The Result: For many combinations of room size and group size, the geometry is so restrictive that you can create a "monster" structure that requires infinite colors to satisfy the rule "no group can be one color."
The Method: They used clever mathematical tricks (like building trees of connections and using "moment curves" which are special curved lines) to prove that these monsters exist.

In a nutshell: This paper proves that geometry can be so tricky that it forces us to use an infinite number of colors to solve a simple coloring puzzle, shattering the idea that there's always a simple, finite limit to how complex these shapes can get.

Here is a detailed technical summary of the paper "On colorings of hypergraphs embeddable in $\mathbb{R}^d$ " by Seunghun Lee and Eran Nevo.

1. Problem Statement and Context

The paper investigates the relationship between the geometric embeddability of simplicial complexes (or hypergraphs) in Euclidean space $\mathbb{R}^d$ and their weak chromatic number $\chi(H)$ .

Definitions:
- A hypergraph $H$ is weakly $m$ -colorable if its vertices can be colored with $m$ colors such that no hyperedge is monochromatic. The weak chromatic number $\chi(H)$ is the smallest such $m$ .
- $\chi_L(k, d)$ : The supremum of $\chi(H)$ over all finite $k$ -uniform hypergraphs $H$ that form the maximal faces of a simplicial complex linearly (geometrically) embeddable in $\mathbb{R}^d$ .
- $\chi_{PL}(k, d)$ : The supremum of $\chi(H)$ for complexes piecewise-linearly (PL) embeddable in $\mathbb{R}^d$ .
Motivation: Previous work established that for small $k$ relative to $d$ , these chromatic numbers are unbounded ( $\infty$ ). Specifically, trivial bounds showed $\chi_L(k, d) = \infty$ for $k \le (d+1)/2$ . Heise et al. [20] extended this to $d=2k-3$ and $d=2k-2$ .
Open Questions: The authors aim to determine the behavior of $\chi_L(k, d)$ and $\chi_{PL}(k, d)$ for the remaining cases, particularly when $k$ is close to $d+1$ . Specifically, they address whether $\chi_L(k, d) = \infty$ for all $2 \le k \le d $and the behavior of$ \chi_{PL}(d+1, d)$.

2. Methodology

The authors employ a combination of combinatorial constructions and geometric embedding techniques.

A. Combinatorial Frameworks

Interlacing Property: The paper utilizes the concept of $l$ -interlacing hypergraphs. A hypergraph is $l$ $l$ -interlacing if two edges $e_1, e_2$ $e_{1}, e_{2}$ contain vertices alternating in a specific order $v_1 \prec v_2 \prec \dots \prec v_l$ $v_{1} ≺ v_{2} ≺ \dots ≺ v_{l}$ .
- Key Lemma (2.1): A $k$ -uniform hypergraph is geometrically embeddable on the moment curve $\gamma_d(t) = (t, t^2, \dots, t^d)$ if and only if it is not $(d+2)$ -interlacing. This connects the geometric condition to a purely combinatorial property.
Hypergraph Families:
- Ackerman-Keszegh-Pálvölgyi (AKP) Construction: The authors utilize a family of hypergraphs $H(a, b)$ based on $b$ -ary trees of depth $a-1$ . They prove these hypergraphs are not $(a+2)$ -interlacing under a Depth-First Search (DFS) ordering.
- Recursive Construction: They define $H_{k,m}$ recursively to achieve unbounded chromatic numbers while maintaining the non-interlacing property required for embedding.
- Hales-Jewett Theorem: For the PL case, they utilize the Hales-Jewett theorem, which guarantees the existence of monochromatic combinatorial lines in high-dimensional hypercubes, implying unbounded chromatic numbers for specific hypergraphs.

B. Geometric Constructions

Moment Curve Embeddings: For the linear case (Theorem A), the authors map vertices to the moment curve $\gamma_d$ . By ensuring the hypergraphs are not $(d+2)$ -interlacing, they satisfy the Radon partition condition required for convex hulls of edges to be disjoint (except at shared vertices).
PL Embeddings via "Inflation": For the PL case (Theorem B), they use a geometric "inflation" technique. Vertices of a linear hypergraph are expanded into $d$ -dimensional polyhedral cells (simplexes) such that intersections of cells correspond exactly to intersections of hyperedges.
Geometric Join and Skewed Position: For the specific case of $\chi_L(d+1, d)$ $χ_{L} (d + 1, d)$ with odd $d$ $d$ (Theorem C), they construct a specific non-2-colorable hypergraph $L_d$ $L_{d}$ . This involves:
- Constructing two copies of a cyclic polytope $C_d(2d)$ (denoted $B_1$ and $B_2$ ).
- Using geometric joins of paths and specific subsets ( $M_1, M_2$ ).
- Ensuring skewed position (a general position condition for affine spans) to prevent unwanted intersections of convex hulls.
- Utilizing separating hyperplanes to isolate different parts of the construction.

3. Key Contributions and Results

The paper establishes the following Main Theorem for $d \ge 3$ :

Result A (Linear Embeddability): $\chi_L(k, d) = \infty$ $χ_{L} (k, d) = \infty$ for all $2 \le k \le d$.
- Significance: This completely resolves the linear case for $k \le d$ , showing that geometric embeddability in $\mathbb{R}^d$ imposes no bound on the chromatic number for any uniformity up to $d$ . This improves upon previous bounds which were limited to $k \le (d+1)/2$ or specific cases like $d=2k-2$ .
Result B (PL Embeddability): $\chi_{PL}(d+1, d) = \infty$ $χ_{P L} (d + 1, d) = \infty$ .
- Significance: This proves that even for the highest possible uniformity ( $k=d+1$ ) in $\mathbb{R}^d$ , if we allow Piecewise-Linear embeddings, the chromatic number is unbounded. This is achieved by embedding linear hypergraphs (which have unbounded chromatic numbers via Hales-Jewett) into $\mathbb{R}^d$ using the inflation lemma.
Result C (Linear Embeddability for $k=d+1$ ): $\chi_L(d+1, d) \ge 3$ $χ_{L} (d + 1, d) \geq 3$ for all odd $d \ge 3$ $d \geq 3$ .
- Significance: This provides a non-trivial lower bound for the linear case when $k=d+1$ . While it does not prove $\infty$ , it shows that the chromatic number is not bounded by 2 (i.e., non-2-colorable hypergraphs exist). The construction $L_d$ is a specific non-2-colorable $(d+1)$ -uniform hypergraph embeddable in $\mathbb{R}^d$ .
Result D (Manifolds): $\chi_s(M) = \infty$ $χ_{s} (M) = \infty$ for every triangulable $d$ $d$ -manifold $M$ $M$ and $1 \le s \le d$.
- Significance: This extends the results to triangulations of manifolds, answering a question by Lutz and Møller regarding the existence of non-2-colorable simplicial $d$ -spheres for $d > 3$ .

4. Significance and Implications

Resolution of Open Problems: The paper significantly advances the understanding of the "chromatic number vs. embeddability" problem. It closes the gap for linear embeddings where $k \le d$ and provides the first strong lower bounds for the critical $k=d+1$ case.
Manifold Triangulations: The result that $\chi_s(M) = \infty$ implies that for any dimension $d \ge 3$ , there exist triangulations of $d$ -manifolds (including spheres) with arbitrarily high weak chromatic numbers. This answers a specific question about the existence of non-2-colorable simplicial spheres for $d > 3$ .
Methodological Innovation:
- The use of the moment curve combined with interlacing properties provides a powerful tool for constructing linearly embeddable hypergraphs with high chromatic numbers.
- The inflation lemma (Lemma 3.1) offers a constructive method to convert abstract linear hypergraphs into PL-embeddable complexes, bridging combinatorics and topology.
Future Directions: The paper highlights a remaining gap: Is $\chi_L(d+1, d) = \infty$ for all $d \ge 3$ ? (Currently known only to be $\ge 3$ for odd $d$ ). It also poses questions about the chromatic numbers of boundary complexes of $d$ -polytopes.

Summary Table of Results

Parameter	Previous Best Bound	New Result (This Paper)
$\chi_L(k, d)$ for $k \le (d+1)/2$	$\infty$	$\infty$ (Trivial)
$\chi_L(k, d)$ for $d=2k-2, 2k-3$	$\infty$ (Heise et al.)	$\infty$ (Extended to all $2 \le k \le d$)
$\chi_L(d+1, d)$ (Odd $d$ )	Unknown / $\ge 2$	$\ge 3$
$\chi_{PL}(d+1, d)$	Unknown	$\infty$
$\chi_s(M)$ (Triangulable $d$ -manifold)	$\infty$ for $s \le \lceil d/2 \rceil$	$\infty$ for all $1 \le s \le d$

In conclusion, Lee and Nevo demonstrate that geometric constraints in $\mathbb{R}^d$ are surprisingly weak regarding the coloring of hypergraphs, allowing for unbounded chromatic numbers in almost all cases of interest, with only a specific gap remaining for the linear embedding of $(d+1)$ -uniform hypergraphs.

On colorings of hypergraphs embeddable in Rd\mathbb{R}^dRd