ماترويد

من حيث الاستقلال، الماترويد المحدود${\displaystyle M}$هو زوج${\displaystyle (E,{\mathcal {I}})}$، أين${\displaystyle E}$هي مجموعة منتهية (تسمى المجموعة الأساسية ) و${\displaystyle {\mathcal {I}}}$هي عائلة من المجموعات الفرعية من${\displaystyle E}$(تسمى المجموعات المستقلة ) بالخصائص التالية: ^{[ 4 ]}

• (I1) المجموعة الفارغة مستقلة، أي${\displaystyle \emptyset \in {\mathcal {I}}}$.

• (I2) كل مجموعة جزئية من مجموعة مستقلة هي مجموعة مستقلة، أي لكل${\displaystyle A'\subseteq A}$، لو${\displaystyle A\in {\mathcal {I}}}$ثم${\displaystyle A'\in {\mathcal {I}}}$يُطلق على هذا أحيانًا اسم الملكية الوراثية ، أو الملكية المغلقة تنازليًا .

• (I3) إذا${\displaystyle A}$و${\displaystyle B}$هما مجموعتان مستقلتان (أي أن كل مجموعة مستقلة) و${\displaystyle A}$يحتوي على عناصر أكثر من${\displaystyle B}$إذن يوجد${\displaystyle x\in A\setminus B}$بحيث${\displaystyle B\cup \{x\}}$مستقلة. يُطلق على هذا أحيانًا اسم خاصية التوسيع أو خاصية تبادل المجموعات المستقلة (انظر مبرهنة تبادل ستينيتز ).

تُحدد الخاصيتان الأوليان بنيةً توافقيةً تُعرف بنظام الاستقلال (أو المُركب التبسيطي المُجرد ). في الواقع، بافتراض (I2)، فإن الخاصية (I1) تُكافئ حقيقة أن مجموعةً فرعيةً واحدةً على الأقل من${\displaystyle E}$مستقل، أي${\displaystyle {\mathcal {I}}\neq \emptyset }$.

مجموعة فرعية من المجموعة الأساسية${\displaystyle E}$ما ليس مستقلاً يسمى تابعاً .

مجموعة مستقلة قصوى - أي مجموعة مستقلة تصبح تابعة عند إضافة أي عنصر منها${\displaystyle E}$– يُطلق عليه اسم أساس الماترويد.

دائرة في ماترويد${\displaystyle M}$هي مجموعة فرعية تابعة دنيا من${\displaystyle E}$– أي مجموعة تابعة تكون جميع مجموعاتها الجزئية مستقلة. ينشأ هذا المصطلح لأن دوائر الماترويدات الرسومية هي دورات في الرسوم البيانية المقابلة. ^{[ 4 ]}

تُحدد المجموعات التابعة، أو القواعد، أو الدوائر في الماترويد خصائص الماترويد بشكل كامل: فالمجموعة مستقلة إذا وفقط إذا لم تكن تابعة، وإذا وفقط إذا كانت مجموعة جزئية من قاعدة، وإذا وفقط إذا لم تحتوي على دائرة. ولكل من مجموعات المجموعات التابعة، والقواعد، والدوائر خصائص بسيطة يمكن اعتبارها بديهيات للماترويد. على سبيل المثال، يمكن تعريف الماترويد${\displaystyle M}$أن يكونا زوجين${\displaystyle (E,{\mathcal {B}})}$، أين${\displaystyle E}$هي مجموعة منتهية كما كان من قبل و${\displaystyle {\mathcal {B}}}$هي مجموعة من المجموعات الفرعية من${\displaystyle E}$، تسمى القواعد ، ولها الخصائص التالية: ^{[ 4 ]}

• (ب1)${\displaystyle {\mathcal {B}}}$غير فارغ.

• (ب2) إذا${\displaystyle A}$و${\displaystyle B}$أعضاء متميزون في${\displaystyle {\mathcal {B}}}$و${\displaystyle a\in A\smallsetminus B}$إذن يوجد عنصر${\displaystyle b\in B\smallsetminus A}$بحيث${\displaystyle (A\smallsetminus \{a\})\cup \{b\}\in {\mathcal {B}}}$.

تُسمى هذه الخاصية (B2) خاصية تبادل الأساس . ويترتب على هذه الخاصية أنه لا يوجد عضو من${\displaystyle {\mathcal {B}}}$يمكن أن تكون مجموعة فرعية مناسبة لأي مجموعة أخرى.

من النتائج الأساسية لنظرية الماترويد، والتي تُشابه مباشرةً نظرية مماثلة للقواعد في الجبر الخطي ، أن أي قاعدتين للماترويد${\displaystyle M}$تحتوي على نفس عدد العناصر. يُطلق على هذا العدد اسم رتبة${\displaystyle M}$. لو${\displaystyle M}$هو ماترويد على${\displaystyle E}$، و${\displaystyle A}$هي مجموعة فرعية من${\displaystyle E}$ثم ماترويد على${\displaystyle A}$يمكن تعريفها من خلال النظر في مجموعة فرعية من${\displaystyle A}$أن تكون مستقلة إذا وفقط إذا كانت مستقلة في${\displaystyle M}$وهذا يسمح لنا بالحديث عن المصفوفات الفرعية وعن رتبة أي مجموعة فرعية من${\displaystyle E}$رتبة مجموعة جزئية${\displaystyle A}$يتم تحديدها بواسطة دالة الرتبة${\displaystyle r(A)}$من الماترويد، الذي له الخصائص التالية: ^{[ 4 ]}

