Yasak alt grafik sorunu - Forbidden subgraph problem

İçinde aşırı grafik teorisi, yasak alt grafik problemi aşağıdaki problem: bir grafik verilmiş ${displaystyle G}$, maksimum kenar sayısını bulun ${displaystyle operatorname {ex} (n, G)}$ içinde ${displaystyle n}$-vertex grafiği olmayan alt grafik izomorf -e ${displaystyle G}$. Bu içerikte, ${displaystyle G}$ denir yasak alt grafik.^[1]

Eşdeğer bir problem, bir ${displaystyle n}$-vertex grafiği, alt grafiğinin izomorfik olduğunu garanti eder. ${displaystyle G}$?^[2]

Tanımlar

aşırı sayı ${displaystyle operatorname {ex} (n, G)}$ bir içindeki maksimum kenar sayısıdır ${displaystyle n}$- alt grafik izomorfik içermeyenvertex grafiği ${displaystyle G}$. ${displaystyle K_ {r}}$ ... tam grafik açık ${displaystyle r}$ köşeler. ${displaystyle T (n, r)}$ ... Turán grafiği: tam ${displaystyle r}$-partit grafik üzerinde ${displaystyle n}$ köşeler, parçalar arasında olabildiğince eşit olarak dağıtılmış. kromatik sayı ${displaystyle chi (G)}$ nın-nin ${displaystyle G}$ köşelerini renklendirmek için gereken minimum renk sayısıdır ${displaystyle G}$ öyle ki bitişik iki köşe aynı renge sahip değildir.

Sonuçlar

İki parçalı olmayan grafikler

'Turán teoremi '. Pozitif tamsayılar için ${displaystyle n, r}$ doyurucu ${displaystyle ngeq rgeq 3}$,^[3] ${extstyle operatorname {ex} (n, K_ {r}) = left (1- {frac {1} {r-1}} ight) {frac {n ^ {2}} {2}}.}$

Bu, yasak alt grafik problemini çözer ${displaystyle G = K_ {r}}$. Turán teoremi için eşitlik durumları Turán grafiği ${displaystyle T (n, r-1)}$.

Bu sonuç rastgele grafiklere genelleştirilebilir ${displaystyle G}$ dikkate alarak kromatik sayı ${displaystyle chi (G)}$ nın-nin ${displaystyle G}$. Bunu not et ${displaystyle T (n, r)}$ ile renklendirilebilir ${displaystyle r}$ renklidir ve bu nedenle kromatik numarası şundan büyük olan alt grafiği yoktur. ${displaystyle r}$. Özellikle, ${displaystyle T (n, chi (G) -1)}$ izomorfik alt grafikleri yoktur ${displaystyle G}$. Bu, yasak alt grafik problemi için genel eşitlik davalarının, aşağıdaki eşitlik davalarıyla ilgili olabileceğini düşündürmektedir. ${displaystyle G = K_ {r}}$. Bu sezginin doğru olduğu ortaya çıktı. ${displaystyle o (n ^ {2})}$ hata.

'Erdős-Taş teoremi '. Tüm pozitif tamsayılar için ${displaystyle n}$ ve tüm grafikler ${displaystyle G}$,^[4]${extstyle operatorname {ex} (n, G) = left (1- {frac {1} {chi (G) -1}} + o (1) ight) {frac {n ^ {2}} {2}} .}$

Ne zaman ${displaystyle G}$ çift ​​taraflı değildir, bu bize birinci dereceden bir yaklaşım verir. ${displaystyle operatorname {ex} (n, G)}$.

İkili grafikler

İki parçalı grafikler için ${displaystyle G}$Erdős-Stone teoremi sadece bize şunu söyler: ${görüntü stili operatör adı {örnek} (n, G) = o (n ^ {2})}$. İki parçalı grafikler için yasak alt grafik problemi, Zarankiewicz sorunu ve genel olarak çözülmedi.

Zarankiewicz problemindeki ilerleme aşağıdaki teoremi içerir:

Kővári – Sós – Turán teoremi. Her pozitif tam sayı çifti için ${displaystyle s, t}$ ile ${displaystyle tgeq sgeq 1}$bazı sabitler var ${displaystyle C}$ (dan bağımsız ${displaystyle n}$) öyle ki ${extstyle operatorname {ex} (n, K_ {s, t}) leq Cn ^ {2- {frac {1} {s}}}}$ her pozitif tam sayı için ${displaystyle n}$.^[5]

İki parçalı grafikler için başka bir sonuç, çift döngüler durumudur, ${displaystyle G = C_ {2k}, kgeq 2}$. Döngüler bile, bir kök tepe noktası ve bu tepe noktasından çıkan yollar dikkate alınarak ele alınır. Aynı uzunlukta iki yol ${displaystyle k}$ aynı uç noktaya sahiptirler ve çakışmazlarsa, bir uzunluk döngüsü oluştururlar ${displaystyle 2k}$. Bu, aşağıdaki teoremi verir.

