Garment numbers of bi-colored point sets in the plane

Este artigo investiga variantes coloridas de problemas geométrico-combinatórios sobre polígonos vazios, estabelecendo novos limites inferiores e superiores para o menor número de pontos em um conjunto bicoloreado no plano que garante a existência de estruturas monocromáticas específicas com quatro pontos.

O essencial

Imagine que você tem uma caixa cheia de pontos no chão. Alguns pontos são vermelhos e outros são azuis. Eles estão espalhados de forma que nenhum três deles formem uma linha reta (isso é o que os matemáticos chamam de "posição geral").

O objetivo deste artigo é responder a uma pergunta divertida: Quantos pontos (vermelhos e azuis juntos) precisamos ter no chão para garantir que, não importa como eles estejam espalhados, sempre existirá um "desenho" especial feito apenas de pontos da mesma cor, que não tenha nenhum ponto da outra cor "sentado" dentro dele?

Os autores chamam esses desenhos de "Garments" (Roupas), como se cada um fosse um tipo de peça de vestuário geométrico.

1. O que são essas "Roupas"?

O artigo foca em desenhos feitos com exatamente 4 pontos. Eles definiram 5 tipos de "roupas" diferentes, dependendo da forma como os pontos se conectam:

• Gravata (Cravat): É um quadrado perfeito (ou qualquer quadrilátero) onde os 4 pontos formam os cantos de uma caixa. É o mais simples.
• Colar (Necklace): Imagine dois triângulos que compartilham um lado, formando uma forma de "8" ou de um colar de contas.
• Laço (Bowtie): É como um laço de gravata de verdade. Os pontos formam um quadrilátero que se cruza no meio (como um X).
• Saia (Skirt): É um triângulo grande com um ponto "escondido" dentro dele. A forma final parece uma saia.
• Calça (Pant): É um quadrilátero simples (não cruza), mas com um dos pontos "entrando" para dentro, fazendo a forma parecer uma calça com duas pernas.

A Regra do Jogo:
Para que uma "roupa" seja considerada válida (ou "vazia"), ela deve ser feita apenas de pontos vermelhos (ou apenas de azuis) e não pode ter nenhum ponto da cor oposta no seu interior. Se houver um ponto azul dentro de uma "calça" vermelha, a calça está "bloqueada" e não conta.

2. O Problema Principal: O "Número da Roupa"

Os matemáticos querem saber: Qual é o número mágico?
Se eu tiver 10 pontos, será que sempre consigo encontrar uma "calça" vermelha vazia? E se tiver 20? E se tiver 100?

Esse número mágico é chamado de Número da Roupa (Garment Number).

• Se o número for 11, significa que com 11 pontos, você garantidamente encontrará pelo menos uma dessas roupas vazias.
• Se o número for infinito, significa que você pode espalhar pontos para sempre sem nunca conseguir formar essa roupa vazia.

3. O que os autores descobriram?

Eles usaram lógica, geometria e até computadores para descobrir limites para essas "roupas".

• O mistério da "Calça" e do "Laço": Eles provaram que se você tiver 11 pontos (vermelhos e azuis misturados), você sempre conseguirá encontrar uma "calça" vazia ou um "laço" vazio de uma única cor. Isso é ótimo! É um número pequeno e definitivo.
• O mistério da "Saia" e da "Gravata": Aqui a coisa é mais difícil. Eles sabem que você precisa de pelo menos 35 pontos para garantir uma "saia" ou "gravata" vazia (baseado em exemplos que eles construíram), mas não sabem qual é o limite máximo exato. Pode ser que você precise de 100, ou 1000 pontos. Ainda é um mistério.
• O mistério do "Colar": Eles provaram que, se você tiver 1508 pontos, garantidamente encontrará um "colar" vazio. É um número grande, mas é um limite seguro.

4. Analogia da Festa

Pense em uma festa onde há convidados de duas cores de camisa: Vermelho e Azul.

• Os matemáticos são os organizadores que querem garantir que, em algum lugar da festa, exista um grupo de 4 pessoas da mesma cor formando um círculo (ou uma forma específica) onde ninguém da outra cor esteja sentado dentro desse círculo.
• Se houver apenas 10 pessoas, talvez os organizadores azuis consigam sentar-se estrategicamente no meio de todos os grupos vermelhos para "estragar" o desenho.
• Mas, se houver 11 pessoas, os organizadores mostram que é impossível que os azuis consigam bloquear todos os grupos vermelhos de fazerem uma "calça" ou um "laço". Alguém vai conseguir fazer o desenho limpo.