• (R1) قيمة دالة الرتبة هي دائمًا عدد صحيح غير سالب .

• (R2) لأي مجموعة جزئية${\displaystyle A\subset E}$لدينا${\displaystyle r(A)\leq |A|}$.

• (R3) لأي مجموعتين جزئيتين${\displaystyle A,B\subset E}$لدينا:${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$أي أن الرتبة هي دالة شبه معيارية .

• (R4) لأي مجموعة${\displaystyle A}$وعنصر${\displaystyle x}$لدينا:${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$. من المتباينة الأولى، يتبين بشكل عام أنه إذا${\displaystyle A\subseteq B\subseteq E}$، ثم${\displaystyle r(A)\leq r(B)\leq r(E)}$أي أن الرتبة دالة رتيبة .

يمكن استخدام هذه الخصائص كأحد التعريفات البديلة للماترويد المحدود: إذا${\displaystyle (E,r)}$إذا استوفت هذه الخصائص، فإن المجموعات المستقلة للماترويد على${\displaystyle E}$يمكن تعريفها بأنها تلك المجموعات الفرعية${\displaystyle A}$ل${\displaystyle E}$مع${\displaystyle r(A)=|A|}$في لغة المجموعات المرتبة جزئيًا ، يكون هذا التركيب الماتروي مكافئًا للشبكة الهندسية التي تكون عناصرها هي المجموعات الجزئية${\displaystyle A\subset M}$مرتبة جزئياً حسب الاحتواء.

الفرق${\displaystyle |A|-r(A)}$يُطلق على ذلك اسم عدم وجود مجموعة جزئية${\displaystyle A}$هو الحد الأدنى لعدد العناصر التي يجب إزالتها من${\displaystyle A}$للحصول على مجموعة مستقلة. عدم وجود مصفوفة${\displaystyle E}$في${\displaystyle M}$يُطلق عليه اسم العدمية${\displaystyle M}$الفرق${\displaystyle r(E)-r(A)}$يُطلق عليه أحيانًا اسم الرتبة المشتركة للمجموعة الجزئية${\displaystyle A}$.

يترك${\displaystyle M}$ليكن ماترويد على مجموعة منتهية${\displaystyle E}$، مع دالة الترتيب${\displaystyle r}$كما سبق. الإغلاق أو الامتداد${\displaystyle \operatorname {cl} (A)}$من مجموعة جزئية${\displaystyle A}$ل${\displaystyle E}$هي المجموعة

${\displaystyle \operatorname {cl} (A)={\Bigl \{}\ x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\Bigr \}}}$.

يُعرّف هذا عامل الإغلاق${\displaystyle \operatorname {cl}$ :{\mathcal {P}}(E)\mapsto {\mathcal {P}}(E)} حيث${\displaystyle {\mathcal {P}}}$يشير إلى مجموعة القوى ، مع الخصائص التالية:

• (ج1) لجميع المجموعات الجزئية${\displaystyle X}$ل${\displaystyle E}$،${\displaystyle X\subseteq \operatorname {cl} (X).}$

• (ج2) لجميع المجموعات الجزئية${\displaystyle X}$ل${\displaystyle E}$،${\displaystyle \operatorname {cl} (X)=\operatorname {cl} \left(\operatorname {cl} \left(X\right)\right).}$

• (ج3) لجميع المجموعات الجزئية${\displaystyle X}$و${\displaystyle Y}$ل${\displaystyle E}$مع${\displaystyle X\subseteq Y}$،${\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y).}$

• (ج4) لجميع العناصر${\displaystyle a}$و${\displaystyle b}$من${\displaystyle E}$وجميع المجموعات الفرعية${\displaystyle Y}$ل${\displaystyle E}$، لو${\displaystyle a\in \operatorname {cl} (Y\cup \{b\})\smallsetminus \operatorname {cl} (Y)}$ثم${\displaystyle b\in \operatorname {cl} (Y\cup \{a\})\smallsetminus \operatorname {cl} (Y).}$

تُعدّ الخصائص الثلاث الأولى من هذه الخصائص هي الخصائص المُحدِّدة لمؤثر الإغلاق. أما الخاصية الرابعة فتُسمى أحيانًا خاصية تبادل ماك لين - ستاينيتز . ويمكن اعتبار هذه الخصائص تعريفًا آخر للماترويد: كل دالة${\displaystyle \operatorname {cl}$ :{\mathcal {P}}(E)\to {\mathcal {P}}(E)} الذي يحقق هذه الخصائص يحدد الماترويد. ^{[ 4 ]}

