ในทฤษฎีทางคณิตศาสตร์ของแมทรอยด์อันดับของแมทรอยด์คือขนาดสูงสุดของเซตอิสระในแมทรอยด์นั้น ในทำนองเดียวกัน อันดับของเซตย่อยS ของสมาชิกในแมทรอยด์ก็คือขนาดสูงสุดของเซตย่อยอิสระของSและฟังก์ชันอันดับของแมทรอยด์จะแมปเซตของสมาชิกไปยังอันดับของสมาชิกเหล่านั้น

ฟังก์ชันอันดับ (rank function) เป็นหนึ่งในแนวคิดพื้นฐานของทฤษฎีแมทรอยด์ (matroid theory) ซึ่งใช้ในการกำหนดสัจพจน์ของแมทรอยด์ฟังก์ชันอันดับ ของแมทรอยด์ เป็นกลุ่มย่อยที่สำคัญของฟังก์ชันเซตย่อยโมดูลาร์ (submodular set functions ) ฟังก์ชันอันดับของแมทรอยด์ที่นิยามจากวัตถุทางคณิตศาสตร์ ประเภทอื่น ๆ เช่นกราฟไร้ทิศทาง เมท ริกซ์และส่วนขยายฟิลด์มีความสำคัญในการศึกษาเกี่ยวกับวัตถุเหล่านั้น

ในทุกตัวอย่างEคือเซตฐานของแมทรอยด์ และBคือเซตย่อยบางส่วนของ E

• ให้Mเป็นเมทริกซ์อิสระโดยที่เซตอิสระทั้งหมดเป็นเซตย่อยของEแล้วฟังก์ชันอันดับของMก็คือ r ( B ) = | B |
• ให้Mเป็นเมทริกซ์เอกรูปโดยที่เซตอิสระคือเซตย่อยของEที่มีสมาชิกไม่เกินkตัว สำหรับจำนวนเต็มk บาง ตัว ฟังก์ชันอันดับของMคือ: r ( B ) = min( k , | B |)
• ให้Mเป็นเมทริกซ์แบ่งส่วน (partition matroid ) โดยที่องค์ประกอบของEถูกแบ่งออกเป็นหมวดหมู่ แต่ละหมวดหมู่cมีความจุk _cและเซตอิสระคือเซตที่มีองค์ประกอบในหมวดหมู่c ไม่เกิน k _cเซต ฟังก์ชันอันดับของMคือr ( B ) = ผลรวม_c min( k _c , | B _c |) โดยที่B _cคือเซตย่อยBที่อยู่ในหมวดหมู่c
• ให้Mเป็นเมทริกซ์กราฟิกโดยที่เซตอิสระคือเซตขอบที่ไม่มีวงจร ( ป่า ) ทั้งหมดของกราฟไม่มี ทิศทาง G ที่กำหนด ไว้ ฟังก์ชันอันดับr ( B ) คือจำนวนจุดยอดในกราฟ ลบด้วยจำนวนส่วนประกอบที่เชื่อมต่อกันของB (รวมถึงส่วนประกอบที่มีจุดยอดเดียว)

ฟังก์ชันอันดับของแมทริกซ์มีคุณสมบัติดังต่อไปนี้

(R1) ค่าของฟังก์ชันอันดับจะเป็นจำนวนเต็มที่ ไม่เป็นลบเสมอ และอันดับของเซตว่างคือ 0

