Beck–Fiala-satsen

Inom matematiken är Beck–Fiala-satsen en storsats inom diskrepansteorin på grund av József Beck och Tibor Fiala. Diskrepans handlar om att färga element i en grundsats så att varje uppsättning i ett visst uppsättningssystem är så balanserat som möjligt, dvs har ungefär samma antal element av varje färg. Beck–Fiala-satsen handlar om fallet där varje element inte förekommer många gånger över alla mängder. Satsen garanterar att om varje element dyker upp högst t gånger, så kan elementen färgas så att obalansen är högst 2 t − 1 .

Påstående

Formellt givet ett universum

$[n]=\{1,\ldots ,n\}$

och en samling delmängder

$S_{1},S_{2},\ldots ,S_{m}\subseteq [n]$

så att för varje $i\in [n]$ ,

$\vert \{j:i\in S_{j}\}\vert \leq t,$

då kan man hitta ett uppdrag

$x:[n]\högerpil \{-1,+1\}$

Så att

$|x(S_{j})|\leq 2t-1,\forall j{\text{ där }}x(S_{j}):=\summa _{i\i S_{j}}x_ {i}.$

Bevisskiss

Beviset är baserat på ett enkelt linjärt-algebraiskt argument. Börja med $x_{i}=0$ för alla element och anropa alla variabler som är aktiva i början.

Tänk bara på uppsättningar med $\vert S_{j}\vert >t$ . Eftersom varje element visas högst $t$ gånger i en uppsättning, finns det färre än $n$ sådana uppsättningar. Framtvinga nu linjära begränsningar $\sum _{i\in S_{j}}x_{i}=0$ för dem. Eftersom det är ett icke-trivialt linjärt delrum av $\mathbf {R} ^{n}$ med färre begränsningar än variabler, finns det en lösning som inte är noll. Normalisera denna lösning, och åtminstone ett av värdena är antingen $+1,-1$ . Ställ in detta värde och inaktivera denna variabel. Ignorera nu uppsättningarna med mindre än $t$ aktiva variabler. Och upprepa samma procedur och upprätthålla de linjära begränsningarna att summan av aktiva variabler för varje återstående uppsättning fortfarande är densamma. Med samma räkneargument finns det en icke-trivial lösning, så man kan ta linjära kombinationer av denna med den ursprungliga tills något element blir $+1,-1$ , Upprepa tills alla variabler är inställda.

När väl en uppsättning ignoreras är summan av värdena för dess variabler noll och det finns högst $t$ oinställda variabler. Förändringen av dessa kan öka $|x(S_{j})|$ till högst $2t-1$ .

• József Beck och Tibor Fiala (1981). " Satser för "heltalsskapande"" . Diskret tillämpad matematik . 3 (1): 1–8. doi : 10.1016/0166-218X(81)90022-6 .
•   Chazelle, Bernard (2000). Diskrepansmetoden: slumpmässighet och komplexitet . New York: Cambridge University Press. ISBN 0-521-77093-9 .