Ekstremal Çizge Kuramı
Ekstremal çizge kuramı, belirli bir alt yapıyı içermeyen bir çizgenin ne kadar büyük veya yoğun olabileceğini inceler ve ekstremal konfigürasyonları belirler.
Tanım
Sabit bir alt çizgenin yokluğu gibi yapısal bir kısıtlamaya tabi olarak, kenar sayısı gibi bir çizge parametresinin maksimum veya minimum değerinin incelenmesidir.
Kapsam
Bu konu, Mantel ve Turan teoremleriyle başlayıp, yasaklanmış herhangi bir alt çizge için asimptotik ekstremal yoğunluğu belirleyen Erdos-Stone teoremine kadar uzanan, belirli bir alt çizge içermeyen bir çizgedeki maksimum kenar sayısını konu alan Turan tipi problemlere odaklanmaktadır. Yoğunluk, yapı ve Szemeredi düzenlilik yönteminin karşılıklı etkileşimini tanıtmaktadır.
Temel sorular
- Belirli bir alt çizgenin kopyasını içermeyen n köşeli bir çizgedeki maksimum kenar sayısı nedir?
- Bu ekstremal sınırları hangi çizgeler sağlar?
- Yasaklanmış bir alt çizgenin kromatik sayısı, asimptotik cevabı nasıl belirler?
- Düzenlilik yöntemleri, yoğun çizgeleri sınırlı bir yapıya nasıl indirger?
Anahtar kavramlar
- Yasaklanmış alt çizgeler
- Turan çizgesi
- Mantel teoremi
- Ekstremal sayı (Turan sayısı)
- Erdos-Stone teoremi
- Szemeredi düzenlilik leması
Temel kuramlar
- Turan teoremi
- r+1 köşeli tam alt çizge içermeyen n köşeli tüm çizgeler arasında, dengeli tam r-parçalı çizge en fazla kenara sahiptir; bu, Mantel'in üçgen içermeyen sınırını genelleştirir ve ekstremal çizge kuramının temelini oluşturur.
- Erdos-Stone teoremi
- Sabit herhangi bir yasaklanmış H alt çizgesi için, H içermeyen bir çizgenin maksimum kenar yoğunluğu, H'nin kromatik sayısı tarafından asimptotik olarak belirlenir ve Turan tipi ekstremal sonuçları birleştirir.
Klinik önem
Ekstremal yoğunluk sonuçları, büyük ağların ve kısıt sistemlerinin yapısını sınırlar; bu alanda geliştirilen düzenlilik yöntemi ise özellik testi, teorik bilgisayar bilimi ve toplamsal kombinatorik alanlarında uygulamalara sahiptir.
Tarihçe
Mantel'in 1907 üçgen içermeyen sınırı ve Turan'ın 1941 genellemesi bu alanı başlatmıştır; Erdos-Stone-Simonovits kuramı ve Szemeredi'nin düzenlilik leması, onu modern kombinatoriğin merkezi bir direği haline getirmiştir.
Öne çıkan isimler
- Paul Turan
- Paul Erdos
- Endre Szemeredi
İlgili konular
Temel eserler
- bollobas1998
- diestel2017
Sıkça sorulan sorular
- Turan tipi problem nedir?
- Sabit bir alt çizgeden kaçınırken bir çizgenin sahip olabileceği en fazla kenar sayısını sorar; kanonik örnek, üçgen içermeyen bir çizgedeki maksimum kenar sayısıdır.
- Ekstremal çizge kuramı, Ramsey kuramı ile nasıl ilişkilidir?
- Her ikisi de kaçınılmaz yapıyı inceler, ancak ekstremal kuram yasaklanmış bir alt çizgeyi sabitler ve kenarları maksimize ederken, Ramsey kuramı çizge yeterince büyük olduğunda monokromatik bir yapıyı garanti eder.