ช่วงแคบ
ในเรขาคณิตเมตริกขอบเขตเมตริกหรือขอบเขตแน่นของปริภูมิเมตริกMคือปริภูมิเมตริกแบบหนึ่งต่อหนึ่งที่สามารถฝังM เข้าไปได้ ในแง่หนึ่ง มันประกอบด้วยจุดทั้งหมด "ระหว่าง" จุดต่างๆ ของ Mคล้ายกับส่วนนูนของเซตจุดในปริภูมิยุคลิดขอบเขตแน่นนี้บางครั้งก็เรียกว่าขอบเขตแบบหนึ่งต่อหนึ่งหรือส่วนนูนเกินของMนอกจากนี้ยังเรียกว่าส่วนนูนแบบหนึ่งต่อหนึ่งแต่ไม่ควรสับสนกับส่วนนูนแบบหนึ่งต่อหนึ่งของโมดูลในพีชคณิตซึ่งเป็นแนวคิดที่มีคำอธิบายคล้ายกันเมื่อเทียบกับหมวดหมู่ของR-โมดูลมากกว่าปริภูมิเมตริก
แนวคิดเรื่องช่วงแคบ (tight span) ได้รับการอธิบายครั้งแรกโดยIsbell (1964)และได้รับการศึกษาและนำไปประยุกต์ใช้โดยHolsztyńskiในช่วงทศวรรษ 1960 ต่อมาได้รับการค้นพบใหม่โดยอิสระโดยDress (1984)และChrobak & Larmore (1994)ดูChepoi (1997)สำหรับประวัติความเป็นมา แนวคิดเรื่องช่วงแคบนี้เป็นหนึ่งในโครงสร้างหลักของทฤษฎี T
คำนิยาม
ช่วงแคบของปริภูมิเมตริกสามารถนิยามได้ดังนี้ ให้ ( X , d ) เป็นปริภูมิเมตริก และให้T ( X ) เป็นเซตของฟังก์ชันสุดขั้วบนXโดยที่เรากล่าวว่าฟังก์ชันสุดขั้วบนXหมายถึงฟังก์ชันfจากXไปยังRซึ่ง
- สำหรับxและy ใดๆ ในX d ( x , y ) ≤ f ( x ) + f ( y )และ
- สำหรับแต่ละxในX , f(x) = sup{ d(x,y) - f(y):yในX }. [ 1 ] : 124
โดยเฉพาะอย่างยิ่ง (โดยกำหนดให้x = yในคุณสมบัติที่ 1 ข้างต้น) f ( x ) ≥ 0 สำหรับทุกxวิธีหนึ่งในการตีความข้อกำหนดแรกข้างต้นคือfกำหนดเซตของระยะทางที่เป็นไปได้จากจุดใหม่บางจุดไปยังจุดในXซึ่งต้องสอดคล้องกับอสมการสามเหลี่ยมร่วมกับระยะทางใน ( X , d ) ข้อกำหนดที่สองระบุว่าไม่มีระยะทางใด ๆ เหล่านี้ที่สามารถลดลงได้โดยไม่ละเมิดอสมการสามเหลี่ยม
ช่วงแคบของ(X,d)คือปริภูมิเมตริก(T(X),δ)โดยที่ คล้ายคลึงกับเมตริกที่เกิดจากนอร์มℓ ∞ (ถ้าdมีขอบเขต δ จะเป็นเมตริกของปริภูมิย่อยที่เกิดจากเมตริกที่เกิดจากนอร์มℓ ∞ถ้าdไม่มีขอบเขต ฟังก์ชันสุดขั้วทุกฟังก์ชันบนXจะไม่มีขอบเขต ดังนั้นอย่างไรก็ตาม จะเป็นความจริงที่ว่าสำหรับf,g ใดๆ ในT(X)ความแตกต่างเป็นของ(กล่าวคือ มีขอบเขตจำกัด)
นิยามที่เทียบเท่ากันของฟังก์ชันสุดขั้ว
สำหรับฟังก์ชันfจากXไปยังRที่ตรงตามเงื่อนไขข้อแรก เงื่อนไขข้อที่สองในรูปแบบต่อไปนี้ถือว่าเทียบเท่ากัน:
- สำหรับแต่ละxในX , f(x) = sup{ d(x,y) - f(y):yในX }
- fเป็นฟังก์ชันขั้นต่ำแบบจุดต่อจุดโดยสัมพันธ์กับข้อกำหนดแรกที่กล่าวถึงข้างต้น กล่าวคือ สำหรับฟังก์ชันg ใดๆ จากXไปยังRที่d(x,y) ≤ g(x) + g(y)สำหรับทุกx,yในXถ้าg≤fแบบจุดต่อจุด แล้วf=g [ 2 ] : 93 , ข้อเสนอ 4.6.2 [หมายเหตุ 1 ] [หมายเหตุ 2 ] [ 3 ] :บทพิสูจน์ 5.1
คุณสมบัติพื้นฐานและตัวอย่าง
- สำหรับทุกxในX ,
- สำหรับแต่ละxในX ,เป็นค่าสุดขั้ว (พิสูจน์: ใช้สมมาตรและอสมการสามเหลี่ยม ) [หมายเหตุ 3 ]
- ถ้าXเป็นเซตจำกัด สำหรับฟังก์ชันf ใดๆ จากXไปยังRที่ตรงตามเงื่อนไขข้อแรก เงื่อนไขข้อที่สองจะเทียบเท่ากับเงื่อนไขที่ว่า สำหรับแต่ละxในXจะมีyในXที่ทำให้f ( x ) + f ( y ) = d ( x , y ) (ถ้าถ้าเช่นนั้น ทั้งสองเงื่อนไขจะเป็นจริง ถ้าจากนั้นจึงบรรลุค่าสูงสุด และข้อกำหนดแรกก็บ่งบอกถึงความเท่าเทียมกัน)
- สมมติว่า|X|=2และเลือกค่าa และ b ที่แตกต่างกัน โดยที่X={a,b}จากนั้นคือส่วนนูนของ{{(a,1),(b,0)},{(a,0),(b,1)}} [เพิ่มรูปภาพ คำบรรยายภาพ: ถ้าX={0,1}แล้วคือส่วนนูนของ{(0,1),(1,0)} ] [ 4 ] : 124
- ฟังก์ชันสุดขั้วทุกฟังก์ชันfบนXคือKatetov : [ 5 ] [ 6 ] :ส่วนที่ 2 fตรงตามข้อกำหนดแรกและหรือกล่าวอีกนัยหนึ่งคือfตรงตามข้อกำหนดแรกและ(คือ 1- ลิปชิตซ์ ) หรือเทียบเท่ากับf ที่ตรง ตามเงื่อนไขข้อแรกและ[ 2 ] :การพิสูจน์ข้อเสนอ 4.6.1 [หมายเหตุ 4 ]
- T(X)⊆ C(X) (ฟังก์ชันลิปชิตซ์เป็นฟังก์ชันต่อเนื่อง)
- T(X)เป็นฟังก์ชันต่อเนื่องสม่ำเสมอ (เป็นผลมาจากฟังก์ชันสุดขั้วทุกฟังก์ชันบนXเป็นฟังก์ชัน 1-ลิปชิตซ์ ดู ตัวอย่างใน Equicontinuity#Examples )
- ไม่ใช่ทุกฟังก์ชัน Katetov บนXจะเป็นฟังก์ชันสุดขั้วเสมอไป ตัวอย่างเช่น ให้aและbแตกต่างกัน ให้X = {a,b}ให้d = ([x≠y]) เป็นเมตริกแบบไม่ต่อเนื่องบนXและให้f = {(a,1),(b,2)}แล้วfเป็นฟังก์ชัน Katetov แต่ไม่ใช่ฟังก์ชันสุดขั้ว (เป็นที่เข้าใจได้เกือบจะทันทีว่าfเป็นฟังก์ชัน Katetov แต่ fไม่ใช่ฟังก์ชันสุดขั้วเพราะมันไม่ตรงตามคุณสมบัติในข้อที่สามของส่วนนี้)
- ถ้าdมีขอบเขตจำกัด ดังนั้นทุกfในT(X)จะมีขอบเขตจำกัด ที่จริงแล้ว สำหรับทุกfในT(X )(บันทึก(สืบเนื่องมาจากคุณสมบัติที่เทียบเท่าข้อที่สามในหัวข้อข้างต้น)
- ถ้าdไม่มีขอบเขต ดังนั้นทุกฟังก์ชัน fในT(X)ก็จะไม่มีขอบเขตเช่นกัน (เป็นผลมาจากเงื่อนไขแรก)
- ปิดภายใต้ขีดจำกัดแบบจุดต่อจุด สำหรับการลู่เข้าแบบจุดต่อจุดใดๆ
- ถ้า(X,d)เป็นคอมแพ็กต์ แล้ว(T(X),δ)จะเป็นคอมแพ็กต์[ 7 ] [ 2 ] :ข้อเสนอ 4.6.3 (พิสูจน์: ทฤษฎีบทค่าสุดขั้วบ่งชี้ว่าdเป็นฟังก์ชันต่อเนื่อง)มีขอบเขตจำกัด ดังนั้น (ดูข้อก่อนหน้า)เป็นเซตย่อยที่มีขอบเขตของC(X)เราได้แสดงให้เห็นแล้ว ว่า T(X)เป็นฟังก์ชันต่อเนื่องสม่ำเสมอ ดังนั้นทฤษฎีบท Arzelà–Ascoliจึงบ่งชี้ว่าT(X)เป็นเซตกระชับสัมพัทธ์อย่างไรก็ตาม หัวข้อก่อนหน้านี้บ่งชี้ว่าT(X)เป็นเซตปิดภายใต้ปกติ เนื่องจากการลู่เข้าหมายถึงการลู่เข้าแบบจุดต่อจุด ดังนั้นT(X) จึง เป็นเมทริกซ์กระชับ)
- สำหรับฟังก์ชันg ใดๆ จากXไปยังRที่ตรงตามข้อกำหนดแรก จะมีfในT(X)ที่f≤gในแต่ละจุด[ 2 ] :บทพิสูจน์ 4.4
- สำหรับฟังก์ชันสุดขั้วใดๆfบนX[ 2 ] :ข้อเสนอ 4.6.1 [หมายเหตุ 5 ]
- สำหรับf,g ใดๆ ในT(X)ผลต่างเป็นของกล่าวคือ มีขอบเขตจำกัด (ใช้ข้อความข้างต้น)
- แผนที่คูราโทวสกี้[ 4 ] : 125เป็นสมมาตร (เมื่อX = ∅ ผลลัพธ์จะชัดเจน เมื่อ X ≠ ∅ อสมการสามเหลี่ยมผกผันจะบ่งบอกถึงผลลัพธ์)
- ให้fอยู่ในT(X)สำหรับa ใดๆ ในXถ้าf(a)=0แล้วf=e(a) [ 3 ] :เลมมา 5.1 (สำหรับทุกxในXเรา มีจากความน้อยที่สุด (ลักษณะเทียบเท่าลำดับที่สองในส่วนด้านบน) ของfและข้อเท็จจริงที่ว่าหากตรงตามเงื่อนไขข้อแรก ก็หมายความว่า)
- (X,d)เป็นแบบไฮเปอร์โบลิกก็ต่อเมื่อ(T(X),δ)เป็นแบบไฮเปอร์โบลิก[ 3 ] :ทฤษฎีบท 5.3
คุณสมบัติความนูนสูง
- (T(X),δ)และทั้งคู่เป็นไฮเปอร์คอนเว็กซ์ [ 2 ] :ข้อเสนอ 4.7.1
- สำหรับY ใดๆ ที่ไม่ใช่ไฮเปอร์คอนเว็กซ์[ 2 ] :ข้อเสนอ 4.7.2 (" (T(X),δ)เป็นไฮเปอร์คอนเว็กซ์ฮัลล์ของ(X,d) .")
- อนุญาตเป็นปริภูมิเมตริกนูนสูงที่มีและถ้าหากว่าทั้งหมดที่ฉันมีอยู่ถ้าไม่ใช่ไฮเปอร์คอนเว็กซ์แล้วและ(T(X),δ)เป็นไอโซเมตริก [ 2 ] :ข้อเสนอ 4.7.1 ("ไฮเปอร์คอนเว็กซ์ฮัลล์ทุกอันของ(X,d)เป็นไอโซเมตริกกับ(T(X),δ) ")
ตัวอย่าง
- สมมติว่า|X|=3เลือกค่าa, b, c ที่แตกต่างกัน โดยที่X={a,b,c}และให้i=d(a,b), j=d(a,c), k=d(b,c)จากนั้นที่ไหน[เพิ่มรูปภาพ คำบรรยายภาพ: ถ้าX={0,1,2}แล้วT(X)=conv{(,,),(,,)} u conv{(,,),(,,)} u conv{(,,),(,,)}จะมีรูปร่างเหมือนตัวอักษร Y] (ดู[ 4 ] : 124 )

- รูปแสดงเซตXของจุด 16 จุดในระนาบ เพื่อสร้างปริภูมิเมตริกจำกัดจากจุดเหล่านี้ เราใช้ระยะทางแมนฮัตตัน ( ระยะทาง ℓ 1 ) [ 8 ]บริเวณสีน้ำเงินที่แสดงในรูปคือส่วนนูนเชิงตั้งฉาก ซึ่ง เป็นเซตของจุดzที่แต่ละควอดแรนต์ปิดทั้งสี่ที่มีzเป็นจุดยอดมีจุดของX อยู่ จุด zดังกล่าวใดๆสอดคล้องกับจุดของสแปนแน่น: ฟังก์ชันf ( x ) ที่สอดคล้องกับจุดzคือf ( x ) = d ( z , x ) ฟังก์ชันในรูปแบบนี้เป็นไปตามคุณสมบัติ 1 ของสแปนแน่นสำหรับz ใดๆ ในระนาบเมตริกแมนฮัตตัน โดยอสมการสามเหลี่ยมสำหรับเมตริกแมนฮัตตัน เพื่อแสดงคุณสมบัติ 2 ของสแปนแน่น ให้พิจารณาจุดx บางจุด ในXเราต้องหาyในXที่f ( x )+ f ( y )= d ( x , y ) แต่ถ้าxอยู่ในหนึ่งในสี่ควอดแรนต์ที่มีzเป็นจุดยอดyสามารถเป็นจุดใดก็ได้ในควอดแรนต์ตรงข้าม ดังนั้นคุณสมบัติข้อ 2 จึงเป็นจริงเช่นกัน ในทางกลับกัน สามารถแสดงได้ว่าทุกจุดของสแปนต์แน่นจะสอดคล้องกับจุดในเปลือกนูนเชิงตั้งฉากของจุดเหล่านั้น อย่างไรก็ตาม สำหรับเซตของจุดที่มีเมตริกแมนฮัตตันในมิติที่สูงกว่า และสำหรับเซตของจุดระนาบที่มีเปลือกเชิงตั้งฉากที่ไม่เชื่อมต่อกัน สแปนต์แน่นจะแตกต่างจากเปลือกนูนเชิงตั้งฉาก
มิติของช่วงแคบเมื่อXมีค่าจำกัด
คำจำกัดความข้างต้นฝังช่วงแคบT ( X ) ของเซตn () ชี้ไปยังR Xซึ่งเป็นปริภูมิเวกเตอร์จริงที่มีมิติnในทางกลับกัน หากเราพิจารณามิติของT ( X ) เป็นคอมเพล็กซ์ทรงหลายเหลี่ยม Develin (2006)แสดงให้เห็นว่า ด้วยสมมติฐานตำแหน่งทั่วไปที่เหมาะสมบนเมตริก นิยามนี้จะนำไปสู่ปริภูมิที่มีมิติระหว่างn /3 และn /2
คำจำกัดความทางเลือก
นิยามทางเลือกที่อิงตามแนวคิดของปริภูมิเมตริกที่มุ่งไปยังปริภูมิย่อยของมันนั้นได้รับการอธิบายโดยHolsztyński (1968)ซึ่งพิสูจน์ว่าซองบรรจุแบบหนึ่งต่อหนึ่งของปริภูมิ Banach ในหมวดหมู่ของปริภูมิ Banach นั้น สอดคล้อง (หลังจากละทิ้งโครงสร้างเชิงเส้น) กับช่วงกระชับ ทฤษฎีบทนี้ช่วยให้สามารถลดปัญหาบางอย่างจากปริภูมิ Banach ใดๆ ไปสู่ปริภูมิ Banach ในรูปแบบ C(X) โดยที่ X เป็นปริภูมิกระชับ
Develin & Sturmfels (2004)พยายามเสนอคำจำกัดความทางเลือกของ tight span ของปริภูมิเมตริกจำกัด โดยใช้Tropical convex hullของเวกเตอร์ระยะทางจากแต่ละจุดไปยังจุดอื่นๆ ในปริภูมิ อย่างไรก็ตาม ในปีเดียวกันนั้น พวกเขายอมรับในErratum Develin & Sturmfels (2004a)ว่า แม้ว่า Tropical convex hull จะครอบคลุม tight span เสมอ แต่ก็อาจไม่ตรงกับ tight span เสมอไป
แอปพลิเคชัน
- Dress, Huber และ Moulton (2001)อธิบายถึงการประยุกต์ใช้ช่วงแคบในการสร้างแผนภูมิวิวัฒนาการขึ้นใหม่จากข้อมูลทางชีววิทยา
- ช่วงแคบทำหน้าที่ในอัลกอริธึมออนไลน์หลายตัวสำหรับปัญหา K -server [ 9 ]
- Sturmfels & Yu (2004)ใช้ช่วงแคบเพื่อจำแนกพื้นที่เมตริกตามจุดได้มากถึงหกจุด
- Chepoi (1997)ใช้ช่วงแคบเพื่อพิสูจน์ผลลัพธ์เกี่ยวกับการบรรจุเมตริกตัดลงในปริภูมิเมตริกจำกัดทั่วไปมากขึ้น
ดูเพิ่มเติม
- การฝังแบบคุราตอฟสกี (Kuratowski embedding ) คือการฝังปริภูมิเมตริกใดๆ ลงในปริภูมิบานาค (Banach space)ซึ่งนิยามในลักษณะเดียวกับแผนที่คุราตอฟสกี (Kuratowski map)
- ปริภูมิเมตริกแบบฉีด
หมายเหตุ
- ↑ชุดเดรส, ฮูเบอร์และมอลตัน (2001 )
- 1 2 3 4 5 6 7 8 Khamsi, Mohamed A. ; Kirk, William A. (2001). บทนำสู่ปริภูมิเมตริกและทฤษฎีจุดตรึง . Wiley.
- 1 2 3 Dress, Andreas ; Huber, Katharina T. ; Koolen, Jacobus; Moulton, Vincent; Spillner, Andreas (2012). Basic Phylogenetic Combinatorics . Cambridge University Press. ISBN 978-0-521-76832-0.
- 1 2 3 Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine (2010). เครือข่ายวิวัฒนาการ: แนวคิด อัลกอริทึม และการประยุกต์ใช้สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ISBN 978-0-521-75596-2.
- ↑ Deza, Michel Marie ; Deza, Elena (2014). สารานุกรมระยะทาง ( ฉบับที่สาม). Springer. หน้า47. ISBN 978-3-662-44341-5.
- ↑ Melleray, Julien (2008). "คุณสมบัติทางเรขาคณิตและพลวัตบางประการของปริภูมิ Urysohn" . Topology and Its Applications . 155 (14): 1531– 1560. doi : 10.1016/j.topol.2007.04.029 .
- ↑ Benyamini, Yoav ; Lindenstrauss, Joram (2000). การวิเคราะห์เชิงฟังก์ชันแบบไม่เชิงเส้นทางเรขาคณิตสมาคมคณิตศาสตร์อเมริกัน หน้า32. ISBN 978-0-8218-0835-1.
- ↑ในสองมิติ ระยะทางแมนฮัตตันจะสมมาตรหลังจากการหมุนและการปรับขนาดให้เป็นระยะทางℓ ∞ดังนั้นด้วยเมตริกนี้ ระนาบจึงเป็นฟังก์ชันหนึ่งต่อหนึ่ง แต่ความเท่าเทียมกันระหว่าง ℓ 1และ ℓ ∞ นี้ ไม่เป็นจริงในมิติที่สูงกว่า
- ↑โครบักแอนด์ลาร์มอร์ (1994 )
- ↑ Khamsi และ Kirk ใช้เงื่อนไขนี้ในคำจำกัดความของพวกเขา
- ↑บทพิสูจน์ของ Khamsi และ Kirk แสดงให้เห็นถึงผลลัพธ์ประการหนึ่งของความเท่าเทียมกันกับเงื่อนไขข้างต้น ส่วนผลลัพธ์อีกประการหนึ่งนั้นไม่ยากที่จะแสดงให้เห็น
- ↑เช่น แผนที่คุราตอฟสกีเราจะนำเสนอแผนที่คุราตอฟสกีด้านล่างนี้
- ↑ค่าสูงสุดจะเกิดขึ้นเมื่อ y= x
- ↑ค่าสูงสุดจะเกิดขึ้นเมื่อ y= x
External links
- Joswig, Michael, Tight spans.