Exact values and exact upper bounds for families of integers with arithmetic progression intersections (Erd\H{o}s Problem #272)

Resumo Técnico: Valores Exatos e Limites Superiores Exatos para Famílias de Inteiros com Interseções de Progressões Aritméticas

Enunciado do Problema
O artigo aborda o Problema de Erdős #272, que busca determinar a função $t(N)$, definida como o número máximo de subconjuntos distintos $A_1, \dots, A_t \subseteq \{1, \dots, N\}$ tais que a interseção de quaisquer dois conjuntos distintos $A_i \cap A_j$ seja uma progressão aritmética (PA) não vazia.

Historicamente, Simonovits e Sós estabeleceram que $t(N) = O(N^2)$ e conjecturaram que o máximo é alcançado pela família de todos os subconjuntos de tamanho no máximo 3 que contêm um elemento fixo, gerando um limite de $\binom{N}{2} + 1$. Szabó posteriormente refutou essa conjectura de exatidão ao construir uma família que atinge $t(N) \ge \binom{N}{2} + 1 + \lfloor (N-1)/4 \rfloor$. Szabó também estabeleceu o comportamento assintótico $t(N) = N^2/2 + O(N^{5/3}(\log N)^3)$ e propôs duas questões críticas: (i) se $t(N) = \binom{N}{2} + O(N)$, e (ii) a "questão do núcleo" (kernel question), perguntando se toda família extremal (uma que atinge o tamanho máximo) deve conter um elemento comum compartilhado por todos os seus conjuntos.

Metodologia
Os autores empregam uma abordagem híbrida combinando verificação computacional exaustiva, combinatória estrutural e técnicas de limitação analítica:

1. Computação Exata: Para $N$ pequeno ($N \le 12$), o problema é modelado como a busca pelo clique máximo em um grafo onde os vértices são subconjuntos não vazios de $[N]$ e as arestas conectam conjuntos com interseções de PA não vazias.
   • Para $N \le 10$, foi utilizado um resolvedor de branch-and-bound com paralelismo de bits e limites de coloração gulosa (greedy coloring).
   • Para $N=11$ e $12$, uma busca de decisão utilizando decomposição de raiz, ordenação de degenerescência, descascamento de núcleo (core peeling) e uma etapa rigorosa de "poda de estrela" (star pruning) foi empregada para provar a inexistência de famílias maiores.
2. Decomposição Estrutural: A prova para o limite superior geral baseia-se na decomposição de uma família "estrelada" (uma com um elemento comum $m$) em subconjuntos de tamanho $\le 2$, tamanho $3$ e tamanho $\ge 4$.
3. Desigualdade de Contagem de Defeito-Um: Uma ferramenta técnica central é uma desigualdade de contagem para "regiões de escada" (famílias de intervalos de inteiros que contêm 0). Os autores provam que, para qualquer tal família, o número de membros é limitado pelo número de "pares ruins" (pares $\{u,v\}$ tais que $\{0,u,v\}$ não é uma PA) que eles cobrem, mais um termo de defeito pequeno. Isso é verificado via um programa dinâmico exato para parâmetros até 500 e um argumento assintótico usando formas quadráticas definidas positivas para parâmetros maiores.
4. Teorema do Par Privado: Um teorema estrutural é estabelecido mostrando que todo membro "torto" (crooked member) (um conjunto de tamanho $\ge 4$ que não é uma PA) contém um "par ruim privado"—um par de elementos não contido em nenhum outro membro da família. Isso impede o compartilhamento de "mortes" (kills - pares ruins) entre membros que não são PA, permitindo uma contagem de limite apertado.

Principais Contribuições e Resultados

• Valores Exatos para $N$ Pequeno: O artigo determina $t(N)$ exatamente para $N = 3, \dots, 12$. Os valores são $4, 7, 12, 17, 23, 30, 39, 48, 58, 69$. Em todo este intervalo, o limite inferior de Szabó é exato. A sequência não aparece atualmente no OEIS.
• Conjectura Refinada: Com base na evidência computacional, os autores conjecturam que, para todo $N \ge 1$:
  $$t(N) = \binom{N}{2} + 1 + \left\lfloor \frac{N-1}{4} \right\rfloor$$
  Isso refina a questão assintótica de Szabó para uma fórmula exata.
• Limite Superior Exato para Famílias Estreladas: O principal resultado teórico (Teorema 1.4) prova que, para qualquer família estrelada (onde todos os conjuntos compartilham um elemento comum), o tamanho é limitado pelo limite inferior de Szabó. Este é o primeiro limite superior exato deste tipo conhecido para qualquer $N \ge 5$.
  • A prova combina a desigualdade de contagem de "defeito-um" com o "teorema do par privado" para lidar com membros que não são PA.
• Redução à Questão do Núcleo: Os autores demonstram que a conjectura refinada (de que a fórmula se aplica a todo $N$) segue imediatamente se a conjectura do núcleo de Szabó for verdadeira (ou seja, se toda família extremal for estrelada). Assim, o problema de determinar $t(N)$ exatamente é reduzido a provar que famílias extremais devem ter um elemento comum.
• Restrições Estruturais sobre Contraexemplos: O artigo analisa a estrutura hipotética de uma família extremal não-estrelada (um contraexemplo à conjectura do núcleo). Eles provam que, se tal família existir, seus triplas devem compartilhar um elemento comum, e quaisquer membros que evitem esse elemento devem ser progressões aritméticas longas com diferenças pequenas. Os autores argumentam que tais configurações são "autolimitantes" e improváveis de atingir o limite conjecturado, embora uma prova completa permaneça em aberto.

Significância
O artigo afirma fornecer a primeira determinação exata de $t(N)$ para qualquer $N \ge 5$ (especificamente $N \le 12$) e estabelece o primeiro limite superior exato para a classe restrita de famílias estreladas. Ao provar que o limite inferior é exato para todas as famílias estreladas, o trabalho isola a "propriedade do núcleo" como o único obstáculo restante para resolver completamente o Problema de Erdős #272. Os autores observam que seus resultados confirmam que a construção de Szabó é ótima dentro da classe de famílias que compartilham um elemento comum, e fornecem as primeiras restrições estruturais rigorosas sobre como seria um potencial contraexemplo não-estrelado. O trabalho também introduz novas técnicas combinatórias, especificamente a desigualdade de contagem de defeito-um e o teorema do par privado, que podem ser aplicáveis a outros problemas de interseção.