تُسمى المجموعة التي يكون إغلاقها مساويًا لنفسها مجموعةً مغلقة ، أو فضاءً مسطحًا أو جزئيًا من الماترويد. ^{[ 5 ]} تُسمى المجموعة مغلقة إذا كانت ذات رتبة قصوى ، أي أن إضافة أي عنصر آخر إليها يزيد من رتبتها. وتتميز المجموعات المغلقة للماترويد بخاصية التغطية التقسيمية.

• (F1) مجموعة النقاط الكاملة${\displaystyle E}$مغلق.

• (F2) إذا${\displaystyle S}$و${\displaystyle T}$إذا كانت شققًا، فإذن${\displaystyle S\cap T}$شقة.

• (F3) إذا${\displaystyle S}$إذا كان مسطحًا، فإن كل عنصر من عناصر${\displaystyle E\smallsetminus S}$يقع في إحدى الشقق تحديداً${\displaystyle T}$ذلك الغلاف${\displaystyle S}$(بمعنى أن${\displaystyle T}$يحتوي بشكل صحيح${\displaystyle S}$لكن لا توجد شقة${\displaystyle U}$بين${\displaystyle S}$و${\displaystyle T}$).

الفصل${\displaystyle {\mathcal {L}}(M)}$تشكل جميع الأسطح المستوية، المرتبة جزئيًا حسب احتواء المجموعة، شبكة ماترويد . وعلى العكس من ذلك، فإن كل شبكة ماترويد${\displaystyle L}$يشكل ماترويد فوق مجموعته${\displaystyle E}$من الذرات تحت عامل الإغلاق التالي: لمجموعة${\displaystyle S}$من الذرات مع الربط${\displaystyle \bigvee S}$،

${\displaystyle \operatorname {cl} (S)=\{x\in E\mid x\leq \bigvee S\}.}$

تتطابق المستويات المسطحة لهذا الماترويد تطابقًا تامًا مع عناصر الشبكة؛ المستوى المسطح المقابل لعنصر الشبكة${\displaystyle y}$هي المجموعة

${\displaystyle \{x\in E\mid x\leq y\}.}$

وبالتالي، فإن شبكة الأسطح المستوية لهذا الماترويد متماثلة بشكل طبيعي مع${\displaystyle L}$.

في مصفوفة من الرتبة${\displaystyle r}$شقة من الدرجة الأولى${\displaystyle r-1}$يُطلق عليه اسم المستوى الفائق ، أو الذرات المشتركة ، أو النقاط المشتركة . هذه هي المستويات المسطحة القصوى؛ أي أن المجموعة الشاملة الوحيدة للمستوى الفائق التي هي أيضًا مستوى مسطح هي المجموعة${\displaystyle E}$من بين جميع عناصر الماترويد. تعريف مكافئ هو أن الكواتوم عبارة عن مجموعة جزئية من E لا تولد M ، ولكن إضافة أي عنصر آخر إليها لا يؤدي إلى تكوين مجموعة مولدة. ^{[ 6 ]}

العائلة${\displaystyle {\mathcal {H}}}$تتمتع المستويات الفائقة للماترويد بالخصائص التالية، والتي يمكن اعتبارها بمثابة بديهية أخرى للماترويد: ^{[ 6 ]}

• (H1) مجموعة التأريض${\displaystyle E}$هو نفسه ليس مستوى فائق.

• (H2) لا توجد مجموعات متميزة${\displaystyle X}$و${\displaystyle Y}$في${\displaystyle {\mathcal {H}}}$مع${\displaystyle X\subseteq Y}$أي أن المستويات الفائقة تشكل عائلة سبيرنر .

• (H3) لكل${\displaystyle x\in E}$ومميز${\displaystyle Y,Z\in {\mathcal {H}}}$مع${\displaystyle x\notin Y\cup Z}$، يوجد${\displaystyle X\in {\mathcal {H}}}$مع${\displaystyle (Y\cap Z)\cup \{x\}\subseteq X}$.

عرّف مينتي (1966) الرسم البياني بأنه ثلاثي${\displaystyle (L,C,D)}$في أي${\displaystyle C}$و${\displaystyle D}$هي فئات من المجموعات الفرعية غير الفارغة من${\displaystyle L}$بحيث

• (G1) لا يوجد عنصر من${\displaystyle C}$(تسمى "دائرة") تحتوي على أخرى،

• (G2) لا يوجد عنصر من${\displaystyle D}$(يُطلق عليه اسم "دائرة مشتركة") يحتوي على دائرة أخرى،

• (G3) لا يوجد مجموعة في${\displaystyle C}$وحدد${\displaystyle D}$يتقاطعان في عنصر واحد فقط، و

