Harborths varsayımı - Harborths conjecture

Soru, Web Fundamentals.svgMatematikte çözülmemiş problem:
Her düzlemsel grafiğin entegre bir Fáry yerleştirmesi var mı?
(matematikte daha fazla çözülmemiş problem)

İçinde matematik, Harborth varsayımı şunu belirtir her düzlemsel grafik düzlemsel çizim her kenarın düz olduğu segment nın-nin tamsayı uzunluk.[1][2][3] Bu varsayımın adı Heiko Harborth ve (eğer doğruysa) güçlendirirdi Fáry teoremi her düzlemsel grafik için düz çizgi çizimlerinin varlığı üzerine. Bu nedenle, tamsayı kenar uzunluklarına sahip bir çizim aynı zamanda integral Fáry gömme.[4] Sonraki araştırmalara rağmen, Harborth'un varsayımı çözülemedi.[5]

İntegral Fáry gömme sekiz yüzlü grafik K2,2,2

Özel grafik sınıfları

Harborth'un varsayımının tüm düzlemsel grafikler için doğru olduğu bilinmemekle birlikte, birkaç özel düzlemsel grafik türü için kanıtlanmıştır.

Entegre Fáry düğünlerine sahip bir grafik sınıfı, indirgenebilen grafiklerdir. boş grafik iki tür işlem dizisi ile:

  • En fazla iki derecelik bir tepe noktasını kaldırmak.
  • Üçüncü dereceden bir tepe noktasını iki komşusu arasındaki bir kenarla değiştirmek. (Böyle bir kenar zaten mevcutsa, üçüncü derece tepe, komşuları arasına başka bir kenar eklemeden kaldırılabilir.)

Böyle bir grafik için, rasyonel bir Fáry gömme işlemi, verilen iki noktadan rasyonel bir mesafede bulunan noktalar kümesinin düzlemde yoğun olduğu ve üç noktanın rasyonel olması durumunda bu çıkarma işlemini tersine çevirerek aşamalı olarak inşa edilebilir. bir çift arasındaki mesafe ve diğer iki çift arasındaki rasyonel mesafenin karekökü, bu durumda üçünden de rasyonel uzaklıklardaki noktalar düzlemde yine yoğun olur.[6][7] Böyle bir katıştırmadaki mesafeler, yerleştirmeyi uygun bir faktörle ölçeklendirerek tamsayılar haline getirilebilir. Bu yapıya dayanarak, entegre Fáry düğünlerine sahip olduğu bilinen grafikler şunları içerir: iki parçalı düzlemsel grafikler, (2, 1) - seyrek düzlemsel grafikler, düzlemsel grafikler ağaç genişliği en fazla 3 ve en fazla dört derece grafikleri elmas altyazı ya da değil 4 kenara bağlı.[4][8][9]

Özellikle, yalnızca en fazla iki derece olan köşelerin kaldırılmasıyla boş grafiğe indirgenebilen grafikler ( 2-dejenere düzlemsel grafikler) hem dış düzlemsel grafikler ve seri paralel grafikler. Bununla birlikte, dış düzlemsel grafikler için, sonsuz alt kümelerin varlığına bağlı olarak, integral Fáry yerleştirmelerinin daha doğrudan bir inşası mümkündür. birim çember tüm mesafelerin rasyonel olduğu.[10]

Ek olarak, bütünleşik Fáry düğünleri, beş Platonik katılar.[3]

İlgili varsayımlar

Harborth varsayımının daha güçlü bir versiyonu, Kleber (2008), her düzlemsel grafiğin köşe koordinatlarının yanı sıra kenar uzunluklarının tümünün tam sayı olduğu bir düzlemsel çizime sahip olup olmadığını sorar.[11] Doğru olduğu biliniyor 3 düzenli grafikler,[12] maksimum derece 4 olan ancak 4 düzenli olmayan grafikler için,[13] ve için düzlemsel 3-ağaçlar.[13]

Geometride çözülmemiş başka bir problem olan Erdős – Ulam sorunu, varlığıyla ilgilidir yoğun alt kümeler tüm mesafelerin olduğu uçağın rasyonel sayılar. Böyle bir alt küme olsaydı, bir evrensel nokta kümesi rasyonel kenar uzunluklarına sahip tüm düzlemsel grafikleri çizmek için kullanılabilir (ve bu nedenle, bunları uygun şekilde ölçeklendirdikten sonra, tamsayı kenar uzunluklarıyla). Ancak Ulam, yoğun rasyonel mesafe kümelerinin var olmadığını varsaydı.[14]Göre Erdős-Anning teoremi, tüm mesafeleri tam sayı olan sonsuz doğrusal olmayan nokta kümeleri var olamaz. Bu, tüm mesafeleri rasyonel olan kümelerin varlığını dışlamaz, ancak bu türden herhangi bir sette rasyonel mesafelerin paydalarının keyfi bir şekilde büyümesi gerektiği anlamına gelir.