(R2) สำหรับเซตย่อยสองเซตใดๆและของนั่นคือ อันดับ เป็นฟังก์ชันเซตย่อยโมดูลาร์ ${\displaystyle A}$${\displaystyle B}$${\displaystyle E}$${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$

(R3) สำหรับเซตและองค์ประกอบ ใดๆ , . ${\displaystyle A}$${\displaystyle x}$${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$

คุณสมบัติเหล่านี้สามารถใช้เป็นสัจพจน์เพื่อกำหนดลักษณะฟังก์ชันอันดับของแมทรอยด์ได้: ฟังก์ชันเซตย่อยโมดูลาร์ที่มีค่าเป็นจำนวนเต็มทุกตัวบนเซตย่อยของเซตจำกัดที่ปฏิบัติตามอสมการสำหรับทุก ๆและเป็นฟังก์ชันอันดับของแมทรอยด์^{[ 1 ] [ 2 ]}${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$${\displaystyle A}$${\displaystyle x}$

คุณสมบัติข้างต้นบ่งบอกถึงคุณสมบัติเพิ่มเติมดังต่อไปนี้:

• ถ้าแล้วนั่นคือ อันดับเป็นฟังก์ชันเอกภาค${\displaystyle A\subset B\subset E}$${\displaystyle r(A)\leq r(B)\leq r(E)}$
• ${\displaystyle r(A)\leq |A|}$.

ฟังก์ชันลำดับอาจใช้เพื่อกำหนดคุณสมบัติสำคัญอื่นๆ ของแมทริกซ์ได้:

• เซตจะเป็นอิสระก็ต่อเมื่ออันดับของมันเท่ากับจำนวนสมาชิก และจะขึ้นอยู่กันก็ต่อเมื่อจำนวนสมาชิกมากกว่าอันดับ^{[ 3 ]}
• เซตที่ไม่ว่างเปล่าเป็นวงจรก็ต่อเมื่อจำนวนสมาชิกของเซตเท่ากับหนึ่งบวกกับอันดับของเซต และเซตย่อยทุกเซตที่เกิดจากการลบสมาชิกหนึ่งตัวออกจากเซตจะมีอันดับเท่ากัน^{[ 3 ]}
• เซตจะเป็นฐานก็ต่อเมื่ออันดับของเซตเท่ากับจำนวนสมาชิกและอันดับของมาทรอยด์^{[ 3 ]}
• เซตจะเรียกว่าเซตปิด ถ้าเซตนั้นเป็นเซตสูงสุดสำหรับลำดับของมัน กล่าวคือ ไม่มีสมาชิกอื่นใดที่สามารถเพิ่มเข้าไปในเซตนั้นได้โดยที่ลำดับยังคงเดิม
• ความแตกต่างนี้เรียกว่าค่าว่างของเซตย่อยมันคือจำนวนองค์ประกอบขั้นต่ำที่ต้องถูกลบออกจากเซตย่อยเพื่อให้ได้เซตอิสระ^{[ 4 ]}${\displaystyle |A|-r(A)}$${\displaystyle A}$${\displaystyle A}$
• โคแรงค์ของเซตย่อยสามารถหมายถึงปริมาณที่แตกต่างกันอย่างน้อยสองอย่าง: ผู้เขียนบางคนใช้มันเพื่อหมายถึงแรงค์ของในเมทริกซ์คู่ , , ในขณะที่ผู้เขียนคนอื่นๆ ใช้โคแรงค์เพื่อหมายถึงความแตกต่าง${\displaystyle A}$${\displaystyle A}$${\displaystyle r^{*}(A)=|A|+r(E\setminus A)-r(E)}$${\displaystyle r(E)-r(A)}$

ในทฤษฎีกราฟจำนวนไซโคลมาติกของกราฟคือโคแรงค์ของกราฟิกแมทรอยด์ ที่เกี่ยวข้อง โดยจะวัดจำนวนขอบขั้นต่ำที่ต้องลบออกจากกราฟเพื่อให้ขอบที่เหลือก่อตัวเป็นป่า^{[ 5 ]}ผู้เขียนหลายคนได้ศึกษาความซับซ้อนของอัลกอริทึมกราฟที่กำหนดพารามิเตอร์ด้วยจำนวนนี้^{[ 6 ] [ 7 ]}

ในพีชคณิตเชิงเส้น อันดับของเมทริกซ์เชิงเส้นที่กำหนดโดยความเป็นอิสระเชิงเส้นจากคอลัมน์ของเมทริกซ์คืออันดับของเมทริกซ์^{[ 8 ]}และยังเป็นมิติของปริภูมิเวกเตอร์ที่เกิดจากคอลัมน์ อีกด้วย

ในพีชคณิตนามธรรมอันดับของเมทริกซ์ที่กำหนดจากเซตขององค์ประกอบในส่วนขยายฟิลด์L / Kโดยความเป็นอิสระเชิงพีชคณิตเรียกว่าระดับการเคลื่อนย้าย^{[ 9 ]}

ฟังก์ชันลำดับเมทริกซ์ (MRF) ถูกนำมาใช้เพื่อแสดงฟังก์ชันอรรถประโยชน์ของตัวแทนในปัญหาการจัดสรรสินค้าอย่างเป็นธรรมหากฟังก์ชันอรรถประโยชน์ของตัวแทนเป็น MRF นั่นหมายความว่า:

• ประโยชน์ของตัวแทนมีผลตอบแทนลดลง (ซึ่งเป็นผลมาจากข้อเท็จจริงที่ว่า MRF เป็นฟังก์ชันย่อยแบบโมดูลาร์)
• อรรถประโยชน์ส่วนเพิ่มของตัวแทนสำหรับแต่ละรายการเป็นแบบทวิภาค (ไบนารี) คือ 0 หรือ 1 กล่าวคือ การเพิ่มรายการลงในชุดจะไม่เพิ่มอรรถประโยชน์ หรือเพิ่มอรรถประโยชน์เท่ากับ 1

วิธีแก้ปัญหาที่ทราบกันดีสำหรับสถานการณ์นี้ ได้แก่:

• Babaioff, Ezra และ Feige ^{[ 10 ]} ออกแบบ กลไกความจริงแบบพหุนามเชิงกำหนดที่เรียกว่า Prioritized Egalitarian ซึ่งให้ผลลัพธ์เป็นการจัดสรรแบบครอบงำของ Lorenz ซึ่งส่งผลให้ EFX _{0 เช่นกัน เพิ่มผลคูณของอรรถประโยชน์ให้สูงสุด บรรลุ} ส่วนแบ่ง maximinเศษส่วน 1/2 และบรรลุส่วนแบ่ง maximin เต็มเมื่อการประเมินค่าสามารถบวกกันได้ ด้วยลำดับความสำคัญแบบสุ่ม กลไกนี้ยังปราศจากความอิจฉา แบบ ex-ante อีกด้วย พวกเขายังศึกษา การประเมินค่าแบบ e -dichotomous ซึ่งอรรถประโยชน์ส่วนเพิ่มจะไม่เป็นบวกหรืออยู่ในช่วง [1,1+ e ]
• Benabbou, Chakraborty, Igarashi และ Zick ^{[ 11 ]}แสดงให้เห็นว่า ในการตั้งค่านี้การจัดสรรที่เหมาะสมที่สุดแบบ Pareto จะเพิ่มผลรวมของอรรถประโยชน์สูงสุด ( สวัสดิการแบบอรรถประโยชน์นิยม ) เซตของการจัดสรรที่เพิ่มฟังก์ชันเว้า อย่างเคร่งครัดแบบสมมาตร f ให้ สูงสุดเหนือการจัดสรรผลรวมสูงสุดทั้งหมดจะไม่ขึ้นอยู่กับการเลือกfและ การจัดสรรที่เพิ่ม f ให้สูงสุดทั้งหมดเหล่านี้ เป็น EF1 ซึ่งหมายความว่าการจัดสรรผลคูณสูงสุดเป็นการ จัดสรร ที่เหมาะสมที่สุดแบบ leximinและทั้งหมดเป็นผลรวมสูงสุดและ EF1 พวกเขายังนำเสนออัลกอริทึมเวลาพหุนามที่คำนวณการจัดสรรผลรวมสูงสุดและ EF1 (ซึ่งไม่จำเป็นต้องเพิ่มฟังก์ชันเว้าให้สูงสุด) และอัลกอริทึมเวลาพหุนามที่เพิ่มฟังก์ชันเว้าให้สูงสุดสำหรับกรณีพิเศษของ MRF โดยอิงจากการจับคู่จำนวนสมาชิกสูงสุดในกราฟสองส่วน

ฟังก์ชันลำดับเมทริกซ์เป็นคลาสย่อยของการประเมินค่าทดแทนแบบรวม

• ออราเคิลระดับ