• (G4) كلما${\displaystyle L}$يتم تمثيلها كاتحاد منفصل لمجموعات جزئية${\displaystyle R,G,B}$مع${\displaystyle G=\{g\}}$( مجموعة أحادية )، ثم إما${\displaystyle X\in C}$يوجد بحيث${\displaystyle g\in X\subseteq R\cup G}$أو${\displaystyle Y\in D}$يوجد بحيث${\displaystyle g\in Y\subseteq B\cup G}$.

لقد أثبت أن هناك ماترويدًا من أجله${\displaystyle C}$هي فئة من الدوائر و${\displaystyle D}$هي فئة الدوائر المشتركة. على العكس من ذلك، إذا${\displaystyle C}$و${\displaystyle D}$هما فئتا الدائرة والدائرة المساعدة في الماترويد${\displaystyle M}$مع مجموعة أرضية${\displaystyle E}$، ثم${\displaystyle (E,C,D)}$هو رسم بياني. وبالتالي، فإن الرسوم البيانية تعطي بديهية ذاتية التناظر ومتخفية الشكل للماترويدات.

يترك${\displaystyle E}$لتكن مجموعة منتهية. مجموعة جميع المجموعات الجزئية من${\displaystyle E}$يُعرّف هذا المصطلح المجموعات المستقلة للماترويد. ويُطلق عليه اسم الماترويد الحر .${\displaystyle E}$.

يترك${\displaystyle E}$أن تكون مجموعة منتهية و${\displaystyle k}$عدد طبيعي . يمكن تعريف الماترويد على${\displaystyle E}$من خلال أخذ كل${\displaystyle k}$مجموعة فرعية من عناصر${\displaystyle E}$أن تكون أساسًا. يُعرف هذا باسم المصفوفة الموحدة من الرتبة${\displaystyle k}$. ماترويد منتظم ذو رتبة${\displaystyle k}$ومع${\displaystyle n}$يُشار إلى العناصر بـ${\displaystyle U_{k,n}}$جميع المصفوفات المنتظمة ذات الرتبة 2 على الأقل هي مصفوفات بسيطة (انظر §  المصطلحات الإضافية ). المصفوفة المنتظمة ذات الرتبة  2 على${\displaystyle n}$تُسمى النقاط بـ${\displaystyle n}$ خط النقطة . يكون الماترويد منتظمًا إذا وفقط إذا لم يكن لديه دوائر بحجم أقل من واحد زائد رتبة الماترويد. تسمى المجاميع المباشرة للماترويدات المنتظمة ماترويدات التقسيم .

في الماترويد المنتظم${\displaystyle U_{0,n}}$كل عنصر عبارة عن حلقة (عنصر لا ينتمي إلى أي مجموعة مستقلة)، وفي الماترويد المنتظم${\displaystyle U_{n,n}}$كل عنصر هو حلقة مشتركة (عنصر ينتمي إلى جميع القواعد). المجموع المباشر للماترويدات من هذين النوعين هو ماترويد تجزئة يكون فيه كل عنصر حلقة أو حلقة مشتركة؛ ويُسمى ماترويد منفصل . تعريف مكافئ للماترويد المنفصل هو ماترويد تكون فيه كل مجموعة جزئية فعلية غير فارغة من المجموعة الأساسية${\displaystyle E}$هو فاصل.

تطورت نظرية الماترويد بشكل أساسي من خلال دراسة معمقة لخصائص الاستقلال والبعد في الفضاءات المتجهة. وهناك طريقتان لعرض الماترويدات المعرفة بهذه الطريقة:

لو${\displaystyle E}$هي أي مجموعة جزئية منتهية من فضاء متجهي${\displaystyle V}$ثم يمكننا تعريف الماترويد${\displaystyle M}$على${\displaystyle E}$عن طريق أخذ المجموعات المستقلة من${\displaystyle M}$أن تكون المجموعات الفرعية المستقلة خطيًا من${\displaystyle E}$.

تتحقق صحة بديهيات المجموعة المستقلة لهذا الماترويد من خلال مبرهنة تبادل ستينيتز .

لو${\displaystyle M}$إذا كان لدينا ماترويد يمكن تعريفه بهذه الطريقة، نقول المجموعة${\displaystyle E}$يمثل${\displaystyle M}$.

تُسمى الماترويدات من هذا النوع بالماترويدات المتجهة .

من الأمثلة المهمة على الماترويدات المُعرَّفة بهذه الطريقة ماترويد فانو، وهو  ماترويد من الرتبة الثالثة مُشتق من مستوى فانو ، وهو هندسة منتهية تتكون من سبع نقاط (عناصر الماترويد السبعة) وسبعة خطوط (المستويات غير التافهة الفعلية للماترويد). وهو ماترويد خطي يمكن وصف عناصره بأنها النقاط السبع غير الصفرية في  فضاء متجهي ثلاثي الأبعاد فوق الحقل المنتهي GF(2) . مع ذلك، لا يمكن تقديم تمثيل مماثل لماترويد فانو باستخدام الأعداد الحقيقية بدلاً من GF(2).