5. Por que isso importa?

Pode parecer apenas um jogo de pontos, mas isso faz parte de uma área da matemática chamada Geometria Combinatória, que estuda como objetos se organizam no espaço.

• Isso ajuda a entender a estrutura fundamental do espaço e da ordem.
• Tem aplicações em computação gráfica, robótica (como robôs evitam obstáculos) e até em como organizamos dados.
• O artigo é importante porque fecha algumas portas (provando que 11 pontos bastam para certas formas) e abre outras (mostrando que para outras formas, ainda precisamos de muito mais pesquisa).

Resumo final:
Os autores criaram um "guarda-roupa" de formas geométricas (gravata, colar, laço, saia, calça) e descobriram quantas "pessoas" (pontos) são necessárias em uma festa colorida para garantir que, inevitavelmente, alguém consiga formar uma dessas roupas sem ser "invadido" pela cor oposta. Eles resolveram alguns mistérios (como o da calça e do laço) e deixaram outros para serem resolvidos no futuro.

Resumo técnico

Resumo Técnico: Números de Vestuário de Conjuntos de Pontos Bicoloridos

1. Problema e Contexto

O artigo aborda variações coloridas de problemas geométrico-combinatórios clássicos, iniciados por Erdős e Szekeres em 1935 (o "Problema do Fim Feliz"). O problema original busca um limite $ES(k)$ tal que qualquer conjunto de pontos em posição geral no plano contenha um subconjunto de $k$ pontos que formem um $k$-gono convexo.

Neste trabalho, o foco desloca-se para conjuntos bicoloridos (pontos vermelhos e azuis) no plano. O objetivo é determinar a existência de estruturas monocráticas (todos os pontos da mesma cor) que sejam vazias (não contenham pontos da outra cor em seu interior ou fronteira).

• O Desafio Central: Para $k=4$, é um problema em aberto saber se, para qualquer conjunto bicolorido suficientemente grande, existe sempre um quadrilátero monocrático, convexo e vazio.
• A Contribuição Específica: Os autores investigam a existência de cinco estruturas específicas que utilizam exatamente 4 pontos, indo além da simples distinção entre convexo/não-convexo. Eles introduzem novas estruturas e definem um novo parâmetro: o Número de Vestuário (Garment Number).

2. Definições e Estruturas

O artigo define cinco tipos de estruturas baseadas em 4 pontos ($P$), classificadas pela posição de seus vértices (convexa ou não convexa) e pela topologia da figura formada:

1. Cravat (Gravata): 4 pontos em posição convexa; é a casca convexa (convex hull) desses pontos.
2. Necklace (Colar): 4 pontos em posição convexa; união de dois triângulos que compartilham exatamente dois pontos consecutivos na casca convexa.
3. Bowtie (Laço): 4 pontos em posição convexa; um quadrilátero auto-intersectante.
4. Skirt (Saia): 4 pontos em posição não convexa; a casca convexa desses pontos (que terá 3 vértices).
5. Pant (Calça): 4 pontos em posição não convexa; um quadrilátero simples (não auto-intersectante).

Conceito de "Bloqueio": Uma estrutura é considerada vazia se não houver pontos da cor oposta dentro de sua fronteira. Se um ponto da cor oposta estiver presente, a estrutura é "bloqueada".

Número de Vestuário ($G(S)$): É definido como o menor inteiro $n$ tal que todo conjunto bicolorido de $n$ pontos contém pelo menos uma estrutura vazia monocrática do conjunto de tipos $S$. Se tal $n$ não existir, $G(S) = +\infty$.

3. Metodologia

Os autores utilizam uma combinação de raciocínio indutivo, análise de casos (casework) e enumeração computacional para estabelecer limites superiores e inferiores.

