อ่าน 3 นาที
โครงตาข่ายเรขาคณิต
ในคณิตศาสตร์ของแมทรอยด์และแลตทิซ แลตทิซเชิงเรขาคณิตคือแลตทิซกึ่งโมดูลา ร์อะตอมิก แบบจำกัด และแลตทิซแมทรอยด์คือแลตทิซกึ่งโมดูลาร์อะตอมิกโดยไม่ต้องสมมติว่าเป็นแบบจำกัด
โครงตาข่ายเรขาคณิต
ในคณิตศาสตร์ของแมทรอยด์และแลตทิซ แลตทิซเชิงเรขาคณิตคือแลตทิซกึ่งโมดูลา ร์อะตอมิก แบบจำกัด และแลตทิซแมทรอยด์คือแลตทิซกึ่งโมดูลาร์อะตอมิกโดยไม่ต้องสมมติว่าเป็นแบบจำกัด แลตทิซเชิงเรขาคณิตและแลตทิซแมทรอยด์นั้นเกิดจากแลตทิซของระนาบของแมทรอยด์แบบจำกัด หรือแบบจำกัดและอนันต์ ตามลำดับ และแลตทิซเชิงเรขาคณิตหรือแลตทิซแมทรอยด์ทุกอันล้วนมาจากแมทรอยด์ในลักษณะนี้
คำนิยาม
แลตทิซคือเซตลำดับบางส่วนที่สมาชิกสองตัวใดๆและต่างก็มีขอบเขตบนที่น้อยที่สุด เรียกว่าจุดร่วมหรือค่าสูงสุดซึ่งเขียนแทนด้วยและขอบเขตล่างที่มากที่สุด เรียกว่าจุดร่วมหรือค่าต่ำสุดซึ่งเขียนแทนด้วย
คำจำกัดความต่อไปนี้ใช้กับโพเซตโดยทั่วไป ไม่ใช่เฉพาะแลตทิซ เว้นแต่จะระบุไว้เป็นอย่างอื่น
- สำหรับองค์ประกอบขั้นต่ำ จะไม่มีองค์ประกอบใดที่ทำให้
- องค์ประกอบหนึ่งจะครอบคลุมองค์ประกอบอื่น(เขียนเป็นหรือ) ก็ต่อเมื่อและไม่มีองค์ประกอบใดที่แตกต่างจากทั้งและที่ทำให้
- อนุภาค ที่ประกอบด้วยธาตุพื้นฐานที่สุดเรียกว่าอะตอม
- โครงสร้างแลตติสจะเรียกว่าเป็นโครงสร้างอะตอมิกก็ต่อเมื่อธาตุทุกตัวเป็นค่าสูงสุดของชุดอะตอมบางชุด
- เซตลำดับ บางส่วน (poset) จะถูกจัดระดับได้ก็ต่อเมื่อสามารถกำหนดฟังก์ชันลำดับที่แมปองค์ประกอบของเซตนั้นไปยังจำนวนเต็มได้ โดยที่เมื่อใดก็ตามที่และเมื่อใดก็ตามที่
- เมื่อโพเซตแบบมีลำดับชั้นมีธาตุล่างสุด เราอาจสมมติได้โดยไม่เสียความเป็นทั่วไปว่าลำดับชั้นของธาตุล่างสุดนั้นคือศูนย์ ในกรณีนี้ อะตอมจะเป็นธาตุที่มีลำดับชั้นหนึ่ง
- แลตทิซแบบไล่ระดับเรียกว่าเซมิโมดูลาร์ถ้าสำหรับทุกและฟังก์ชันอันดับของมันเป็นไปตามเอกลักษณ์[ 1 ]
ผู้เขียนหลายคนพิจารณาเฉพาะแลตติสเมทริกซ์จำกัด และใช้คำว่า "แลตติสเรขาคณิต" และ "แลตติสเมทริกซ์" สลับกันได้สำหรับทั้งสองกรณี[ 5 ]
แลตติสเทียบกับแมทรอยด์
แลตติซทางเรขาคณิตเทียบเท่ากับแมทรอยด์แบบง่าย (จำกัด) และแลตติซแมทรอยด์เทียบเท่ากับแมทรอยด์แบบง่ายโดยไม่ต้องสมมติว่ามีจำนวนจำกัด (ภายใต้นิยามที่เหมาะสมของแมทรอยด์อนันต์ ซึ่งมีนิยามดังกล่าวอยู่หลายแบบ) ความสัมพันธ์คือ องค์ประกอบของแมทรอยด์เป็นอะตอมของแลตติซ และองค์ประกอบxของแลตติซสอดคล้องกับระนาบของแมทรอยด์ที่ประกอบด้วยองค์ประกอบของแมทรอยด์ที่เป็นอะตอมเหล่านั้น
เช่นเดียวกับโครงข่ายเรขาคณิต แมทรอยด์ก็มีฟังก์ชันอันดับแต่ฟังก์ชันนั้นจะแปลงเซตของสมาชิกแมทรอยด์ไปเป็นตัวเลข แทนที่จะใช้สมาชิกโครงข่ายเป็นอาร์กิวเมนต์ ฟังก์ชันอันดับของแมทรอยด์ต้องเป็นฟังก์ชันเอกภาค (การเพิ่มสมาชิกในเซตจะไม่ทำให้อันดับของเซตลดลง) และต้องเป็นฟังก์ชันย่อยโมดูลาร์ซึ่งหมายความว่ามันต้องเป็นไปตามอสมการที่คล้ายกับอสมการสำหรับโครงข่ายอันดับกึ่งโมดูลาร์:
สำหรับเซตXและYขององค์ประกอบ matroid เซต สูงสุดของอันดับที่กำหนดเรียกว่าflatการตัดกันของ flat สองอันก็คือ flat อีกครั้ง ซึ่งกำหนดการดำเนินการขอบล่างที่มากที่สุดบนคู่ของ flat นอกจากนี้ยังสามารถกำหนดขอบบนที่น้อยที่สุดของคู่ของ flat ให้เป็น superset สูงสุด (ที่ไม่ซ้ำกัน) ของผลรวมของ flat เหล่านั้นที่มีอันดับเดียวกับผลรวมของ flat เหล่านั้น ด้วยวิธีนี้ flat ของ matroid จะก่อตัวเป็น matroid lattice หรือ (ถ้า matroid เป็นเซตจำกัด) เป็น geometric lattice [ 4 ]
ในทางกลับกัน หากเป็นแลตทิซของแมทรอยด์ เราอาจกำหนดฟังก์ชันอันดับบนเซตของอะตอมได้ โดยกำหนดอันดับของเซตของอะตอมให้เป็นอันดับแลตทิซของขอบบนต่ำสุดของเซต ฟังก์ชันอันดับนี้จำเป็นต้องเป็นฟังก์ชันโมโนโทนิกและซับโมดูลาร์ ดังนั้นจึงกำหนดแมทรอยด์ได้ แมทรอยด์นี้จำเป็นต้องเป็นแมทรอยด์แบบง่าย หมายความว่าเซตที่มีสององค์ประกอบทุกเซตจะมีอันดับสอง[ 4 ]
โครงสร้างทั้งสองนี้ ได้แก่ แมทรอยด์แบบง่ายจากแลตทิซ และแลตทิซจากแมทรอยด์ เป็นสิ่งที่ผกผันกัน กล่าวคือ เมื่อเริ่มต้นจากแลตทิซทางเรขาคณิตหรือแมทรอยด์แบบง่าย และดำเนินการสร้างทั้งสองแบบทีละขั้นตอน จะได้แลตทิซหรือแมทรอยด์ที่เป็นไอโซมอร์ฟิกกับของเดิม[ 4 ]
ความเป็นสองด้าน
มีแนวคิดเรื่องความเป็นคู่ตามธรรมชาติที่แตกต่างกันสองแบบสำหรับแลตทิซทางเรขาคณิต: แมทรอยด์คู่ซึ่งมีเซตฐานเป็นส่วนเติมเต็มของฐานของแมทรอยด์ที่สอดคล้องกับและแลตทิซคู่ซึ่งเป็นแลตทิซที่มีองค์ประกอบเดียวกันกับในลำดับย้อนกลับ ทั้งสองอย่างนี้ไม่เหมือนกัน และโดยทั่วไปแล้วแลตทิซคู่ก็ไม่ใช่แลตทิซทางเรขาคณิตด้วยตัวมันเอง: คุณสมบัติของการเป็นเซมิโมดูลาร์ (บน) ไม่ได้รับการรักษาไว้โดยการกลับลำดับ ตัวอย่างง่ายๆ ของแลตทิซทางเรขาคณิตที่แลตทิซคู่ไม่ใช่เรขาคณิตคือแลตทิซของแฟลตของแมทรอยด์เอกรูปอันดับ 3 ที่มี 4 องค์ประกอบCheung (1974)กำหนดแอดจอยต์ของแลตทิซทางเรขาคณิต(หรือของแมทรอยด์ที่กำหนดจากมัน) ให้เป็นแลตทิซทางเรขาคณิตขั้นต่ำซึ่งแลตทิซคู่ของถูกฝังตามลำดับแมทรอยด์บางตัวไม่มีแอดจอยต์ ตัวอย่างเช่น แมทรอย ด์Vámos [ 6 ]
คุณสมบัติเพิ่มเติม
ช่วงแต่ละช่วงของแลตทิซทางเรขาคณิต (เซตย่อยของแลตทิซระหว่างองค์ประกอบขอบล่างและขอบบนที่กำหนด) นั้นเป็นเรขาคณิตในตัวเอง การเลือกช่วงของแลตทิซทางเรขาคณิตจะสอดคล้องกับการสร้างไมเนอร์ของแมทรอยด์ที่เกี่ยวข้อง แลตทิซทางเรขาคณิตเป็นส่วนเติมเต็มและเนื่องจากคุณสมบัติของช่วง จึงเป็นส่วนเติมเต็มเชิงสัมพัทธ์ด้วย[ 7 ]
แลตติซจำกัดทุกอันเป็นแลตติซย่อยของแลตติซเรขาคณิต[ 8 ]
ลิงก์ภายนอก
- "โครงข่ายเรขาคณิต" , PlanetMath
- ลำดับ OEIS A281574 (จำนวนโครงข่ายเรขาคณิตที่ไม่มีป้ายกำกับซึ่งมี องค์ประกอบ nตัว)
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ โครงตาข่ายเรขาคณิต
ในคณิตศาสตร์ของแมทรอยด์และแลตทิซ แลตทิซเชิงเรขาคณิตคือแลตทิซกึ่งโมดูลา ร์อะตอมิก แบบจำกัด และแลตทิซแมทรอยด์คือแลตทิซกึ่งโมดูลาร์อะตอมิกโดยไม่ต้องสมมติว่าเป็นแบบจำกัด
คำนิยาม
แล ตทิซ คือ เซตลำดับ บางส่วนที่สมาชิกสองตัวใดๆและต่างก็มีขอบเขตบนที่น้อยที่สุด เรียกว่า จุดร่วม หรือ ค่าสูงสุด ซึ่งเขียนแทนด้วยและขอบเขตล่างที่มากที่สุด เรียกว่า จุดร่วม หรือ ค่าต่ำสุด ซึ่งเขียนแทนด้วย x {\displaystyle x} y {\displaystyle y} x ∨ y...
แลตติสเทียบกับแมทรอยด์
แลตติซทางเรขาคณิตเทียบเท่ากับแมทรอยด์แบบง่าย (จำกัด) และแลตติซแมทรอยด์เทียบเท่ากับแมทรอยด์แบบง่ายโดยไม่ต้องสมมติว่ามีจำนวนจำกัด (ภายใต้นิยามที่เหมาะสมของแมทรอยด์อนันต์ ซึ่งมีนิยามดังกล่าวอยู่หลายแบบ) ความสัมพันธ์คือ องค์ประกอบของแมทรอยด์เป็นอะตอมของแลตติซ...
ความเป็นสองด้าน
มีแนวคิดเรื่องความเป็นคู่ตามธรรมชาติที่แตกต่างกันสองแบบสำหรับแลตทิซทางเรขาคณิต: แมทรอยด์คู่ ซึ่งมีเซตฐานเป็น ส่วนเติมเต็ม ของฐานของแมทรอยด์ที่สอดคล้องกับและ แลตทิซคู่ ซึ่งเป็นแลตทิซที่มีองค์ประกอบเดียวกันกับในลำดับย้อนกลับ ทั้งสองอย่างนี้ไม่เหมือนกัน...