مصفوفة​${\displaystyle A}$يؤدي إدخال عناصر في حقل إلى ظهور مصفوفة${\displaystyle M}$على مجموعة أعمدتها. مجموعات الأعمدة التابعة في الماترويد هي تلك التي ترتبط خطيًا كمتجهات.

يُطلق على هذا الماترويد اسم ماترويد العمود لـ${\displaystyle A}$، و${\displaystyle A}$يقال إنه يمثل${\displaystyle M}$.

على سبيل المثال، يمكن تمثيل مصفوفة فانو بهذه الطريقة كمصفوفة 3 × 7 ( 0,1) . مصفوفات الأعمدة هي ببساطة مصفوفات متجهة تحت مسمى آخر، ولكن غالبًا ما توجد أسباب لتفضيل تمثيل المصفوفة. ^{[ ب ]}   

يُطلق على الماترويد المكافئ للماترويد المتجهي، على الرغم من اختلاف طريقة عرضه، اسم الماترويد القابل للتمثيل أو الخطي .${\displaystyle M}$يكافئ ذلك مصفوفة متجهة على حقل${\displaystyle F}$ثم نقول${\displaystyle M}$يمكن تمثيله على${\displaystyle F}$؛ بخاصة،${\displaystyle M}$يكون العدد الحقيقي قابلاً للتمثيل إذا كان قابلاً للتمثيل على الأعداد الحقيقية. على سبيل المثال، على الرغم من أن الماترويد الرسومي (انظر أدناه) يُعرض على شكل رسم بياني، إلا أنه قابل للتمثيل أيضًا بواسطة متجهات على أي حقل.

تتمثل إحدى المشكلات الأساسية في نظرية الماترويد في تحديد خصائص الماترويدات التي يمكن تمثيلها على حقل معين.${\displaystyle F;}$تصف حدسية روتا توصيفًا محتملاً لكل حقل منتهٍ . وتتمثل النتائج الرئيسية حتى الآن في توصيفات الماترويدات الثنائية (القابلة للتمثيل على حقل GF(2)) التي وضعها توت (في خمسينيات القرن العشرين)، والماترويدات الثلاثية (القابلة للتمثيل على  حقل العناصر الثلاثة) التي وضعها ريد وبيكسبي، وبشكل منفصل سيمور (في سبعينيات القرن العشرين)، والماترويدات الرباعية (القابلة للتمثيل على  حقل العناصر الأربعة) التي وضعها جيلين وجيراردز وكابور (في عام 2000) . وقد أُعلن عن برهان حدسية روتا، لكنه لم يُنشر، في عام 2014 من قِبل جيلين وجيراردز وويتيل. ^{[ 7 ]}

الماترويد المنتظم هو ماترويد يمكن تمثيله على جميع الحقول الممكنة. أما ماترويد Vámos فهو أبسط مثال على ماترويد لا يمكن تمثيله على أي حقل.

المصدر الأصلي الثاني لنظرية الماترويدات هو نظرية الرسم البياني .

كل رسم بياني محدود (أو رسم بياني متعدد )${\displaystyle G}$يؤدي إلى ظهور الماترويد${\displaystyle M(G)}$على النحو التالي: خذ كما${\displaystyle E}$مجموعة جميع الحواف في${\displaystyle G}$ولنعتبر مجموعة من الحواف مستقلة إذا وفقط إذا كانت غابة ؛ أي إذا لم تحتوي على دورة بسيطة .${\displaystyle M(G)}$يُطلق عليه اسم ماترويد دوري . الماترويدات المشتقة بهذه الطريقة هي ماترويدات رسومية . ليس كل ماترويد رسوميًا، ولكن جميع الماترويدات المكونة من ثلاثة عناصر هي رسومية. ^{[ 8 ]} كل ماترويد رسومي منتظم.

تم اكتشاف مصفوفات أخرى على الرسوم البيانية لاحقاً:

• يتم تعريف الماترويد ثنائي الدائرة للرسم البياني من خلال تسمية مجموعة من الحواف مستقلة إذا كانت كل مجموعة فرعية متصلة تحتوي على دورة واحدة على الأكثر، أي أن مجموعة الحواف مستقلة إذا وفقط إذا كانت غابة زائفة .

• في أي رسم بياني موجه أو غير موجه${\displaystyle G}$يترك${\displaystyle E}$و${\displaystyle F}$لنفترض مجموعتين متميزتين من الرؤوس. في المجموعة${\displaystyle E}$، حدد مجموعة جزئية${\displaystyle U}$أن يكون مستقلاً إذا كان هناك${\displaystyle |U|}$المسارات المنفصلة عن الرؤوس من${\displaystyle F}$على${\displaystyle U}$هذا يُعرّف ماترويد على${\displaystyle E}$يُطلق عليه اسم غامويد : ^{[ 9 ]} الغامويد الصارم هو الذي تكون فيه المجموعة${\displaystyle E}$هي مجموعة الرؤوس الكاملة لـ${\displaystyle G}$[ ^{10 ]​}

