رسم بياني موسع

يُعرَّف امتداد الحافة (أو العدد المحيطي المتساوي أو ثابت شيغر ) h ( G ) للرسم البياني G ذي n رأسًا على النحو التالي:

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial S|}{|S|}},}$

أين${\displaystyle \partial S:=\{\{u,v\}\in E(G)\$ :\ u\in S,v\notin S\},}

والتي يمكن كتابتها أيضًا على النحو التالي: ∂S = E ( S , S ) حيث S : = V  ( G ) \ S هي متممة S و

${\displaystyle E(A,B)=\{\{u,v\}\in E(G)\$ u في A، v في B

الحواف بين المجموعات الفرعية من الرؤوس A و B ⊆ V ( G ) .

في المعادلة، يكون الحد الأدنى على جميع المجموعات غير الفارغة S التي تحتوي ^على n ⁄ 2 رأس على الأكثر و ∂ S هو حدود الحافة لـ S ، أي مجموعة الحواف التي لها نقطة نهاية واحدة فقط في S. ^{[ 2} ]

بشكل بديهي،

${\displaystyle \min {|\partial S|}=\min |E({S},{\overline {S}})|}$

يمثل الحد الأدنى لعدد الحواف التي يجب قطعها لتقسيم الرسم البياني إلى قسمين. تعمل عملية توسيع الحواف على توحيد هذا المفهوم من خلال القسمة على أصغر عدد من الرؤوس بين الجزأين. لفهم كيف يمكن للتوحيد أن يغير القيمة بشكل جذري، انظر المثال التالي: خذ رسمين بيانيين كاملين لهما نفس عدد الرؤوس n، وأضف n حافة بين الرسمين البيانيين عن طريق توصيل رؤوسهما بشكل مباشر. سيكون الحد الأدنى للقطع هو n، لكن توسيع الحواف سيكون 1.

لاحظ أنه في min | ∂ S | ، يمكن إجراء التحسين بشكل مكافئ إما على 0 ≤ | S | ≤ n ⁄ 2 أو على أي مجموعة جزئية غير فارغة، لأن ${\displaystyle E(S,{\overline {S}})=E({\overline {S}},S)}$لا ينطبق الأمر نفسه على h ( G ) بسبب التطبيع بواسطة | S | . إذا أردنا كتابة h ( G ) مع تحسين على جميع المجموعات الجزئية غير الفارغة، فيمكننا إعادة كتابتها على النحو التالي:

${\displaystyle h(G)=\min _{\emptyset \subsetneq S\subsetneq V(G)}{\frac {|E({S},{\overline {S}})|}{\min\{|S|,|{\overline {S}}|\}}}.}$

يُعرَّف عدد الرؤوس المتساوي المحيط h _out ( G ) (ويُسمى أيضًا توسيع الرؤوس أو تكبيرها ) للرسم البياني G على النحو التالي:

${\displaystyle h_{\text{out}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{out}}(S)|}{|S|}},}$

حيث ∂out ( S ) هي الحدود الخارجية لـ S ، أي مجموعة الرؤوس في V ( G )\ S التي لها جار واحد على الأقل في S. ^{[ 3} ] في صيغة معدلة لهذا التعريف (تسمى توسيع الجوار الفريد ) _، ^يتم _{استبدال ∂out} ( S ) بمجموعة الرؤوس في V التي لها جار واحد فقط في S. ^{[ 4 ]}

يُعرَّف عدد الرؤوس المتساوية المحيط h في _الرسم البياني G على النحو التالي:

${\displaystyle h_{\text{in}}(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial _{\text{in}}(S)|}{|S|}},}$

أين${\displaystyle \partial _{\text{in}}(S)}$^{[ 3} ] هو الحد الداخلي لـ S ، أي مجموعة الرؤوس في S التي ^لها جار واحد على الأقل في V ( G ) \ S.

