معضلة خلط الموسع

يمكننا في الواقع أن نثبت ذلك.

$\displaystyle \left|e(S,T)-{\frac {d|S||T|}{n}}\right|\leq \lambda {\sqrt {|S||T|(1-|S|/n)(1-|T|/n)}}\,}$

باستخدام تقنيات مماثلة. ^{[ 1 ]}

بالنسبة للرسوم البيانية ثنائية الانتظام ، لدينا التباين التالي، حيث نأخذ${\displaystyle \lambda }$لتكون ثاني أكبر قيمة ذاتية. ^{[ 2 ]}

يترك${\displaystyle G=(L,R,E)}$ليكن رسمًا بيانيًا ثنائي الأجزاء بحيث يكون كل رأس في${\displaystyle L}$يقع بجوار${\displaystyle d_{L}}$رؤوس${\displaystyle R}$وكل رأس في${\displaystyle R}$يقع بجوار${\displaystyle d_{R}}$رؤوس${\displaystyle L}$. يترك${\displaystyle S\subseteq L,T\subseteq R}$مع${\displaystyle |S|=\alpha |L|}$و${\displaystyle |T|=\beta |R|}$. يترك${\displaystyle e(G)=|E(G)|}$. ثم

$\displaystyle \left|\frac {e(S,T)}{e(G)}}-\alpha \beta \right|\leq {\frac {\lambda }{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta (1-\alpha )(1-\beta )}}\leq {\frac {\lambda }{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta }}\,.}$

لاحظ أن${\displaystyle {\sqrt {d_{L}d_{R}}}}$هي أكبر قيمة ذاتية لـ${\displaystyle G}$.

يترك${\displaystyle A_{G}}$لتكن مصفوفة التجاور لـ${\displaystyle G}$ودع${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{n}}$لتكن القيم الذاتية لـ${\displaystyle A_{G}}$(هذه القيم الذاتية حقيقية لأن${\displaystyle A_{G}}$(متناظر). نعلم أن${\displaystyle \lambda _{1}=d}$مع المتجه الذاتي المقابل${\displaystyle v_{1}={\frac {1}{\sqrt {n}}}\mathbf {1} }$، عملية تطبيع متجه جميع عناصره 1. عرّف${\displaystyle \lambda ={\sqrt {\max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}}}}$ولاحظ أن${\displaystyle \max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}=\lambda ^{2}\leq \lambda _{1}^{2}=d^{2}}$. لأن${\displaystyle A_{G}}$إذا كانت متناظرة، فيمكننا اختيار المتجهات الذاتية${\displaystyle v_{2},\ldots ,v_{n}}$ل${\displaystyle A_{G}}$المقابل للقيم الذاتية${\displaystyle \lambda _{2},\ldots ,\lambda _{n}}$لهذا السبب.${\displaystyle \{v_{1},\ldots ,v_{n}\}}$يشكل أساسًا متعامدًا لـ${\displaystyle \mathbf {R} ^{n}}$.

يترك${\displaystyle J}$كن${\displaystyle n\times n}$مصفوفة جميع عناصرها تساوي 1. لاحظ أن${\displaystyle v_{1}}$هو متجه ذاتي لـ${\displaystyle J}$مع القيمة الذاتية${\displaystyle n}$وبعضهم البعض${\displaystyle v_{i}}$، كونه عموديًا على${\displaystyle v_{1}=\mathbf {1} }$، هو متجه ذاتي لـ${\displaystyle J}$بقيمة ذاتية 0. لمجموعة فرعية من الرؤوس${\displaystyle U\subseteq V}$، يترك${\displaystyle 1_{U}}$ليكن متجه العمود مع${\displaystyle v^{\text{th}}}$الإحداثي يساوي 1 إذا${\displaystyle v\in U}$وصفر فيما عدا ذلك. ثم،

${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|=\left|1_{S}^{\operatorname {T} }\left(A_{G}-{\frac {d}{n}}J\right)1_{T}\right|}$.

يترك${\displaystyle M=A_{G}-{\frac {d}{n}}J}$. لأن${\displaystyle A_{G}}$و${\displaystyle J}$تتشارك المتجهات الذاتية، والقيم الذاتية لـ${\displaystyle M}$نكون${\displaystyle 0,\lambda _{2},\ldots ,\lambda _{n}}$باستخدام متباينة كوشي-شفارتز ، لدينا أن${\displaystyle |1_{S}^{\operatorname {T} }M1_{T}|=\langle 1_{S},M1_{T}\rangle \leq \|1_{S}\|\|M1_{T}\|}$علاوة على ذلك، لأن${\displaystyle M}$بما أن المصفوفة ذاتية الترافق، يمكننا كتابة

${\displaystyle \|M1_{T}\|^{2}=\langle M1_{T},M1_{T}\rangle =\langle 1_{T},M^{2}1_{T}\rangle =\left\langle 1_{T},\sum _{i=1}^{n}M^{2}\langle 1_{T},v_{i}\rangle v_{i}\right\rangle =\sum _{i=2}^{n}\lambda _{i}^{2}\langle 1_{T},v_{i}\rangle ^{2}\leq \lambda ^{2}\|1_{T}\|^{2}}$.

وهذا يعني أن${\displaystyle \|M1_{T}\|\leq \lambda \|1_{T}\|}$و${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \lambda \|1_{S}\|\|1_{T}\|=\lambda {\sqrt {|S||T|}}}$.

ولإظهار الحد الأكثر دقة أعلاه، سننظر بدلاً من ذلك في المتجهات${\displaystyle 1_{S}-{\frac {|S|}{n}}\mathbf {1} }$و${\displaystyle 1_{T}-{\frac {|T|}{n}}\mathbf {1} }$وكلاهما عمودي على${\displaystyle v_{1}}$يمكننا التوسع

${\displaystyle 1_{S}^{\operatorname {T} }A_{G}1_{T}=\left({\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left({\frac {|T|}{n}}\mathbf {1} \right)+\left(1_{S}-{\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left(1_{T}-{\frac {|T|}{n}}\mathbf {1} \right)}$

لأن الحدين الآخرين في المتسلسلة يساويان صفرًا. الحد الأول يساوي${\displaystyle {\frac {|S||T|}{n^{2}}}\mathbf {1} ^{\operatorname {T} }A_{G}\mathbf {1} ={\frac {d}{n}}|S||T|}$لذلك نجد أن

${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \left|\left(1_{S}-{\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left(1_{T}-{\frac {|T|}{n}}\mathbf {1} \right)\right|}$

يمكننا ربط الجانب الأيمن بواسطة${\displaystyle \lambda \left\|1_{S}-{\frac {|S|}{|n|}}\mathbf {1} \right\|\left\|1_{T}-{\frac {|T|}{|n|}}\mathbf {1} \right\|=\lambda {\sqrt {|S||T|\left(1-{\frac {|S|}{n}}\right)\left(1-{\frac {|T|}{n}}\right)}}}$باستخدام نفس الأساليب المستخدمة في البرهان السابق.