• في الرسم البياني ثنائي الأجزاء${\displaystyle G=(U,V,E)}$يمكن للمرء تكوين ماترويد تكون عناصره رؤوسًا على جانب واحد${\displaystyle U}$من التقسيم الثنائي، والمجموعات الفرعية المستقلة هي مجموعات من نقاط نهاية المطابقات في الرسم البياني. يُطلق على هذا اسم الماترويد المستعرض ، ^{[ 11 ] [ 12 ]} وهو حالة خاصة من الغامويد. ^{[ 9 ]} الماترويدات المستعرضة هي الماترويدات الثنائية للغامويدات الصارمة. ^{[ 10 ]}

• تم تعميم الماترويدات الرسومية لتشمل الماترويدات من الرسوم البيانية الموقعة ، ورسوم الربح ، والرسوم البيانية المتحيزة . الرسم البياني${\displaystyle G}$مع فئة خطية مميزة${\displaystyle {\mathcal {B}}}$من الدورات، والمعروفة باسم "الرسم البياني المتحيز".${\displaystyle (G,{\mathcal {B}})}$، لها ماترويدتان، تُعرفان باسم ماترويد الإطار وماترويد الرفع للرسم البياني المتحيز.

إذا كانت كل دورة تنتمي إلى الفئة المميزة، فإن هذه الماترويدات تتطابق مع ماترويد الدورة لـ${\displaystyle G}$. إذا لم يتم تمييز أي دورة، فإن الماتويد الإطاري هو الماتويد ثنائي الدائرة${\displaystyle G}$. الرسم البياني الموقع، الذي يتم تسمية حوافه بالإشارات، والرسم البياني للربح، وهو رسم بياني يتم تسمية حوافه بشكل موجه من مجموعة، كل منهما يؤدي إلى رسم بياني متحيز وبالتالي يحتوي على إطار ومصفوفات رفع.

• تشكل مخططات لامان أساسات الماترويد ثنائي الأبعاد للصلابة ، وهو ماترويد معرف في نظرية الصلابة الهيكلية .

• يترك${\displaystyle G}$ليكن رسمًا بيانيًا متصلًا و${\displaystyle E}$لتكن مجموعة حوافها.${\displaystyle I}$لتكن مجموعة من المجموعات الجزئية${\displaystyle F}$ل${\displaystyle E}$بحيث${\displaystyle G-F}$لا يزال متصلاً. ثم${\displaystyle M^{*}(G)}$، والتي مجموعة عناصرها هي${\displaystyle E}$ومع${\displaystyle I}$باعتبارها فئة من المجموعات المستقلة، فإن الماترويد يسمى ماترويد الرابط لـ${\displaystyle G}$.

دالة الترتيب${\displaystyle r(F)}$يمثل العدد الحلقي للرسم البياني الفرعي المستحث على مجموعة الحواف الفرعية${\displaystyle F}$، وهو ما يساوي عدد الحواف خارج الغابة القصوى لهذا الرسم البياني الفرعي، وكذلك عدد الدورات المستقلة فيه.

المصدر الأصلي الثالث لنظرية الماترويد هو نظرية المجال .

يؤدي امتداد الحقل إلى ظهور الماترويد :

يفترض${\displaystyle F}$و${\displaystyle K}$هي حقول تحتوي على${\displaystyle K}$يحتوي على${\displaystyle F}$. يترك${\displaystyle E}$ليكن أي مجموعة جزئية منتهية من${\displaystyle K}$.

حدد مجموعة جزئية${\displaystyle S}$ل${\displaystyle E}$أن تكون مستقلة جبريًا إذا كان حقل التمديد${\displaystyle F(S)}$له درجة تجاوز تساوي${\displaystyle |S|}$[ ^{13 ]​}

يُطلق على الماترويد المكافئ لماترويد من هذا النوع اسم الماترويد الجبري . ^{[ 14 ]} تُعدّ مشكلة توصيف الماترويدات الجبرية بالغة الصعوبة، ولا يُعرف عنها إلا القليل. ويُقدّم ماترويد فاموس مثالًا على ماترويد غير جبري.

لو${\displaystyle M}$إذا كانت ماترويدًا محدودًا، فيمكننا تعريف الماترويد المتعامد أو الثنائي${\displaystyle M^{*}}$من خلال أخذ نفس المجموعة الأساسية وتسمية المجموعة أساسًا في${\displaystyle M^{*}}$إذا وفقط إذا كان مكملها أساسًا في${\displaystyle M}$ليس من الصعب التحقق من ذلك${\displaystyle M^{*}}$هي ماترويد وأن ثنائية${\displaystyle M^{*}}$يكون${\displaystyle M}$[ ^{15 ]​}

يمكن وصف الثنائية بنفس القدر من الدقة باستخدام طرق أخرى لتعريف الماترويد. على سبيل المثال:

• تكون المجموعة مستقلة في${\displaystyle M^{*}}$إذا وفقط إذا كان مكملها يمتد${\displaystyle M}$.

• المجموعة هي دائرة من${\displaystyle M^{*}}$إذا وفقط إذا كان مكملها عبارة عن ذرة في${\displaystyle M}$.