عندما تكون G منتظمة من الدرجة d ، يُمكن تعريف التوسع جبريًا خطيًا بناءً على القيم الذاتية لمصفوفة التجاور A = A ( G ) لـ G ، حيث A _{_ij} هو عدد الحواف بين الرأسين i و j . ^{[ 5 ]} ولأن A متناظرة ، فإن نظرية الطيف تُشير إلى أن A لها n قيمة ذاتية حقيقية λ _₁ ≥ λ _₂ ≥ … ≥ λ_{_n} . من المعروف أن جميع هذه القيم الذاتية تقع في الفترة [−d , d ] ، وبشكل أكثر تحديدًا، من المعروف أن λ _{_n} = −d إذا وفقط إذا كانت G ثنائية الأجزاء.

بصورة أكثر رسمية، نشير إلى رسم بياني ذي n رأسًا و d منتظمًا بـ

${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$

باعتباره رسمًا بيانيًا ( n , d , λ ) . يُعد الحد الذي يُعطيه الرسم البياني ( n , d , λ ) على λ _i لـ i ≠ 1 مفيدًا في العديد من السياقات، بما في ذلك مبرهنة مزج الموسع .

يمكن أن يكون التوسع الطيفي ثنائي الجانب ، كما هو موضح أعلاه، مع${\displaystyle \max _{i\neq 1}|\lambda _{i}|\leq \lambda }$أو قد يكون الأمر من جانب واحد ، مع${\displaystyle \max _{i\neq 1}\lambda _{i}\leq \lambda }$أما المفهوم الأخير فهو مفهوم أضعف ينطبق أيضاً على الرسوم البيانية ثنائية الأجزاء، ولا يزال مفيداً للعديد من التطبيقات، مثل مبرهنة ألون-تشونغ. ^{[ 6 ]}

لأن G منتظم، فإن التوزيع المنتظم${\displaystyle u\in \mathbb {R} ^{n}}$حيث uᵢ ₌ 1 / n لجميع i = 1، ...، n _، يمثل التوزيع الثابت للرسم البياني G. أي أن لدينا Au = du ، و u متجه ذاتي للمصفوفة A بقيمة ذاتية λ₁ = d ، حيث d هي درجة رؤوس الرسم البياني G. تُعرَّف الفجوة الطيفية للرسم البياني G بأنها d - λ₂ _{، وهي تقيس} ^التوسع الطيفي للرسم البياني G. [ ^{7 ]}

إذا قمنا بتعيين

${\displaystyle \lambda =\max\{|\lambda _{2}|,|\lambda _{n}|\}}$

بما أن هذه هي أكبر قيمة ذاتية تتوافق مع متجه ذاتي متعامد مع u ، فيمكن تعريفها بشكل مكافئ باستخدام حاصل قسمة رايلي :

${\displaystyle \lambda =\max _{v\perp u,v\neq 0}{\frac {\|Av\|_{2}}{\|v\|_{2}}},}$

أين

${\displaystyle \|v\|_{2}=\left(\sum _{i=1}^{n}v_{i}^{2}\right)^{1/2}}$

المعيار 2 للمتجه${\displaystyle v\in \mathbb {R} ^{n}}$.

تُستخدم الصيغ المعيارية لهذه التعريفات على نطاق واسع، وهي أكثر ملاءمةً في عرض بعض النتائج. هنا، نأخذ بعين الاعتبار المصفوفة 1 / dA ، وهي مصفوفة انتقال ماركوف للرسم البياني G. تتراوح قيمها الذاتية بين -1 و1. بالنسبة للرسوم البيانية غير المنتظمة بالضرورة، يمكن تعريف طيف الرسم البياني بشكل مشابه باستخدام القيم الذاتية لمصفوفة لابلاس . أما بالنسبة للرسوم البيانية الموجهة ، فنأخذ بعين الاعتبار القيم المفردة لمصفوفة التجاور A ، والتي تساوي جذور القيم الذاتية ^{للمصفوفة} المتناظرة ATA .

عائلة${\displaystyle (G_{i})_{i\in \mathbb {N} }}$ل${\displaystyle d}$- الرسوم البيانية المنتظمة ذات الحجم المتزايد هي عائلة موسعة إذا${\displaystyle h(G_{i})}$^{[ 8 ]}​

عندما يكون الرسم _{البياني} G منتظمًا من الدرجة d ، أي أن درجة كل رأس فيه هي d ، توجد علاقة بين ثابت المحيط h ( G ) والفجوة d − λ² في طيف عامل التجاور لـ G. وفقًا لنظرية الرسم البياني الطيفية القياسية، فإن القيمة الذاتية التافهة لعامل التجاور في الرسم البياني المنتظم من الدرجة d هي λ₁ ₌ d ، والقيمة الذاتية غير التافهة الأولى هي λ₂ . إذا كان G متصلًا، فإن λ₂ < d . تنص متباينة منسوبة إلى دودزيوك ^{[ 9 ]} ، وبشكل مستقل إلى ألون وميلمان ^{[ 10 ]،} _{على ما يلي} ^{[ 11 ]} _.

${\displaystyle {\tfrac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

في الواقع، الحد الأدنى دقيق. يتحقق الحد الأدنى في حالة المكعب الفائق Q _{_n} ، حيث h ( G ) = 1 و d – λ _² = 2. أما الحد الأعلى فيتحقق (تقاربياً) لدورة، حيث h ( C_{_n} ) = 4/ n = Θ(1/ n ) و d – λ _² = 2 – 2cos(2).${\displaystyle \pi }$( ن ) ≈ (2${\displaystyle \pi }$/ n ) ² = Θ(1/ n ² ) . ^{[ 1 ]} ويُعطى حدٌّ أفضل في ^{[ 12 ]} على النحو التالي:

${\displaystyle h(G)\leq {\sqrt {d^{2}-\lambda _{2}^{2}}}.}$

ترتبط هذه المتباينات ارتباطًا وثيقًا بحد شيغر لسلاسل ماركوف ويمكن اعتبارها نسخة منفصلة من متباينة شيغر في الهندسة الريمانية .

وقد تمت دراسة روابط مماثلة بين أرقام المحيط المتساوي للرؤوس والفجوة الطيفية أيضًا: ^{[ 13 ]}

${\displaystyle h_{\text{out}}(G)\leq \left({\sqrt {4(d-\lambda _{2})}}+1\right)^{2}-1}$

${\displaystyle h_{\text{in}}(G)\leq {\sqrt {8(d-\lambda _{2})}}.}$

من الناحية التقاربية، فإن الكميات h ² ⁄ d و h _out و h _in ² كلها محدودة من الأعلى بواسطة الفجوة الطيفية O ( d – λ ₂ ) .

تُعرف الإنشاءات الجبرية القائمة على مخططات كايلي لمختلف أنواع مخططات التوسيع. يُنسب الإنشاء التالي إلى مارغوليس، وقد حلله غابر وغليل. ^{[ 16 ]} لكل عدد طبيعي n ، يُنظر في المخطط G_{_n} بمجموعة الرؤوس${\displaystyle \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$، أين${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$لكل رأس${\displaystyle (x,y)\in \mathbb {Z} _{n}\times \mathbb {Z} _{n}}$رؤوسها الثمانية المجاورة هي

${\displaystyle (x\pm 2y,y),(x\pm (2y+1),y),(x,y\pm 2x),(x,y\pm (2x+1)).}$

ثم ينطبق ما يلي:

نظرية. لكل قيمة n ، يكون للرسم البياني G _n ثاني أكبر قيمة ذاتية${\displaystyle \lambda (G)\leq 5{\sqrt {2}}}$.

بحسب نظرية ألون وبوبانا ، فإن جميع الرسوم البيانية المنتظمة من الدرجة d الكبيرة بما فيه الكفاية تحقق${\displaystyle \lambda _{2}\geq 2{\sqrt {d-1}}-o(1)}$حيث λ ₂ هي ثاني أكبر قيمة ذاتية بالقيمة المطلقة. ^{[ 17 ]} وكنتيجة مباشرة لذلك، نعلم أنه لكل قيمة ثابتة لـ d و${\displaystyle \lambda <2{\sqrt {d-1}}}$، يوجد عدد محدود فقط من الرسوم البيانية ( n ، d ، λ ) . رسوم رامانوجان البيانية هي رسوم بيانية منتظمة من الدرجة d يكون هذا الحد فيها دقيقًا، ويحقق ^{[ 18 ]}

${\displaystyle \lambda =\max _{|\lambda _{i}|<d}|\lambda _{i}|\leq 2{\sqrt {d-1}}.}$

وبالتالي فإن مخططات رامانوجان لها أصغر قيمة ممكنة لـ λ _2. وهذا يجعلها موسعات طيفية ممتازة.

يوضح كل من لوبوتزكي وفيليبس وسارناك (1988) ومارجوليس (1988) ومورجنسترن (1994) كيفية إنشاء رسوم بيانية رامانوجان بشكل صريح. ^{[ 19 ]}

في عام 1985، افترض ألون أن معظم الرسوم البيانية المنتظمة من الدرجة d على n رأسًا، بالنسبة لقيم n الكبيرة بما فيه الكفاية ، هي تقريبًا رسوم رامانوجان. ^{[ 20 ]} أي، بالنسبة لـ ε > 0 ، فإنها تحقق

${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$.

في عام 2003، أثبت جويل فريدمان صحة الفرضية وحدد المقصود بعبارة "معظم الرسوم البيانية المنتظمة من الدرجة d " من خلال إظهار أن الرسوم البيانية المنتظمة العشوائية من الدرجة d لها${\displaystyle \lambda \leq 2{\sqrt {d-1}}+\varepsilon }$لكل ε > 0 باحتمالية 1 – O ( n ^-τ ) ، حيث ^{[ 21 ] [ 22 ]}

${\displaystyle \tau =\left\lceil {\frac {{\sqrt {d-1}}+1}{2}}\right\rceil .}$

وقدّم بودر برهاناً أبسط لنتيجة أضعف قليلاً. ^{[ 23 ] [ 24 ] [ 25 ]}

قدم ماركوس وسبيلمان وسريفاستافا ^[ 26 ] ^{[ 27 ]} بناءًا لرسوم ^{بيانية رامانوجان ثنائية} الأجزاء على أساس عمليات الرفع .

في عام 2024، أثبتت دراسة أولية أجراها كل من جياويانغ هوانغ، وثيو ماكنزي، وهورنغ تزر ياو أن

${\displaystyle \lambda \leq 2{\sqrt {d-1}}}$.

مع نسبة القيم الذاتية التي تصل إلى حد Alon-Boppana حوالي 69٪ من إثبات أن عالمية الحافة صحيحة، أي أنها تتبع توزيع Tracy-Widom المرتبط بمجموعة Gaussian Orthogonal Ensemble ^{[ 28 ] [ 29 ]}

قدّم رينغولد وفادان وويغدرسون مفهوم الضرب المتعرج في عام 2000. ^{[ 30} ] وبشكلٍ عام، ينتج عن الضرب المتعرج لرسمين بيانيين موسعين رسم بياني بتوسع أسوأ قليلاً. لذلك، يمكن استخدام الضرب المتعرج أيضًا لإنشاء عائلات من الرسوم البيانية الموسعة. إذا ^كان G رسمًا بيانيًا من النوع ( n , d , λ₁ ) و H رسمًا بيانيًا من النوع ( m , d , _{λ₂ )} ، فإن الضرب المتعرج G ◦ H هو رسم بياني من النوع ( nm , d₂ , φ ( λ₁ _, ^λ₂ ) ₎ حيث يتمتع φ بالخصائص التالية.

1. إذا φ ₁ < 1 و lect ₂ < 1 , فإن φ ( lect ₁ , lect ₂ ) < 1 ;
2. φ ( lect ₁ , lect ₂ ) ≥ lect ₁ + lect ₂ .

على وجه التحديد، ^{[ 30 ]}

${\displaystyle \phi (\lambda _{1},\lambda _{2})={\frac {1}{2}}(1-\lambda _{2}^{2})\lambda _{2}+{\frac {1}{2}}{\sqrt {(1-\lambda _{2}^{2})^{2}\lambda _{1}^{2}+4\lambda _{2}^{2}}}.}$

لاحظ أن الخاصية (1) تعني أن حاصل ضرب متعرج لاثنين من الرسوم البيانية الموسعة هو أيضًا رسم بياني موسع، وبالتالي يمكن استخدام حاصل الضرب المتعرج استقرائيًا لإنشاء عائلة من الرسوم البيانية الموسعة.

يمكن تصور بناء حاصل الضرب المتعرج بشكل بديهي على النحو التالي: يتم توسيع كل رأس من رؤوس الرسم البياني G إلى "سحابة" من m رأس، يرتبط كل منها بحافة مختلفة متصلة بالرأس. يُرمز لكل رأس الآن بالرمز ( v , k )، حيث يشير v إلى رأس أصلي في G ، ويشير k إلى الحافة رقم k من v . يكون الرأسان ( v , k ) و ( w , ℓ ) متصلين إذا كان من الممكن الانتقال من ( v , k ) إلى ( w , ℓ ) عبر سلسلة الحركات التالية.

1. Zig – الانتقال من ( v , k ) إلى ( v , k' ) ، باستخدام حافة من H .
2. اقفز عبر السحب باستخدام الحافة k' في G للوصول إلى ( w , ℓ ′ ) .
3. Zag – الانتقال من ( w , ℓ ′ ) إلى ( w , ℓ ) باستخدام حافة من H . ^{[ 30 ]}

يتم تكوين رفع r للرسم البياني عن طريق استبدال كل رأس بـ r رأس، وكل حافة بمطابقة بين المجموعات المقابلة من${\displaystyle r}$الرؤوس. يرث الرسم البياني المرفوع القيم الذاتية للرسم البياني الأصلي، ويحتوي على بعض القيم الذاتية الإضافية. وقد أظهر بيلو ولينيال ^{[ 31 ] [ 32 ]} أن كل رسم بياني منتظم من الدرجة d له رفع من الدرجة 2 تكون فيه القيم الذاتية الإضافية على الأكثر${\displaystyle O({\sqrt {d\log ^{3}d}})}$من حيث الحجم. كما أظهروا أنه إذا كان الرسم البياني الأولي موسعًا جيدًا بما فيه الكفاية، فإنه يمكن إيجاد رفع جيد من الدرجة 2 في وقت متعدد الحدود ، مما يوفر بناءً فعالًا للموسعات المنتظمة من الدرجة d لكل d .

افترض بيلو ولينال أن الحد${\displaystyle O({\sqrt {d\log ^{3}d}})}$يمكن تحسينه إلى${\displaystyle 2{\sqrt {d-1}}}$وهو ما يُعدّ الأمثل نظرًا لحدّ ألون-بوبانا . وقد أُثبتت هذه الفرضية في سياق الرسوم البيانية ثنائية الأجزاء بواسطة ماركوس ، وسبيل مان، وسريفاستافا [ ^{26 ] [ 27 ] ،} الذين استخدموا طريقة تداخل كثيرات الحدود. ونتيجةً لذلك، حصلوا على بناء بديل لرسوم رامانوجان ثنائية الأجزاء . وقد حُوِّل البرهان الأصلي غير البنّاء إلى خوارزمية بواسطة مايكل ب. كوهين ^{[ 33 ]} . وفي وقت لاحق، عُمِّمت هذه الطريقة لتشمل عمليات الرفع من الرتبة r بواسطة هول، وبودر، وساوين ^{[ 34 ] .}

توجد العديد من النتائج التي تُظهر وجود رسوم بيانية ذات خصائص توسع جيدة من خلال حجج احتمالية. في الواقع، أثبت بينسكر ^{[ 35 ]} _{وجود الموسعات لأول مرة ،} حيث بيّن أنه بالنسبة لرسم بياني ثنائي منتظم ذي n رأسًا يسارًا و d _رأسًا ، فإن | N ( S ) | ≥ ( d – 2) | S | لجميع المجموعات الجزئية من الرؤوس | S | ≤ cdn باحتمالية عالية ، حيث cd ثابت يعتمد على d ويساوي O ( d ^{- 4} ) . وأظهر ألون ورويشمان ^{[ 36 ]} أنه لكل 1 > ε > 0 ، يوجد c ( ε ) > 0 بحيث يتحقق ما يلي: بالنسبة لمجموعة G من الرتبة n ، نعتبر رسم كايلي البياني على G مع c ( ε ) log₂n _عنصرًا مختارًا عشوائيًا من G. عندئذٍ، في حالة اقتراب n من اللانهاية، يكون الرسم البياني الناتج موسعًا من النوع ε بشكل شبه مؤكد .

في عام 2021، قام ألكسندر بتعديل خوارزمية ماركوف مونت كارلو المتسلسلة (MCMC) للبحث عن تركيبات عشوائية لإنتاج رسوم بيانية رامانوجان ذات حجم رأس ثابت ودرجة انتظام ثابتة. ^{[ 37 ]} تُظهر النتائج وجود رسوم بيانية رامانوجان لكل زوج من حجم الرأس ودرجة الانتظام حتى 2000 رأس.

في عام 2024، قدم ألون بناءً صريحًا للرسوم البيانية شبه رامانوجان لكل زوج من أحجام الرؤوس ودرجاتها.

تنصّ مبرهنة مزج الموسّعات على أنه بالنسبة لرسم بياني من الرتبة ( n , d , λ ) ، لأي مجموعتين جزئيتين من الرؤوس S و T ⊆ V ، يكون عدد الحواف بين S و T مساويًا تقريبًا لما هو متوقع في رسم بياني عشوائي منتظم من الرتبة d . ويكون هذا التقريب أدقّ كلما صغرت قيمة λ . في الرسم البياني العشوائي المنتظم من الرتبة d ، وكذلك في الرسم البياني العشوائي من نوع Erdős–Rényi باحتمالية حافة d / n ، نتوقع وجود d / n • | S | • | T | حافة بين S و T.

بصورة أكثر رسمية، لنفترض أن E ( S , T ) يمثل عدد الحواف بين S و T. إذا لم تكن المجموعتان منفصلتين، فإن الحواف في تقاطعهما تُحسب مرتين، أي

${\displaystyle E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S).}$

ثم تنصّ مبرهنة مزج الموسّع على أن المتباينة التالية صحيحة:

${\displaystyle \left|E(S,T)-{\frac {d\cdot |S|\cdot |T|}{n}}\right|\leq \lambda {\sqrt {|S|\cdot |T|}}.}$

العديد من خصائص الرسوم البيانية ( n ، d ، λ ) هي نتائج طبيعية لفرضيات مزج الموسع، بما في ذلك ما يلي. ^{[ 1 ]}

• المجموعة المستقلة في الرسم البياني هي مجموعة جزئية من الرؤوس لا يوجد فيها رأسان متجاوران. في الرسم البياني ( n , d , λ ) ، يكون حجم المجموعة المستقلة على الأكثر λn / d .
• العدد اللوني للرسم البياني G ، χ ( G ) ، هو الحد الأدنى لعدد الألوان اللازمة لجعل الرؤوس المتجاورة ذات ألوان مختلفة. أثبت هوفمان أن d ⁄ λ ≤ χ ( G ) ، ^{[ 38 ]} بينما أثبت ألون وكريفليفيتش وسوداكوف أنه إذا كان d < 2n ⁄ 3 ، فإن ^{[ 39 ]}

${\displaystyle \chi (G)\leq O\left({\frac {d}{\log(1+d/\lambda )}}\right).}$

• قطر الرسم البياني هو أقصى مسافة بين رأسين، حيث تُعرَّف المسافة بين رأسين بأنها أقصر مسار بينهما. وقد أثبت تشونغ أن قطر الرسم البياني ( n , d , λ ) هو على الأكثر ^{[ 40 ]} .

${\displaystyle \left\lceil \log {\frac {n}{\log(d/\lambda )}}\right\rceil .}$

ينص حد تشيرنوف على أنه عند أخذ عينات مستقلة متعددة من متغير عشوائي في النطاق [−1, 1] ، يكون متوسط ​​هذه العينات، باحتمالية عالية، قريبًا من القيمة المتوقعة للمتغير العشوائي. وتنص مبرهنة أخذ العينات من مسار التوسيع، التي وضعها أجتاي وكوملوس وسزيميريدي (1987) وجيلمان (1998) ، على أن هذا ينطبق أيضًا عند أخذ عينات من مسار على رسم بياني موسع. وهذا مفيد بشكل خاص في نظرية إزالة العشوائية ، لأن أخذ العينات وفقًا لمسار التوسيع يستخدم عددًا أقل بكثير من البتات العشوائية مقارنةً بأخذ العينات بشكل مستقل.

تستقبل شبكات الفرز مجموعة من المدخلات وتُنفذ سلسلة من الخطوات المتوازية لفرزها. تتألف الخطوة المتوازية من إجراء أي عدد من المقارنات المنفصلة، ​​مع إمكانية تبديل أزواج من المدخلات المُقارنة. يُحدد عمق الشبكة بعدد الخطوات المتوازية التي تُنفذها. تلعب الرسوم البيانية المُوسِّعة دورًا هامًا في شبكة فرز AKS، التي تصل إلى عمق O (log n ) . على الرغم من أن هذا العمق هو الأفضل المعروف لشبكة فرز، إلا أن الاعتماد على المُوسِّعات يجعل الحد الثابت كبيرًا جدًا للاستخدام العملي.

في شبكة فرز AKS، تُستخدم الرسوم البيانية الموسعة لإنشاء مُقسِّمات ε- ذات عمق محدود . يأخذ مُقسِّم ε- ذات كمدخل تبديلًا بطول n للمجموعة (1، ...، n ) ويُقسِّم المدخلات إلى مجموعتين منفصلتين A و B بحيث يكون لكل عدد صحيح k ≤ n ⁄ 2، على الأكثر εk من أصغر k مدخلات في المجموعة B، وعلى الأكثر εk من أكبر k مدخلات في المجموعة A. تُسمى المجموعتان A و B مُقسِّم ε- ذات عمق .

استنادًا إلى Ajtai و Komlós و Szemerédi (1983) ، يمكن إنشاء مُوسِّع ثنائي الأجزاء بعمق d ε على النحو التالي. خذ مُوسِّعًا ثنائي الأجزاء من الدرجة d و n رأسًا، مع جزأين X و Y متساويين في الحجم بحيث يكون لكل مجموعة فرعية من الرؤوس بحجم لا يتجاوز εn ما لا يقل عن 1 – ε / ε جارًا .

يمكن اعتبار رؤوس الرسم البياني بمثابة سجلات تحتوي على مدخلات، بينما يمكن اعتبار الحواف بمثابة أسلاك تقارن مدخلات سجلين. في البداية، نضع عشوائيًا نصف المدخلات في X والنصف الآخر في Y ، ثم نحلل الحواف إلى d من المطابقات التامة. الهدف هو أن ينتهي بنا المطاف بحيث يحتوي X تقريبًا على النصف الأصغر من المدخلات، و Y تقريبًا على النصف الأكبر منها. لتحقيق ذلك، نعالج كل مطابقة بالتتابع من خلال مقارنة السجلات المقترنة بحواف هذه المطابقة، ونصحح أي مدخلات غير مرتبة. تحديدًا، لكل حافة من حواف المطابقة، إذا كان المدخل الأكبر في السجل X والمدخل الأصغر في السجل Y ، نبدل المدخلين بحيث يكون الأصغر في X والأكبر في Y. من الواضح أن هذه العملية تتكون من d خطوات متوازية.

بعد كل d جولة، نعتبر A مجموعة المدخلات في المسجلات في X و B مجموعة المدخلات في المسجلات في Y للحصول على ε- نصف. ولتوضيح ذلك، نلاحظ أنه إذا كان المسجل u في X والمسجل v في Y متصلين بحافة uv ، فبعد معالجة المطابقة مع هذه الحافة، يكون المدخل في u أقل من المدخل في v . علاوة على ذلك، تظل هذه الخاصية صحيحة طوال بقية العملية. الآن، لنفترض أنه بالنسبة لبعض k ≤ n ⁄ 2 ، يوجد أكثر من εk من المدخلات (1، ...، k ) في B. عندئذٍ ، وفقًا لخصائص توسيع الرسم البياني، تكون مسجلات هذه المدخلات في Y متصلة بما لا يقل عن 1 – ε / ε k مسجل في X. إجمالاً، يشكل هذا أكثر من k سجلاً، لذا يجب أن يكون هناك سجل A في X متصل بسجل B في Y بحيث لا يكون المدخل النهائي لـ A ضمن (1، ...، k ) ، بينما يكون المدخل النهائي لـ B ضمنها. مع ذلك، يخالف هذا الخاصية السابقة، وبالتالي يجب أن تكون مجموعتا المخرجات A و B من نوع ε- النصف.