Garment numbers of bi-colored point sets in the plane

Imagine you are hosting a party with a very specific rule: you have a large group of guests, and every single one of them is wearing either a Red Shirt or a Blue Shirt. You scatter them randomly across a large, flat dance floor (the "plane").

The goal of this paper is to answer a simple but tricky question: How many guests do you need to invite to guarantee that a specific, interesting pattern will form among people of the same color?

The authors call these patterns "Garments" (like neckties, skirts, and pants) because they look like shapes you might find in a fashion magazine. They are studying "empty" garments, which means the shape is formed by four people of the same color, and there are no other guests of that same color standing inside the shape. (Guests of the other color are allowed inside; they act like "blockers" or obstacles).

The Five "Garments"

The paper focuses on four-point shapes. Depending on how the four people stand, they form one of five specific "outfits":

The Cravat (Necktie): Four people standing in a perfect circle (convex). They form a nice, solid diamond shape.
The Necklace: Four people in a circle, but the shape is made of two triangles sharing a side. It looks like a double-loop necklace.
The Bowtie: Four people in a circle, but the lines cross over each other in the middle, looking like a bowtie.
The Skirt: Three people form a triangle, and the fourth person is standing inside that triangle. The shape is the big triangle (the skirt).
The Pant: Three people form a triangle, and the fourth is inside, but they connect the lines differently to form a simple, non-crossing four-sided shape that looks like a pair of pants.

The Big Question

The researchers are trying to find the "Garment Number." This is the minimum number of total guests (Red + Blue) you need to invite to guarantee that at least one of these empty shapes appears.

The Problem: If you invite too few people, you might get lucky and arrange them so that every time four Red people try to form a "Pant," a Blue person is standing right in the middle to ruin it.
The Goal: Find the magic number where it becomes impossible to arrange the guests without creating at least one empty Red or empty Blue shape.

What They Found

The paper is a mix of "Upper Bounds" (proving that if you have this many people, you are guaranteed a shape) and "Lower Bounds" (proving that if you have this few people, you can arrange them to avoid the shape).

Here are the key takeaways, translated into plain English:

1. The "Pants" and "Bowties" are easy to find.
If you invite 11 people, you are guaranteed to find an empty "Pant" or an empty "Bowtie" in either Red or Blue.

Analogy: It's like saying, "If you put 11 people in a room, you can't help but form a specific handshake pattern." The math proves that no matter how the Blue people try to block the Red people, they run out of blockers.

2. The "Necklace" is harder to find.
To guarantee an empty "Necklace," you need a lot more people. The paper proves that if you have 1,508 people, you are guaranteed one.

Analogy: This is like finding a specific, complex knot in a tangled ball of yarn. You need a huge amount of yarn before you are sure the knot will appear naturally. The authors used a famous math theorem (Erdős–Szekeres) to show that with enough people, you can find a large group of one color, and then prove there aren't enough people of the other color to block all the possible necklaces.

3. The "Skirt" and "Cravat" are still mysteries.
For some shapes, like the "Skirt" (a triangle with a point inside) or the "Cravat" (a perfect diamond), we don't know the exact number yet.

We know that if you have 35 people, you might still be able to arrange them to avoid a Red Skirt and a Blue Skirt.
But we also know that if you have a massive number of people (like 2,760), you are guaranteed to find a "Cravat."
The Gap: The gap between "we know it's possible with 35" and "we know it's guaranteed with 2,760" is huge. The paper didn't solve this one, but it set the stage for future detectives to close that gap.

Why Does This Matter?

You might ask, "Who cares about imaginary pants and neckties made of dots?"

This is actually a fundamental problem in Geometry and Computer Science. It helps us understand:

Order in Chaos: How much randomness can you have before order must appear?
Algorithm Design: If you are building software to recognize shapes (like self-driving cars seeing pedestrians), understanding these "blocking" patterns helps the computer know when it can safely ignore certain configurations.
The "Happy End" Problem: This research is a modern spin on a famous math problem from 1935 that started with a group of mathematicians falling in love (hence "Happy End"). It's about how points in space relate to each other.

The Bottom Line

The authors took a complex geometric puzzle and broke it down into five specific "fashion styles." They proved that for some styles (Pants/Bowties), you only need a small crowd (11 people) to guarantee a pattern. For others (Necklaces), you need a massive crowd (1,508). And for the most stylish ones (Cravats/Skirts), the mystery remains, inviting future mathematicians to keep playing with the dots.

Here is a detailed technical summary of the paper "Garment numbers of bi-colored point sets in the plane."

1. Problem Statement and Context

The paper addresses a variation of the classic Erdős–Szekeres problem (the "Happy End Problem"), which seeks the minimum number of points $ES(k)$ in general position in the plane required to guarantee a subset of $k$ points forming a convex $k$ -gon.

This work focuses on bichromatic point sets (points colored red and blue) and investigates the existence of empty monochromatic structures formed by exactly 4 points. A structure is:

Monochromatic: All 4 points share the same color.
Empty: No other point of the same color lies within the boundary of the structure (points of the opposite color act as "blockers").

The authors introduce the concept of Garment Numbers, denoted $G(S)$ , defined as the smallest integer $n$ such that every bichromatic set of $n$ points contains at least one empty monochromatic structure from a specific set $S$ of 4-point configurations.

The Five Structures:
The paper analyzes five specific geometric configurations of 4 points (see Figure 1 in the paper):

