Trovata Soluzione Esatta per il Problema #272 di Erdős sulle Famiglie di Interi con Intersezioni in Progressione Aritmetica
Un nuovo articolo su arXiv (2607.23004) presenta valori esatti per t(N), la dimensione massima di una famiglia di sottoinsiemi distinti di {1,…,N} dove ogni intersezione a coppie è una progressione aritmetica non vuota, risolvendo il Problema #272 di Erdős per N piccolo. Gli autori determinano t(N) esattamente per tutti i 3 ≤ N ≤ 12 tramite calcolo esaustivo, confermando che il limite inferiore di Szabó è stretto in questo intervallo. Congetturano che t(N) = C(N,2) + 1 + floor((N-1)/4) per tutti gli N. Inoltre, dimostrano che il limite di Szabó è il massimo esatto per famiglie con un elemento comune (famiglie stellate). Questo lavoro si basa su risultati precedenti di Simonovits e Sós (che hanno dimostrato t(N)=O(N^2) e congetturato il valore ottimale) e Szabó (che ha migliorato il limite inferiore e stabilito asintotiche). La questione del nucleo—se qualche elemento appartiene a tutti gli insiemi di una famiglia estremale—rimane aperta.
Fatti principali
- L'articolo su arXiv:2607.23004 affronta il Problema #272 di Erdős.
- t(N) è il massimo t per cui esistono insiemi distinti A1,...,At ⊆ {1,…,N} con intersezioni in progressione aritmetica non vuote.
- Simonovits e Sós hanno dimostrato t(N)=O(N^2) e congetturato che C(N,2)+1 sia il miglior possibile.
- Szabó ha confutato la congettura con una costruzione che dà t(N) ≥ C(N,2)+1+floor((N-1)/4).
- Szabó ha dimostrato asintotiche t(N)=N^2/2+O(N^{5/3}(log N)^3).
- Szabó ha chiesto se t(N)=C(N,2)+O(N) e la questione del nucleo.
- Valori esatti per N=3 a 12 sono determinati tramite calcolo esaustivo.
- In questo intervallo, il limite inferiore di Szabó è esatto.
- Gli autori congetturano t(N)=C(N,2)+1+floor((N-1)/4) per tutti gli N.
- Dimostrato limite superiore per famiglie con un elemento comune (famiglie stellate).
Entità
Istituzioni
- arXiv