Düğüm ipliklerinin sayısı değişmez mi?
Soru: Bir düğümdeki bileşenlerin sayısı belirli düzlemsel yerleştirmeye mi bağlı?
Temel düzlemsel grafik yapısına dayalı olarak bir Kelt düğümündeki bileşen sayısını ("ayrı şeritler") nasıl hesaplayacağımı araştırıyorum. (Düğümler / bağlantılar ve düzlemsel grafikler arasındaki ilişkiye buradan bakın ).
Görünüşe göre genel grafikler için hesaplama biraz karmaşıktır; örneğin, bu sorudaki referans, bir üniforma için$m\times n$ kareler ızgarası, bileşenlerin sayısı $\mathrm{lcd}(m,n)$.
Bu özelliklerin hesaplanması zor olsa bile, bileşenlerin sayısını ("sarmallar") veya şerit sayısı ile derecesi, spektrumu gibi çeşitli grafik özellikleri arasında bir ilişki hesaplamak için bir formül bulmak beni tatmin ederdi. .
Aldığım bir yaklaşım, bağlantılı bileşenler açısından: her ayrı iplik belirli bir yörüngeyi takip ediyor ve bu yörüngelerin bağlantılı bileşenleri tam olarak iplikçiklere karşılık geliyor. Yörüngeyi, her bir kenarı ardılına bir geçiş fonksiyonu eşlemesi (bazı ek yapılar artı) olarak tanımlayabilirsiniz; bu, döngüleri bileşenler olan (yapılandırılmış) kenarlar üzerindeki bir permütasyondur.
Geçiş işlevi , bağlı bileşenleri düğüm sisteminin bileşenleri olan kendi, türetilmiş, yönlendirilmiş bir grafik ( grafik kodlu bir haritaya benzer) olarak kodlanabilir . Doğrusal cebirden, bağlı bileşenlerin sayısının, bitişik matrisin Laplacian'ının sıfır özdeğerinin çokluğu olarak elde edilebileceğini biliyoruz.
Ancak, aynı grafiğin $G$birden fazla izomorfik olmayan düzlemsel yerleştirmeye sahip olabilir (yani, dualleri izomorfik değildir). Şimdiye kadar deneyimlerime göre, bu bazı düğümleme özelliklerini (her bileşendeki bükülme sayısı gibi) değiştirdi, ancak bileşenlerin sayısını değiştirmedi:
Sorum şu:
Soru: Bir düğümdeki bileşenlerin sayısı belirli düzlemsel yerleştirmeye mi bağlı? Bunu nasıl kanıtlarız?
Benim sezgim, bileşenlerin sayısının değişmez olduğunu söylüyor, ancak yukarıdaki yaklaşımımı kullanarak bir karşı örnek veya kanıt üretemedim.
Varsayım: If $G$ bir grafikse karşılık gelen düğüm işi $c$ bileşenler, nerede
$$T_G(-1,-1) = (-1)^{|E(G)|}\cdot (-2)^{c - 1}$$
ve $T_G$ Tutte polinomudur ve $|E(G)|$grafikteki kenarların sayısıdır. (?)
Yanıtlar
İzin Vermek $D$bir bağlantının diyagramı olabilir. Örneğin,$D$Gönderinizde gösterilen Kelt düğümünün diyagramı veya bağlantısı olabilir. İzin Vermek$G$ dama tahtası grafiği olmak $D$. Grafik$G$ ilk madde işaretinizde açıklanan grafiktir.
Cevap: Bileşen sayısı$D$ soyut grafik ile belirlenir $G$ ve nasıl olduğuna bağlı değil $G$ düzlemin içine yerleştirilmiştir.
Bildiğim kadarıyla, bu ilk olarak 1979'da Michel Las Vergnas tarafından kanıtlandı. $D$ Tutte polinom değerlendirmesi ile belirlenir $T_G(-1,-1)$. Tutte polinomu, belirli bir$G$sonuç aşağıdaki gibidir. Bu kağıt için referans
- Michel, Las Vergnas. Eulerian grafik bölümlerinde . Çizge teorisi ve kombinatorikler (Proc. Conf., Open Univ., Milton Keynes, 1978), s. 62–75, Res. Matematik Notları, 34, Pitman, Boston, Mass.-London, 1979.
Yukarıdaki makalenin bir kopyasını kolayca bulamadım, bu yüzden Dan Silver ve Susan Williams (arXiv bağlantısı ) nedeniyle çözümü elde etmenin başka bir yolu var . Bir matris tanımlarlar$Q_2(G)$ girişleri iki öğeli alanda olan $\mathbb{F}_2$aşağıdaki gibi. Matrisin hem satırları hem de sütunları köşelere göre indekslenir$v_1,\dots,v_n$ nın-nin $G$. Eğer$i\neq j$, sonra $ij$ girişi $Q_2(G)$ köşeler arasındaki kenarların sayısıdır $v_i$ ve $v_j$ (alınmış$\mod 2$). $ii$ girişi $Q_2(G)$ satırdaki diğer girişlerin toplamıdır $i$ (tekrar alındı$\mod 2$). Eşdeğer olarak, diyebiliriz$ii$ giriş $Q_2(G)$ sütundaki diğer girişlerin toplamıdır $i$.
Bağlantılı makalenin Teorem 1.1'de, bileşenlerin sayısının $D$ sıfıra eşittir $Q_2(G)$. Açıklama 1.2'de bunun, bileşenlerin sayısını ifade ettiğini not ederler.$D$ düzlemin gömülmesinden bağımsızdır $G$.
Düzenleme: Las Vergnas makalesine erişimim yok, ancak Tutte polinomunu ve Jones polinomunu kullanarak sonucun başka bir açıklamasını verebilirim.
İzin Vermek $L$ alternatif bir bağlantı olalım $D$ bağlantının alternatif bir diyagramı olun ve $G$ dama tahtası grafiği olmak $D$. Sonra Tutte polinomu$T_G(x,y)$ nın-nin $G$ ve Jones polinomu $V_L(t)$ nın-nin $L$ aşağıdaki gibi ilişkilidir: $$V_L(t) = f_D(t) T_G(-t,-t^{-1})$$ işlev için $f_D(T)$ tarafından tanımlandı $$f_D(t) = (-1)^{w(D)}t^{\frac{1}{4}(|E| - 2(|V|-1)+3w(D))}$$ nerede $w(D)$ kıvranması $D$, $|E|$ kenarların sayısı $G$, ve $|V|$ köşe noktalarının sayısı $D$. Dikkat edin$|f_D(1)|=1$, ve böylece $|V_L(1)| = |T_G(-1,-1)|$.
Jones polinomu skein ilişkisini karşılar $$(t^{\frac{1}{2}}-t^{-\frac{1}{2}})V_{L_0}(t) = t^{-1}V_{L_+}(t) - tV_{L_-}(t)$$ nerede $L_+,L_-,$ ve $L_0$ aşağıdaki gibidir.
Ayar $t=1$ yukarıdaki skein ilişkisinde verimler $V_{L_+}(1)=V_{L_-}(1)$. Başka bir deyişle Jones polinomu,$t=1$ kesişen değişiklikler altında değişmez ve bu nedenle $V_L(1)=V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(1)$ nerede $\bigcirc\sqcup\dots\sqcup\bigcirc$ aynı sayıda bileşene sahip önemsiz bağlantıdır. $L$. Jones polinomu$\bigcirc\sqcup\dots\sqcup\bigcirc$ dır-dir $V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(t) = (-t^{\frac{1}{2}}-t^{-\frac{1}{2}})^{m-1}$ nerede $m$ bileşenlerinin sayısı $\bigcirc\sqcup\dots\sqcup\bigcirc$. Böylece$$|T_G(-1,-1)|=|V_L(1)|=|V_{\bigcirc\sqcup\dots\sqcup\bigcirc}(1)| = 2^{m-1}.$$
Yukarıdaki durum ne zaman ele alınır $L$değişiyor. Eğer$L$değişmiyorsa, aşağıdaki gibi devam edin. İzin Vermek$D$ herhangi bir diyagramı olmak $L$. Tanımlamak$D_{\text{alt}}$ ile aynı gölgeye sahip bir şema olmak $D$ ancak geçişleri dönüşümlü olarak değiştirilen ve $L_{\text{alt}}$ diyagramı olan bağlantı olmak $D_{\text{alt}}$. Bunu not et$D$ ve $D_{\text{alt}}$ aynı dama tahtası grafiğine sahip $G$. Yukarıdaki argüman şunu ima eder:$|T_G(-1,-1)|=2^{m-1}$ nerede $m$ bileşenlerinin sayısı $L_{\text{alt}}$. Dan beri$L_{\text{alt}}$ ve $L$ aynı sayıda bileşene sahipse, sonuç aşağıdaki gibidir $L$ yanı sıra.