Ayrıca bakınız

Referanslar

  1. ^ Hartsfield, Nora; Ringel, Gerhard (2013), Grafik Teorisinde İnciler: Kapsamlı Bir Giriş Dover Matematik Kitapları, Courier Dover Yayınları, s. 247, ISBN  9780486315522, BAY  2047103. 1994 Academic Press baskısının yeniden basımı; Orijinal 1990 baskısında varsayıma aynı ad verilmiştir.
  2. ^ Kemnitz, Arnfried; Harborth, Heiko (2001), "Düzlemsel grafiklerin düzlem integral çizimleri", Ayrık Matematik Grafik teorisi (Kazimierz Dolny, 1997), 236 (1–3): 191–195, doi:10.1016 / S0012-365X (00) 00442-8, BAY  1830610. Kemnitz ve Harborth, bu varsayımın orijinal yayınına atıfta bulunur: Harborth vd. (1987).
  3. ^ a b Harborth, Heiko; Kemnitz, Arnfried; Möller, Meinhard; Süssenbach, Andreas (1987), "Ganzzahlige planare Darstellungen der platonischen Körper", Elemente der Mathematik, 42 (5): 118–122, BAY  0905393.
  4. ^ a b Sun, Timothy (2013), "Tamsayı kenar uzunluklarına sahip bazı 4 düzenli düzlemsel grafikler çizme", Proc. Kanada Hesaplamalı Geometri Konferansı (CCCG 2013) (PDF).
  5. ^ Pirinç, Peter; Moser, William O. J .; Pach, János (2005), Ayrık Geometride Araştırma Problemleri, Springer, s. 250, ISBN  9780387299297, BAY  2163782.
  6. ^ Almering, J. H. J. (1963), "Rasyonel dörtgenler", Indagationes Mathematicae, 25: 192–199, doi:10.1016 / S1385-7258 (63) 50020-1, BAY  0147447.
  7. ^ Berry, T. G. (1992), "Bir üçgenin köşelerinden rasyonel uzaklıkta bulunan noktalar", Açta Arithmetica, 62 (4): 391–398, doi:10.4064 / aa-62-4-391-398, BAY  1199630.
  8. ^ Biedl, Therese (2011), "Tam sayı kenar uzunluklarına sahip bazı düzlemsel grafikler çizme", Proc. Kanada Hesaplamalı Geometri Konferansı (CCCG 2011) (PDF).
  9. ^ Sun, Timothy (2011), "İntegral Fary Gömmelerinin Sertlik-Teorik Konstrüksiyonları", Proc. Kanada Hesaplamalı Geometri Konferansı (CCCG 2011) (PDF).
  10. ^ Klee, Victor; Vagon, Stan (1991), "Problem 10: Düzlem yoğun bir rasyonel küme içeriyor mu?", Düzlem Geometrisinde ve Sayı Teorisinde Eski ve Yeni Çözülmemiş Problemler Dolciani matematiksel açıklamaları, 11, Cambridge University Press, s. 132–135, ISBN  978-0-88385-315-3, BAY  1133201.
  11. ^ Kleber, Michael (2008), "Uzak noktada karşılaşma", Matematiksel Zeka, 1: 50–53, doi:10.1007 / BF02985756.
  12. ^ Geelen, Jim; Guo, Anjie; McKinnon, David (2008), "Tamsayı kenar uzunluklarına sahip kübik düzlemsel grafiklerin düz çizgi yerleştirmeleri", Journal of Graph Theory, 58 (3): 270–274, doi:10.1002 / jgt.20304, BAY  2419522.
  13. ^ a b Benediktovich, Vladimir I. (2013), "Geometrik bir grafiğin rasyonel yaklaşımı üzerine", Ayrık Matematik, 313 (20): 2061–2064, doi:10.1016 / j.disc.2013.06.018, BAY  3084247.
  14. ^ Solymosi, Jozsef; de Zeeuw, Frank (2010), "Erdős ve Ulam Sorusu Üzerine", Ayrık ve Hesaplamalı Geometri, 43 (2): 393–401, arXiv:0806.3095, doi:10.1007 / s00454-009-9179-x, BAY  2579704.