• دالة رتبة النظام الثنائي هي${\displaystyle r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)}$.

وفقا لنسخة matroid من نظرية كوراتوفسكي ، ثنائي الماتويد الرسومي${\displaystyle M}$يكون ماترويدًا رسوميًا إذا وفقط إذا${\displaystyle M}$هي الماترويد للرسم البياني المستوي . في هذه الحالة، ثنائية لـ${\displaystyle M}$هي الماترويد للرسم البياني الثنائي لـ${\displaystyle G}$[ ^{16 ]} ثنائي الماترويد المتجهي القابل للتمثيل على حقل ^معين${\displaystyle F}$ويمكن تمثيلها أيضًا على${\displaystyle F}$. إن ثنائي الماترويد المستعرض هو غامويد صارم والعكس صحيح.

مثال

الماترويد الدوري للرسم البياني هو الماترويد المزدوج لماترويد الرابط الخاص به.

إذا كانت M مصفوفة ذات مجموعة عناصر E ، و S مجموعة جزئية من E ، فإن تقييد M على S ، ويكتب M | S ، هو المصفوفة على المجموعة S التي تكون مجموعاتها المستقلة هي المجموعات المستقلة لـ M الموجودة في S. ودوائرها هي دوائر M الموجودة في S، ودالة رتبتها هي دالة رتبة M المقيدة على مجموعات جزئية من S. 

في الجبر الخطي، يُقابل هذا التقييد بالفضاء الجزئي المُوَلَّد بواسطة المتجهات في S. وبالمثل، إذا كان T = M − S، يُمكن تسمية ذلك بحذف T ، ويُكتب M \ T أو M − T. المصفوفات الجزئية لـ M هي تحديدًا نتائج سلسلة من عمليات الحذف: الترتيب غير مهم. ^{[ 17 ] [ 18 ]}

العملية المزدوجة للتقييد هي الانكماش. ^{[ 19 ]} إذا كانت T مجموعة جزئية من E ، فإن انكماش M بواسطة T ، ويكتب M / T ، هو الماترويد على المجموعة الأساسية E − T التي تكون دالة رتبتها هي  ${\displaystyle r'(A)=r(A\cup T)-r(T)}$[ ^{20 ] في} الجبر الخطي، يتوافق هذا مع النظر إلى فضاء القسمة بواسطة الفضاء الخطي الناتج عن المتجهات في T ، جنبًا إلى جنب مع صور المتجهات في E  − T. 

تُسمى الماترويد N المُستمدة من M عبر سلسلة من عمليات التقييد والانكماش بالماترويد الصغير لـ M. [ ^{18 ] [ 21 ] نقول} إن M تحتوي على N كماتر صغير . يمكن تمييز العديد من عائلات الماترويدات المهمة بالماترويدات الصغيرة الدنيا التي لا تنتمي إلى العائلة؛ وتُسمى هذه الماترويدات بالماترويدات الممنوعة أو المستبعدة . ^{[ 22 ]}

ليكن M مصفوفة ذات مجموعة أساسية من العناصر E ، وليكن N مصفوفة أخرى على مجموعة أساسية F. المجموع المباشر للمصفوفتين M و N هو المصفوفة التي تكون مجموعتها الأساسية هي الاتحاد المنفصل لـ E و F ، وتكون مجموعاتها المستقلة هي الاتحادات المنفصلة لمجموعة مستقلة من M مع مجموعة مستقلة من N.

اتحاد M و N هو الماترويد الذي مجموعته الأساسية هي اتحاد (وليس اتحادًا منفصلاً) E و F ، ومجموعاته المستقلة هي تلك المجموعات الجزئية التي تمثل اتحاد مجموعة مستقلة في M ومجموعة مستقلة في N. عادةً ما يُستخدم مصطلح "الاتحاد" عندما E = F ، لكن هذا الافتراض ليس شرطًا أساسيًا. إذا كانت E و F منفصلتين، فإن الاتحاد هو المجموع المباشر.

تُعرَّف متعددة الحدود المميزة لـ M - والتي تُسمى أحيانًا متعددة الحدود اللونية ، ^{[ 32 ]} على الرغم من أنها لا تحسب التلوينات - على النحو التالي:

${\displaystyle p_{M}(\lambda ):=\sum _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E)-r(S)},}$

أو بصورة مكافئة (طالما أن المجموعة الفارغة مغلقة في M ) كما

${\displaystyle p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)},}$

حيث تشير μ إلى دالة موبيوس للشبكة الهندسية للماترويد ويتم حساب المجموع على جميع المستويات A للماترويد. ^{[ 33 ]}

• عندما تكون M هي المصفوفة الدورية M ( G ) للرسم البياني G ، فإن متعدد الحدود المميز هو تحويل طفيف لمتعدد الحدود اللوني ، والذي يتم إعطاؤه بواسطة χ _G  (λ) = λ ^c p _{M ( G )}  ( λ )، حيث c هو عدد المكونات المتصلة لـ G.