Cravat: The convex hull of 4 points in convex position.
Necklace: The union of two triangles sharing two consecutive vertices on the convex hull of 4 points in convex position.
Bowtie: A self-intersecting 4-gon (crossed quadrilateral) with 4 points in convex position.
Skirt: The convex hull of 4 points in non-convex position (one point inside the triangle of the other three).
Pant: A simple (non-self-intersecting) 4-gon on 4 points in non-convex position.

The Core Question:
What is the minimum $n$ such that any bichromatic set of size $n$ guarantees an empty monochromatic instance of a specific structure (or a disjunction of structures, e.g., $G(\text{pant} \lor \text{bowtie})$ )?

2. Methodology

The authors employ a combination of combinatorial geometry, inductive reasoning, and computational enumeration to establish bounds.

A. Inductive Framework (The "Garment" Logic)

A central tool is the notation $r \triangleright b$ , meaning "any set of $r$ red points requires at least $b$ blue points to block all red structures in set $S$ ."

Lemma 1 (Inductive Step): The paper proves that for settings involving "pants" ( $S = \{\text{pant}, \text{bowtie}\}$ or $S = \{\text{pant}, \text{necklace}\}$ ), if $r \triangleright b$ and $(r-1) \triangleright (b-1)$ , then $(r+1) \triangleright (b+1)$ .
Geometric Cases: The proof distinguishes between two cases based on the convex hull of the red points:
1. Removing a vertex from the convex hull does not decrease the hull size (Case 1).
2. Removing a vertex decreases the hull size (Case 2).
  This allows the authors to reduce large point sets to smaller, manageable sub-problems.

B. Computational Enumeration

For small point sets, the authors use exhaustive computer enumeration to verify specific blocking properties.

They verify base cases (e.g., $4 \triangleright 2 $,$ 5 \triangleright 3$) by checking all possible order types of small point sets.
They utilize known results on order types (e.g., the 2.3 billion order types of size 11) to verify that specific configurations cannot exist without an empty structure.

C. Island and Unbalanced Subset Arguments

For the "Necklace" setting (which lacks pants), the authors use a different approach:

Islands: A subset of points $I$ is an "island" if no points from the rest of the set lie inside its convex hull.
Unbalanced Islands: They prove that sufficiently large sets contain an island with a significant color imbalance (e.g., at least 5 more blue points than red).
Counting Argument: Using a theorem by Cravioto-Lagos et al. regarding interior-disjoint convex 4-holes, they show that if the color imbalance is large enough, there are not enough points of the minority color to block all potential structures of the majority color.

3. Key Contributions and Results

A. New Definitions and Framework

The paper formally defines "Garment numbers" and introduces the Necklace and Bowtie structures to the study of colored point sets, expanding beyond the traditional convex/non-convex dichotomy.

B. Improved Upper and Lower Bounds

The authors provide a comprehensive table (Table 1) of bounds for various combinations of structures. Key results include:

Setting (Structure Combination)	Lower Bound	Upper Bound	Status
Pant $\lor$ Bowtie	11	11	Solved (Exact value)
Pant $\lor$ Necklace	12	21	Improved
Necklace	14	1508	New Upper Bound
Cravat $\lor$ Skirt	35	$\infty$ (Open)	Lower bound improved
Cravat $\lor$ Pant	22	$\infty$ (Open)	Lower bound improved

Exact Solution: They prove $G(\text{pant} \lor \text{bowtie}) = 11$ . This is a significant result as it closes the gap for this specific combination.
New Upper Bounds:
- $G(\text{pant} \lor \text{necklace}) \le 21$ .
- $G(\text{necklace}) \le 1508$ (using the unbalanced island argument).
New Lower Bounds:
- Constructed specific point sets to prove $G(\text{cravat} \lor \text{skirt}) > 35$ and $G(\text{cravat} \lor \text{pant}) > 22$ .

C. The "Pants" vs. "Skirts" Distinction

The paper highlights a fundamental geometric difference:

Pants (and Bowties/Necklaces) generally require at least two points of the opposite color to be blocked effectively in certain configurations.
Skirts (and Cravats) can often be blocked by a single point.
This distinction explains why settings involving "pants" are more amenable to inductive proofs and have tighter bounds, while settings involving only "skirts" or "cravats" remain more difficult (with some bounds still open or infinite).

4. Significance

Advancing the Erdős–Szekeres Landscape: The paper moves the field beyond the existence of convex polygons to the existence of specific, complex monochromatic sub-structures in colored settings.
Resolving Open Problems: By proving $G(\text{pant} \lor \text{bowtie}) = 11$ , the authors solve a specific open case regarding the minimum number of points required to guarantee these structures.
Methodological Innovation: The introduction of "Garment numbers" provides a unified framework for analyzing 4-point structures. The use of "unbalanced islands" for the necklace problem offers a novel technique for handling settings where standard induction fails.
Future Directions: The paper identifies that the main remaining challenge lies in finding upper bounds for settings without pants (e.g., Cravat $\lor$ Skirt), suggesting that the "single blocker" nature of skirts makes them significantly harder to force in large sets.

5. Conclusion

This work provides a systematic exploration of how color constraints affect the geometric combinatorics of point sets. By defining new structures and establishing rigorous bounds, the authors deepen the understanding of the "Happy End Problem" in bichromatic settings, proving that for certain combinations of 4-point structures, the threshold for existence is surprisingly low (as low as 11 points), while for others, the problem remains wide open.