Kombinatorikus nulltétel

A kombinatorikus nullatétel (Alon-tétel, kombinatorikus nullstellensatz ) egy algebrai tétel , amely egy polinom együtthatóját egy bizonyos monomnál viszonyítja az értékekhez. A tétel alacsonyabb becslést ad egy olyan kombinatorikus paralelepipedon méreteire, amelyen a polinom nem azonos nullával. Ez a becslés az egyes változókban lévő vezető monom mértékétől függ.

Történelem

A tételt először Noga Alon és Michel Tarcy [1] 1989-es tanulmányában bizonyította és alkalmazta, majd Alon, Natanzon és Ruzsa fejlesztette tovább 1995–1996-ban. Alon újrafogalmazta 1999-ben. [2]

tétel állítása

Továbbá a bejegyzés egy polinom együtthatóját jelenti egy polinomban lévő monomnál . $[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f(x_{1},\dots ,x_{n})$ $f$ ${x_{1}}^{d_{1}}\pontok {x_{n}}^{d_{n}}$ $f$

Legyen polinom valamilyen mező felett , és annak vezető monomija abban az értelemben, hogy bármely másik (nullatól eltérő együtthatójú) monomban legalább egy változó mértéke kisebb, mint az adott változóban. $f(x_{1},\dots ,x_{n})$ $K$ ${x_{1}}^{d_{1}}{x_{2}}^{d_{2}}\dots {x_{n}}^{d_{n}}$

A tétel kimondja, hogy ha , akkor minden kardinalitású halmazhoz vannak olyanok , amelyek . $[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f\not =0$ $A_{1},\pontok,A_{n}$ $|A_{i}|\geq d_{i}+1$ $a_{i}\in A_{i}$ $f(a_{1},\dots ,a_{n})\not =0$

Interpolációs polinom

A tétel közvetlenül következik a Lagrange-interpolációs polinomképlet egy fokszámú polinomra vonatkozó általánosításából . $f(x)=\sum \limits _{i=0}^{n}{y_{i}\prod \limits _{i\not =j}{\frac {x-x_{j)) {x_{i}-x_{j}}}}$ $f$ $n$

A Lagrange-képletből elkülönítheti a polinom vezető együtthatóját . Konkrétan a jobb oldal minden n − 1 fokú polinomon eltűnik. $[x^{n}]f=\sum \limits _{i=0}^{n}{{y_{i}}\prod \limits _{i\not =j}{\frac {1 }{x_{i}-x_{j}}}}$

Ezért egy adott monomiális fokra vonatkozó feltétel mellett ez a képlet általánosított: a jobb oldal ${x_{1}}^{d_{1}}\pontok {x_{n}}^{d_{n}}$

$[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f=\sum \limits _{a_{1}\in A_ {1}}\dots \sum \limits _{a_{n}\in A_{n}}{\frac {f(a_{1},\dots ,a_{n})}{\prod \limits _{ a_{1}\not =b_{1}\in A_{1}}\dots \prod \limits _{a_{n}\not =b_{n}\in A_{n}}{(a_{1} -b_{1})\pontok (a_{n}-b_{n})}}}$

csak attól függhet , ahonnan az egyenlőség és nyilvánvalóan a nullatétel következik. ${\textstyle [{{x_{1}}^{d_{1}}\pontok {x_{n}}^{d_{n}}}]f}$

Alkalmazások

A kombinatorikus nullatétel használható létezési tételek bizonyítására , amikor egy polinom nullától eltérő értékének létezése egy bizonyos ponton azt jelenti, hogy valamilyen objektum kielégíti a kívánt tulajdonságot, és az összes objektum halmaza (amelyek között a létezést igazolni kell) egy az egyhez képest a lehetséges változóértékkészletek halmazához képest.

Alon-Friedland-Kalai tétel

Tekintsük például a következő tételt:

Legyen egy prímszám és a gráf esetében a maximális fok és az átlagos fok . $p$ $G=(V,E)$ $\Delta (G)\leq 2p-1$ ${\frac {2|E|}{|V|}}>2p-2$

Ekkor van egy -reguláris részgráf -ban . [3] $G$ $p$

Jelölje a csúcsgal szomszédos élek halmazával . A tétel bizonyításához vegyünk egy polinomot a mezőben (modulo ) a gráf éleinek megfelelő változókban. $E(v)$ $v$ ${\displaystyle {\mathbb {Z} }_{p))$ $p$ $|E|$

$P(x_{1},\dots ,x_{|E|})=\prod \limits _{v\in V}{\left({1-\left({\sum \limits _{e \in E(v)}{x_{e}}}\right)^{p-1}}\right)}-\prod \limits _{e\in E}(1-x_{e})$

Ebben a polinomban a legmagasabb monom együtthatója nem egyenlő nullával. Ugyanakkor nyilván . Ezért van egy olyan nem üres élhalmaz, hogy ha ezekre és a többiekre tesszük , akkor az ilyen halmaz polinomja nullától eltérő értéket vesz fel. $\prod \limits _{e\in E}{x_{e}}$ $P(0,\pontok ,0)=0$ $x_{e}=1$ $x_{e}=0$

Mivel a kivont nulla minden nullától eltérő halmazon, ezért a vizsgált halmazban mindenre , vagyis ezen élek részgráfjában a csúcsok minden foka többszöröse . És mivel ezek mind szigorúan kisebbek, mint feltétel szerint, akkor a nulla fokos csúcsok eltávolításával egy nem üres -reguláris részgráfot kapunk. $P$ $\sum \limits _{e\in E(v)}{x_{e}}\equiv 0\ (mod\ p)$ $v$ $p$ $2p$ $p$

A Cauchy-Davenport-tétel megerősítése

A következő egy prímszám. $p$

A Cauchy-Davenport tétel, amely kimondja, hogy -re, viszonylag könnyen igazolható elemi módszerekkel. $|A+B|=|\{{a+b:a\in A,b\in B}\}|\geq \min\{{p,|A|+|B|-1}\ }$ ${\displaystyle A\subset {\mathbb {Z} }_{p},B\subset {\mathbb {Z} }_{p))$

Azonban még nem találtak olyan kombinatorikus bizonyítékot, amely erősítené a formát . De ez könnyen bebizonyítható a kombinatorikus nulla tételen keresztül. [négy] $|A\oplus B|=|\{{a+b:a\in A,b\in B,a\not =b}\}|\geq \min\{{p,|A|+ |B|-2}\}$ $A\subset {\mathbb {Z} }_{p},B\subset {\mathbb {Z} }_{p},A\not =B$

Bizonyítsuk be ezt az erősödést ellentmondásokkal. Feltételezzük, hogy , mert különben néhány elem egyszerűen eltávolítható a halmazokból. $|A|+|B|-2\leq p$

Ha , akkor a tétel állítása megfelel az eredeti Cauchy-Davenport tétel állításának. Ha , akkor mivel , használhatjuk azt a tényt, hogy és indukciót hajthatunk végre a és a legkisebb halmazok méretére . $|A|=|B|$ $A \cap B = \varnothing$ $A\cap B\not =\varnothing$ $A\not =B$ $(A\cap B)\oplus (A\cup B)\subset A\oplus B$ $A$ $B$

Ezért elegendő az esetet megvizsgálni . Hagyjuk és . Tekintsünk egy polinomot . Ennek a polinomnak kifejezetten nullától eltérő együtthatója van a monomnál , amelyet a binomiális együtthatók különbségével fejezünk ki. Azonban , ez a polinom mindig eltűnik, ami ellentmond a kombinatorikus nulla tételnek. $|A|\not =|B|$ $(A\oplus B)\subset C$ $|C|=|A|+|B|-3$ ${\displaystyle (xy)\prod \limits _{c\in C}{(x+yc)))$ $p$ $x^{|A|-1}y^{|B|-1}$ $x\in A$ $y\in B$

Lásd még

Jegyzetek

↑ Alon, Noga ; Tarsi, Michael. Egy sehol nulla pont a lineáris leképezésekben (neopr.) . - 1989. - T. 9 , 4. sz . - S. 393-395 . - doi : 10.1007/BF02125351 .
↑ Alon, Noga . Kombinatorikus Nullstellensatz (neopr.) . - 1999. - V. 8 , 1-2. sz . - S. 7-29 . - doi : 10.1017/S0963548398003411 .
↑ Alon nulla tétele és alkalmazásai, MIPT, 2014 tavasz . Letöltve: 2016. február 12. Az eredetiből archiválva : 2016. november 17.. (határozatlan)
↑ Additív kombinatorika, videoelőadások nyílt könyvtára, P. L. Csebisevről elnevezett matematikai laboratórium