• عندما تكون M هي مصفوفة الروابط M *( G ) للرسم البياني G ، فإن متعدد الحدود المميز يساوي متعدد حدود التدفق لـ G.

• عندما تكون M هي الماترويد M ( A ) لترتيب A من المستويات الفائقة الخطية في${\displaystyle \mathbb {R} ^{n}}$(أو F ⁿ حيث F هو أي حقل)، يتم إعطاء متعدد الحدود المميز للترتيب بواسطة p _A  ( λ ) = λ ^{n − r ( M )} p _M  ( λ ).

أرقام ويتني من النوع الأول${\displaystyle M}$هي معاملات قوى${\displaystyle \lambda }$في متعددة الحدود المميزة. على وجه التحديد،${\displaystyle i}$رقم ويتني${\displaystyle w_{i}(M)}$هو معامل${\displaystyle \lambda ^{r(M)-i}}$وهو مجموع قيم دالة موبيوس:

${\displaystyle w_{i}(M)=\sum \{\mu (\emptyset ,A):r(A)=i\},}$

مجموع هذه الأرقام على الشقق من الرتبة اليمنى. وتتبادل هذه الأرقام في الإشارة، بحيث${\displaystyle (-1)^{i}w_{i}(M)>0}$ل${\displaystyle 0\leq i\leq r(M)}$.

أرقام ويتني من النوع الثاني${\displaystyle M}$تمثل هذه الأرقام عدد الشقق في كل رتبة. أي،${\displaystyle W_{i}(M)}$هو رقم الرتبة ${\displaystyle i}$شقق سكنية.

تُعمّم أعداد ويتني بنوعيها أعداد ستيرلينغ من النوع الأول والثاني، وهي أعداد ويتني الخاصة بالماترويد الدوري للرسم البياني الكامل ، وبشكل مكافئ، لشبكة التقسيم . وقد سُميت هذه الأعداد نسبةً إلى هاسلر ويتني ، المؤسس المشارك لنظرية الماترويد، من قِبل جيان كارلو روتا . وقد تم توسيع نطاق هذا الاسم ليشمل الأعداد المماثلة للمجموعات المرتبة جزئيًا ذات الرتبة المحدودة .

متعددة حدود توت للماترويد،${\displaystyle T_{M}(x,y)}$يُعمم هذا المفهوم متعدد الحدود المميز إلى متغيرين. وهذا يمنحه تفسيرات توافقية أكثر، كما يمنحه خاصية الازدواجية.

${\displaystyle T_{M^{*}}(x,y)=T_{M}(y,x),}$

مما يعني وجود عدد من الازدواجيات بين خصائص${\displaystyle M}$وخصائص${\displaystyle M^{*}}$أحد تعريفات متعددة حدود توت هو

${\displaystyle T_{M}(x,y)=\sum _{S\subseteq E}(x-1)^{r(M)-r(S)}\ (y-1)^{|S|-r(S)}.}$

وهذا يعبر عن متعددة حدود توت كتقييم لمتعددة الحدود ذات الرتبة المشتركة أو متعددة الحدود المولدة للرتبة ، ^{[ 36 ]}

${\displaystyle R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}.}$

من هذا التعريف، يسهل ملاحظة أن متعددة الحدود المميزة هي، حتى عامل بسيط، تقييم لـ${\displaystyle T_{M}}$، خاصة،

${\displaystyle p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0).}$

وهناك تعريف آخر يتعلق بالأنشطة الداخلية والخارجية ومجموع القواعد، مما يعكس حقيقة أن${\displaystyle T(1,1)}$هو عدد القواعد. ^{[ 37 ]} هذا، الذي يجمع على عدد أقل من المجموعات الفرعية ولكنه يحتوي على مصطلحات أكثر تعقيدًا، كان تعريف توت الأصلي.

يوجد تعريف آخر يتعلق بالاستدعاء الذاتي عن طريق الحذف والانكماش. ^{[ 38 ]} متطابقة الحذف والانكماش هي

${\displaystyle F(M)=F(M-e)+F(M/e)}$

متى${\displaystyle e}$ليست حلقة تكرارية ولا حلقة تكرارية مشتركة. وهي دالة ثابتة للماترويدات (أي دالة تأخذ نفس القيمة على الماترويدات المتماثلة) تحقق هذا الاستدعاء الذاتي والشرط الضربي.

${\displaystyle F(M\oplus M')=F(M)F(M')}$

يُقال إنها ثابتة من نوع توت-غروتينديك . ^{[ 36 ]} تُعدّ متعددة حدود توت أكثر الثوابت عمومية من هذا النوع؛ أي أن متعددة حدود توت هي ثابتة من نوع توت-غروتينديك، وكل ثابت من هذا النوع هو تقييم لمتعددة حدود توت. ^{[ 32 ]}

متعددة حدود توت${\displaystyle T_{G}}$يمثل متعدد حدود توت الرسم البياني${\displaystyle T_{M(G)}}$من دورتها الماترويدية.