Teorem (Bondy ve Simonovits, 1974). Bazı sabitler var ${displaystyle C}$ öyle ki ${extstyle operatorname {ex} (n, C_ {2k}) leq Cn ^ {1+ {frac {1} {k}}}}$ her pozitif tam sayı için ${displaystyle n}$ ve pozitif tam sayı ${displaystyle kgeq 2}$.^[6]

Güçlü bir lemma aşırı grafik teorisi dır-dir bağımlı rastgele seçim. Bu lemma, iki parçalı grafikleri sınırlı derece ile tek parçada işlememize izin verir:

Teorem (Alon, Krivelevich, ve Sudakov, 2003). İzin Vermek ${displaystyle G}$ köşe bölümleri olan iki parçalı bir grafik olun ${displaystyle A}$ ve ${displaystyle B}$ öyle ki her köşe ${displaystyle A}$ en fazla derecesi var ${displaystyle r}$. Sonra sabit bir sabit var ${displaystyle C}$ (sadece şuna bağlıdır ${displaystyle G}$) öyle ki ${extstyle operatorname {ex} (n, G) leq Cn ^ {2- {frac {1} {r}}}}$her pozitif tam sayı için ${displaystyle n}$.^[7]

Genel olarak aşağıdaki varsayımımız var:

Rasyonel Üsler Varsayımı (Erdős and Simonovits). Herhangi bir sonlu aile için ${displaystyle {mathcal {L}}}$ iki bölümlü varsa grafiklerin ${displaystyle Lin {mathcal {L}}}$o zaman bir rasyonel var ${displaystyle alpha in [0,1)}$ öyle ki ${displaystyle operatorname {ex} (n, {mathcal {L}}) = Theta (n ^ {1 + alpha})}$.^[8]

Tarafından bir anket Füredi ve Simonovits Yasaklanmış alt grafik sorunundaki ilerlemeyi daha ayrıntılı olarak açıklar.^[8]

Alt sınırlar

Herhangi bir grafik için ${displaystyle G}$, aşağıdaki alt sınıra sahibiz:

Önerme. ${displaystyle operatorname {ex} (n, G) geq cn ^ {2- {frac {v (G) -2} {e (G) -1}}}}$ bazı sabitler için ${displaystyle c}$.^[9]

Kanıt. Bir teknik kullanıyoruz olasılık yöntemi "değişiklik yöntemi". Bir düşünün Erdős – Rényi rastgele grafiği ${displaystyle G (n, p)}$, yani bir grafik ${displaystyle n}$ köşeler ve herhangi iki köşe arasında olasılıkla bir kenar çizilir ${displaystyle p}$, bağımsız. Beklenen kopya sayısını bulabiliriz ${displaystyle G}$ içinde ${displaystyle G (n, p)}$ tarafından beklentinin doğrusallığı. Ardından, bu tür her kopyadan bir kenar kaldırılır. ${displaystyle G}$biz kaldık ${displaystyle G}$-ücretsiz grafik. Kalan beklenen kenar sayısı şu şekilde bulunabilir: ${displaystyle operatorname {ex} (n, G) geq cn ^ {2- {frac {v (G) -2} {e (G) -1}}}}$ bazı sabitler için ${displaystyle c}$. Bu nedenle, en az bir ${displaystyle n}$-vertex grafiği, en az beklenen sayı kadar çok kenara sahiptir.

Belirli durumlar için, cebirsel yapılar bularak iyileştirmeler yapılmıştır.

Teorem (Erdős, Renyi ve Sős, 1966). ${displaystyle operatorname {ex} (n, K_ {2,2}) geq left ({frac {1} {2}} - o (1) ight) n ^ {3/2}.}$^[10]

Kanıt.^[11] Önce varsayalım ki ${displaystyle n = p ^ {2} -1}$ biraz asal için ${displaystyle p}$. Yi hesaba kat polarite grafiği ${displaystyle G}$ köşe elemanları ile ${displaystyle mathbb {F} _ {p} ^ {2} - {0,0}}$ ve köşeler arasındaki kenarlar ${displaystyle (x, y)}$ ve ${displaystyle (a, b)}$ ancak ve ancak ${displaystyle ax + by = 1}$ içinde ${displaystyle mathbb {F} _ {p}}$. Bu grafik ${displaystyle K_ {2,2}}$-ücretsiz çünkü iki doğrusal denklem sistemi ${displaystyle mathbb {F} _ {p}}$ birden fazla çözüme sahip olamaz. Bir tepe ${displaystyle (a, b)}$ (varsayalım ${displaystyle beq 0}$) bağlı ${displaystyle left (x, {frac {1-ax} {b}} ight)}$ herhangi ${displaystyle xin mathbb {F} _ {p}}$toplamda en az ${displaystyle p-1}$ kenarlar (durumda 1 çıkarılır ${displaystyle (a, b) = left (x, {frac {1-ax} {b}} ight)}$). Yani en azından var ${displaystyle {frac {1} {2}} (p ^ {2} -1) (p-1) = sol ({frac {1} {2}} - o (1) sağ) p ^ {3} = sol ({frac {1} {2}} - o (1) ight) n ^ {3/2}}$ İstenildiği gibi kenarlar. Genel olarak ${displaystyle n}$, alabiliriz ${displaystyle p = (1-o (1)) {sqrt {n}}}$ ile ${displaystyle pleq {sqrt {n + 1}}}$ (bu mümkün çünkü bir asal ${displaystyle p}$ aralıkta${displaystyle [k-k ^ {0.525}, k]}$ yeterince büyük için ${displaystyle k}$^[12]) ve bunu kullanarak bir polarite grafiği oluşturun ${displaystyle p}$, sonra ekliyor ${displaystyle n-p ^ {2} +1}$ asimptotik değeri etkilemeyen izole köşeler.