• Relação de Bloqueio ($r \triangleright b$): Introduzem a notação $r \triangleright b$ para indicar que um conjunto de $r$ pontos de uma cor requer pelo menos $b$ pontos da outra cor para bloquear todas as estruturas possíveis desse conjunto.
• Argumento Indutivo (Lema 1): Demonstram que, para certos conjuntos de estruturas (especificamente envolvendo "Pant"), se $r \triangleright b$ e $(r-1) \triangleright (b-1)$, então $(r+1) \triangleright (b+1)$. Isso permite escalar limites pequenos para grandes conjuntos.
• Análise de Casos e Enumeração: Para pequenos números de pontos (ex: 4 a 11 pontos), realizam uma verificação exaustiva (muitas vezes assistida por computador) para determinar quantos pontos da cor oposta são necessários para bloquear todas as configurações possíveis.
• Teorema de Erdős-Szekeres: Utilizam o teorema clássico sobre $k$-gonos convexos para encontrar subconjuntos desequilibrados (com diferença significativa entre o número de pontos vermelhos e azuis) dentro de grandes conjuntos, garantindo a existência de estruturas vazias.

4. Resultados Principais

O artigo estabelece novos limites superiores e inferiores para o Número de Vestuário em várias configurações. A Tabela 1 do artigo resume os resultados, destacando as seguintes descobertas:

• Configuração {Pant, Bowtie}:

  • Resultado: $G(\text{pant} \lor \text{bowtie}) = 11$.
  • Detalhe: O artigo prova que qualquer conjunto de 11 pontos contém um "Pant" ou "Bowtie" monocrático e vazio. O limite inferior é 10 (existem conjuntos de 10 pontos sem essas estruturas). A prova envolve a análise de camadas convexas e a aplicação do lema indutivo.

• Configuração {Pant, Necklace}:

  • Resultado: $G(\text{pant} \lor \text{necklace}) \le 21$.
  • Método: Usa-se o fato de que qualquer conjunto de 11 pontos contém um 6-gono convexo ou um 5-gono com um ponto interno. Combinado com a relação indutiva, isso limita o número necessário a 21.

• Configuração {Necklace} (Apenas Colar):

  • Resultado: $G(\text{necklace}) \le 1508$.
  • Método: Utiliza-se o teorema de Erdős-Szekeres para encontrar um subconjunto convexo de 9 pontos desequilibrado (diferença de pelo menos 5 entre as cores). Aplica-se um teorema sobre 4-holes (quadriláteros vazios) para mostrar que não há pontos suficientes da cor minoritária para bloquear todos os quadriláteros convexos da cor majoritária.

• Limites Inferiores (Contra-exemplos):

  • $G(\text{bowtie} \lor \text{pant}) > 10$
  • $G(\text{bowtie} \lor \text{skirt}) > 12$
  • $G(\text{necklace} \lor \text{pant}) > 12$
  • $G(\text{necklace}) > 14$
  • $G(\text{cravat} \lor \text{pant}) > 22$
  • $G(\text{cravat} \lor \text{skirt}) > 35$
  • Nota: O limite inferior para a existência de um quadrilátero convexo vazio (Cravat) permanece $>46$ (baseado em trabalhos anteriores), mas o artigo melhora o entendimento das estruturas não convexas.

5. Significado e Conclusão

• Avanço Teórico: O trabalho fornece uma compreensão mais profunda da geometria de conjuntos bicoloridos, mostrando que a introdução de estruturas não convexas (como "Pants" e "Bowties") e a combinação de diferentes tipos de estruturas alteram drasticamente os limites de existência.
• Diferenciação de Estruturas: Uma descoberta chave é a diferença fundamental entre estruturas que requerem 1 ponto para bloquear (como "Skirt", que tem casca convexa de tamanho 3) e aquelas que requerem 2 ou mais pontos (como "Pant"). Isso explica por que configurações sem "Pants" são mais difíceis de resolver (limites superiores desconhecidos ou muito altos).
• Ferramentas Computacionais: O artigo destaca o uso de verificação computacional de tipos de ordem (order types) para pequenos conjuntos de pontos, uma metodologia essencial para problemas de geometria combinatória onde a intuição pura falha.
• Futuro: O trabalho estabelece uma base para explorar sistematicamente o bloqueio de estruturas de 4 pontos. A principal questão em aberto permanece a determinação de limites superiores para configurações que não incluem "Pants" e o fechamento da lacuna entre os limites inferiores e superiores para o quadrilátero convexo vazio (Cravat).

Em suma, o artigo redefine o problema de Erdős-Szekeres para cenários coloridos e não-convexos, introduzindo uma nova terminologia ("Garment numbers") e fornecendo limites rigorosos que conectam a teoria dos grafos geométricos com a combinatória de pontos.