Teorem (Brown, 1966). ${displaystyle operatorname {ex} (n, K_ {3,3}) geq left ({frac {1} {2}} - o (1) ight) n ^ {5/3}.}$^[13]

Kanıt taslağı.^[14] Önceki teoremde olduğu gibi, alabiliriz ${displaystyle n = p ^ {3}}$ asal için ${displaystyle p}$ ve grafiğimizin köşelerinin, ${displaystyle mathbb {F} _ {p} ^ {3}}$. Bu sefer köşeler ${displaystyle (a, b, c)}$ ve ${displaystyle (x, y, z)}$ bağlanırsa ve ancak ${displaystyle (x-a) ^ {2} + (y-b) ^ {2} + (z-c) ^ {2} = u}$ içinde ${displaystyle mathbb {F} _ {p}}$, bazıları için özel olarak seçilmiş ${displaystyle u}$. O zaman bu ${displaystyle K_ {3,3}}$-ücretsizdir çünkü en fazla iki nokta üç kürenin kesişme noktasında bulunur. Sonra değerinden beri ${ekran stili (x-a) ^ {2} + (y-b) ^ {2} + (z-c) ^ {2}}$ neredeyse tek tip ${displaystyle mathbb {F} _ {p}}$her noktanın etrafında olmalı ${görüntü stili p ^ {2}}$ kenarları olduğundan toplam kenar sayısı ${displaystyle left ({frac {1} {2}} - o (1) ight) p ^ {2} cdot p ^ {3} = sol ({frac {1} {2}} - o (1) ight) n ^ {5/3}}$.

Ancak, alt sınırı sıkılaştırmak açık bir soru olmaya devam ediyor. ${displaystyle operatorname {ex} (n, K_ {t, t})}$ için ${displaystyle tgeq 4}$.

Teorem (Alon ve diğerleri, 1999) ${displaystyle tgeq (s-1)! + 1}$, ${displaystyle operatorname {ex} (n, K_ {s, t}) = Theta (n ^ {2- {frac {1} {s}}}).}$^[15]

Genellemeler

Sorun, bir dizi yasaklanmış alt grafik için genelleştirilebilir ${displaystyle S}$: bir içindeki maksimum kenar sayısını bulun ${displaystyle n}$-vertex grafiği herhangi bir grafiğe izomorfik bir alt grafiğe sahip olmayan ${displaystyle S}$.^[16]

Ayrıca orada hiper grafik yasak alt grafik problemlerinin çok daha zor versiyonları. Örneğin, Turán'ın problemi, bir satırdaki en fazla kenar sayısını istemek şeklinde genelleştirilebilir. ${displaystyle n}$-vertex 3-tek tip hipergraf, tetrahedra içermiyor. Turan yapısının analoğu, köşeleri neredeyse eşit alt kümelere ayırmak olacaktır. ${displaystyle V_ {1}, V_ {2}, V_ {3}}$ve köşeleri bağlayın ${displaystyle x, y, z}$ hepsi farklıysa 3 kenarlı ${displaystyle V_ {i}}$s veya ikisi içeride ise ${displaystyle V_ {i}}$ ve üçüncüsü ${displaystyle V_ {i + 1}}$ (nerede ${displaystyle V_ {4} = V_ {1}}$). Bu tetrahedron içermez ve kenar yoğunluğu ${displaystyle 5/9}$. Bununla birlikte, en iyi bilinen üst sınır, bayrak cebirleri tekniği kullanılarak 0.562'dir.^[17]

Ayrıca bakınız

• Biklik içermeyen grafik
• Erdős – Hajnal varsayımı
• Turán teoremi
• Turán numarası
• Alt grafik izomorfizmi sorunu
• Yasak grafik karakterizasyonu
• Erdős-Stone teoremi
• Zarankiewicz sorunu
• Aşırı grafik teorisi

Referanslar