عدم المساواة لغروتينديك

بعض البيانات التاريخية حول أفضل الحدود الدنيا المعروفة لـ${\displaystyle K_{G}^{\mathbb {R} }(d)}$يلخص الجدول التالي ذلك.

د	غروتينديك، 1953 [ 3 ]	كريفين، 1979 [ 6 ]	ديفي، 1984 [ 8 ]	فيشبورن وآخرون، 1994 [ 15 ]	فيرتيسي، 2008 [ 16 ]	بريت وآخرون، 2011 [ 17 ]	هوا وآخرون، 2015 [ 18 ]	ديفيانسكي وآخرون، 2017 [ 19 ]	Designolle et al., 2023 [ 20 ]	Designolle et al., 2024 [ 21 ]	هيلمان، 2026 [ 9 ]	جونز ومالافولتا، 2026 [ 10 ]
2		${\displaystyle {\sqrt {2}}}$≈ 1.41421
3					1.41724		1.41758	1.4359	1.43665	1.43670
4					1.44521		1.44566	1.4821		1.48579
5				${\displaystyle {\frac {10}{7}}}$≈ 1.42857	1.46007		1.46112			1.49339
6							1.47017
7						1.46286	1.47583
8						1.47586	1.47972
9						1.48608
10						1.49431
∞	${\displaystyle {\frac {\pi }{2}}}$≈ 1.57079		1.67696								1.67696${\displaystyle +10^{-26}}$	1.67696${\displaystyle +10^{-12}}$

بعض البيانات التاريخية حول أفضل الحدود العليا المعروفة لـ${\displaystyle K_{G}^{\mathbb {R} }(d)}$:

د	غروتينديك، 1953 [ 3 ]	ريتز، 1974 [ 22 ]	كريفين، 1979 [ 6 ]	برافرمان وآخرون، 2011 [ 7 ]	هيرش وآخرون، 2016 [ 23 ]	Designolle et al., 2023 [ 20 ]	هيلمان، 2026 [ 12 ]	لي وآخرون، 2026 [ 11 ]
2			${\displaystyle {\sqrt {2}}}$≈ 1.41421
3			1.5163		1.4644	1.4546
4			${\displaystyle {\frac {\pi }{2}}}$≈ 1.5708
8			1.6641
∞	${\displaystyle \operatorname {sinh} {\frac {\pi }{2}}}$≈ 2.30130	2.261	${\displaystyle {\frac {\pi }{2\ln(1+{\sqrt {2}})}}}$≈ 1.78221	${\displaystyle {\frac {\pi }{2\ln(1+{\sqrt {2}})}}}$${\displaystyle -\varepsilon }$			${\displaystyle {\frac {\pi }{2\ln(1+{\sqrt {2}})}}}$${\displaystyle -10^{-5}}$	${\displaystyle {\frac {\pi }{2\ln(1+{\sqrt {2}})}}}$${\displaystyle -6.039\cdot 10^{-5}}$

بالنظر إلى${\displaystyle m\times n}$مصفوفة الإدراك${\displaystyle A=(a_{ij})}$، المعيار القطعي لـ${\displaystyle A}$يتم تعريفها بواسطة

${\displaystyle \|A\|_{\square }=\max _{S\subset [m],T\subset [n]}\left|\sum _{i\in S,j\in T}a_{ij}\right|.}$

يُعد مفهوم معيار القطع أساسيًا في تصميم خوارزميات تقريب فعّالة للرسوم البيانية والمصفوفات الكثيفة. وبشكل أعم، يمكن تعميم تعريف معيار القطع ليشمل الدوال المتناظرة القابلة للقياس.${\displaystyle W:[0,1]^{2}\to \mathbb {R} }$بحيث يكون معيار القطع لـ${\displaystyle W}$يتم تعريفها بواسطة

${\displaystyle \|W\|_{\square }=\sup _{S,T\subset [0,1]}\left|\int _{S\times T}W\right|.}$

يُعد هذا التعريف المعمم لمعيار القطع أمرًا بالغ الأهمية في دراسة فضاء الجرافونات ، ويمكن ربط التعريفين لمعيار القطع عبر مصفوفة التجاور للرسم البياني .

يتمثل أحد تطبيقات متباينة غروتينديك في تقديم خوارزمية فعالة لتقريب معيار القطع لمصفوفة حقيقية معطاة${\displaystyle A}$؛ على وجه التحديد، بالنظر إلى${\displaystyle m\times n}$المصفوفة الحقيقية، يمكن للمرء أن يجد عددًا${\displaystyle \alpha }$بحيث

${\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square },}$

أين${\displaystyle C}$هو ثابت مطلق. ^{[ 24 ]} تستخدم خوارزمية التقريب هذه البرمجة شبه المحددة .

نقدم هنا مخططًا موجزًا ​​لخوارزمية التقريب هذه. لنفترض${\displaystyle B=(b_{ij})}$يكون${\displaystyle (m+1)\times (n+1)}$المصفوفة المحددة بواسطة

${\displaystyle {\begin{pmatrix}a_{11}&a_{12}&\ldots &a_{1n}&-\sum _{k=1}^{n}a_{1k}\\a_{21}&a_{22}&\ldots &a_{2n}&-\sum _{k=1}^{n}a_{2k}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\ldots &a_{mn}&-\sum _{k=1}^{n}a_{mk}\\-\sum _{\ell =1}^{m}a_{\ell 1}&-\sum _{\ell =1}^{m}a_{\ell 2}&\ldots &-\sum _{\ell =1}^{m}a_{\ell n}&\sum _{k=1}^{n}\sum _{\ell =1}^{m}a_{\ell k}\end{pmatrix}}.}$

يمكن للمرء أن يتحقق من ذلك${\displaystyle \|A\|_{\square }=\|B\|_{\square }}$عن طريق الملاحظة، إذا${\displaystyle S\in [m+1],T\in [n+1]}$شكّل قيمة عظمى لمعيار القطع لـ${\displaystyle B}$، ثم

${\displaystyle S^{*}={\begin{cases}S,&{\text{if }}m+1\not \in S,\\{[m]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad T^{*}={\begin{cases}T,&{\text{if }}n+1\not \in T,\\{[n]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad }$

شكّل قيمة عظمى لمعيار القطع لـ${\displaystyle A}$بعد ذلك، يمكن التحقق من ذلك.${\displaystyle \|B\|_{\square }=\|B\|_{\infty \to 1}/4}$، أين

${\displaystyle \|B\|_{\infty \to 1}=\max \left\{\sum _{i=1}^{m+1}\sum _{j=1}^{n+1}b_{ij}\varepsilon _{i}\delta _{j}:\varepsilon _{1},\ldots ,\varepsilon _{m+1}\in \{-1,1\},\delta _{1},\ldots ,\delta _{n+1}\in \{-1,1\}\right\}.}$^{[ 25 ]}

على الرغم من عدم أهميتها في هذا البرهان،${\displaystyle \|B\|_{\infty \to 1}}$يمكن تفسير ذلك على أنه القاعدة لـ${\displaystyle B}$عند النظر إليها كمؤثر خطي من${\displaystyle \ell _{\infty }^{m}}$ل${\displaystyle \ell _{1}^{m}}$.

يكفي الآن تصميم خوارزمية فعالة لتقريب${\displaystyle \|A\|_{\infty \to 1}}$نعتبر البرنامج شبه المحدد التالي :

${\displaystyle {\text{SDP}}(A)=\max \left\{\sum _{i=1}^{m}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},y_{j}\right\rangle :x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}\in S^{n+m-1}\right\}.}$

ثم${\displaystyle {\text{SDP}}(A)\geq \|A\|_{\infty \to 1}}$تشير متباينة غروثديك إلى أن${\displaystyle {\text{SDP}}(A)\leq K_{G}^{\mathbb {R} }\|A\|_{\infty \to 1}}$من المعروف أن العديد من الخوارزميات (مثل طرق النقطة الداخلية ، وطرق الرتبة الأولى، وطريقة الحزمة، وطريقة لاغرانج المعززة ) تُخرج قيمة برنامج شبه محدد حتى خطأ إضافي ${\displaystyle \varepsilon }$في وقت يكون متعدد الحدود في حجم وصف البرنامج و${\displaystyle \log(1/\varepsilon )}$[ ^{26 ]} لذلك، يمكن للمرء أن ^يُخرج${\displaystyle \alpha ={\text{SDP}}(B)}$وهو ما يرضي

${\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square }\qquad {\text{with}}\qquad C=K_{G}^{\mathbb {R} }.}$

تُعدّ مبرهنة سيميريدي للانتظام أداةً مفيدةً في نظرية المخططات، إذ تنص (بصورة غير رسمية) على إمكانية تقسيم أي مخطط إلى عدد مُحدد من الأجزاء التي تتفاعل فيما بينها بطريقة شبه عشوائية . ومن التطبيقات الأخرى لمتباينة غروتينديك إنتاج تقسيم لمجموعة الرؤوس يُحقق نتيجة مبرهنة سيميريدي للانتظام ، وذلك باستخدام خوارزمية تقدير معيار القطع، في زمن متعدد الحدود بالنسبة للحد الأعلى لحجم التقسيم المنتظم لسيزميريدي، ولكنه مستقل عن عدد رؤوس المخطط. ^{[ 25 ]}

اتضح أن "العائق الرئيسي" في بناء تجزئة سيميريدي المنتظمة في وقت متعدد الحدود هو تحديد ما إذا كان زوج معين من الأزواج في وقت متعدد الحدود أم لا${\displaystyle (X,Y)}$يقترب من أن يكون${\displaystyle \varepsilon }$-منتظم ، بمعنى أنه بالنسبة للجميع${\displaystyle S\subset X,T\subset Y}$مع${\displaystyle |S|\geq \varepsilon |X|,|T|\geq \varepsilon |Y|}$لدينا

${\displaystyle \left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\leq \varepsilon ,}$

أين${\displaystyle e(X',Y')=|\{(u,v)\in X'\times Y':uv\in E\}|}$للجميع${\displaystyle X',Y'\subset V}$و${\displaystyle V,E}$تمثل مجموعتا الرؤوس والحواف في الرسم البياني، على التوالي. ولتحقيق ذلك، نقوم بإنشاء${\displaystyle n\times n}$مصفوفة${\displaystyle A=(a_{xy})_{(x,y)\in X\times Y}}$، أين${\displaystyle n=|V|}$، كما هو محدد بواسطة

${\displaystyle a_{xy}={\begin{cases}1-{\frac {e(X,Y)}{|X||Y|}},&{\text{if }}xy\in E,\\-{\frac {e(X,Y)}{|X||Y|}},&{\text{otherwise}}.\end{cases}}}$

ثم للجميع${\displaystyle S\subset X,T\subset Y}$،

${\displaystyle \left|\sum _{x\in S,y\in T}a_{xy}\right|=|S||T|\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|.}$

وبالتالي، إذا${\displaystyle (X,Y)}$ليس${\displaystyle \varepsilon }$-منتظم، إذن${\displaystyle \|A\|_{\square }\geq \varepsilon ^{3}n^{2}}$وبناءً على ذلك، باستخدام خوارزمية تقريب معيار القطع مع تقنية التقريب، يمكن إيجاد الحل في وقت متعدد الحدود.${\displaystyle S\subset X,T\subset Y}$بحيث

${\displaystyle \min \left\{n|S|,n|T|,n^{2}\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\right\}\geq \left|\sum _{x\in S,y\in T}a_{xy}\right|\geq {\frac {1}{K_{G}^{\mathbb {R} }}}\varepsilon ^{3}n^{2}\geq {\frac {1}{2}}\varepsilon ^{3}n^{2}.}$

ثم تأتي خوارزمية إنتاج تقسيم Szemerédi المنتظم من الحجة البنائية لـ Alon et al. ^{[ 27 ]}

تنص متباينة غروتينديك للرسم البياني على أنه لكل${\displaystyle n\in \mathbb {N} }$ولكل رسم بياني${\displaystyle G=(\{1,\ldots ,n\},E)}$بدون حلقات ذاتية، يوجد ثابت عالمي${\displaystyle K>0}$بحيث يكون كل${\displaystyle n\times n}$مصفوفة${\displaystyle A=(a_{ij})}$يفي بذلك

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{ij\in E}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq K\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{ij\in E}a_{ij}\varepsilon _{i}\varepsilon _{j}.}$^{[ 28 ]}

ثابت غروتينديك للرسم البياني${\displaystyle G}$، المشار إليه${\displaystyle K(G)}$، ويُعرَّف بأنه أصغر ثابت${\displaystyle K}$الذي يحقق الخاصية المذكورة أعلاه.

تُعدّ متباينة غروتينديك للرسم البياني امتدادًا لمتباينة غروتينديك، لأن المتباينة الأولى هي حالة خاصة من المتباينة الثانية عندما${\displaystyle G}$هو رسم بياني ثنائي الأجزاء يحتوي على نسختين من${\displaystyle \{1,\ldots ,n\}}$باعتبارها فئات التقسيم الثنائي. وهكذا،

${\displaystyle K_{G}=\sup _{n\in \mathbb {N} }\{K(G):G{\text{ is an }}n{\text{-vertex bipartite graph}}\}.}$

ل${\displaystyle G=K_{n}}$، ال${\displaystyle n}$الرسم البياني الكامل ذو الرؤوس n ، متباينة غروتينديك لـ${\displaystyle G}$يصبح

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq K(K_{n})\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\varepsilon _{i}\varepsilon _{j}.}$

اتضح أن${\displaystyle K(K_{n})\asymp \log n}$من جهة، لدينا${\displaystyle K(K_{n})\lesssim \log n}$[ ^{29 ] [ 30 ] [ 31 ] في الواقع ،} المتباينة التالية صحيحة لأي${\displaystyle n\times n}$مصفوفة${\displaystyle A=(a_{ij})}$وهذا يعني أن${\displaystyle K(K_{n})\lesssim \log n}$بواسطة متباينة كوشي-شفارتز : ^{[ 28 ]}

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \log \left({\frac {\sum _{i\in \{1,\ldots ,n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}|a_{ij}|}{\sqrt {\sum _{i\in \{1,\ldots ,n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}a_{ij}^{2}}}}\right)\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\varepsilon _{1}\varepsilon _{n}.}$

من ناحية أخرى، الحد الأدنى المطابق${\displaystyle K(K_{n})\gtrsim \log n}$ويرجع ذلك إلى ألون وماكاريتشيف وماكاريتشيف وناعور في عام 2006. ^{[ 28 ]}

عدم المساواة غروتينديك${\displaystyle K(G)}$رسم بياني${\displaystyle G}$يعتمد ذلك على بنية${\displaystyle G}$من المعروف أن

${\displaystyle \log \omega \lesssim K(G)\lesssim \log \vartheta ,}$^{[ 28 ]}

و

${\displaystyle K(G)\leq {\frac {\pi }{2\log \left({\frac {1+{\sqrt {(\vartheta -1)^{2}+1}}}{\vartheta -1}}\right)}},}$^{[ 32 ]}

أين${\displaystyle \omega }$هو رقم الزمرة لـ${\displaystyle G}$أي الأكبر${\displaystyle k\in \{2,\ldots ,n\}}$بحيث يوجد${\displaystyle S\subset \{1,\ldots ,n\}}$مع${\displaystyle |S|=k}$بحيث${\displaystyle ij\in E}$لجميع المتميزين${\displaystyle i,j\in S}$، و

${\displaystyle \vartheta =\min \left\{\max _{i\in \{1,\ldots ,n\}}{\frac {1}{\langle x_{i},y\rangle }}:x_{1},\ldots ,x_{n},y\in S^{n},\left\langle x_{i},x_{j}\right\rangle =0\;\forall ij\in E\right\}.}$

المعلمة${\displaystyle \vartheta }$تُعرف باسم دالة لوفاس ثيتا لمكمل${\displaystyle G}$[ ^{33 ] [ 34 ] [ 28 ]​}

في تطبيق متباينة غروتينديك لتقريب معيار القطع، رأينا أن متباينة غروتينديك تجيب على السؤال التالي: ما مدى جودة الحل الأمثل للبرنامج شبه المحدد؟${\displaystyle {\text{SDP}}(A)}$تقريبي${\displaystyle \|A\|_{\infty \to 1}}$، والتي يمكن اعتبارها مسألة تحسين على المكعب الواحدي؟ وبشكل أعم، يمكننا طرح أسئلة مماثلة على الأجسام المحدبة الأخرى غير المكعب الواحدي.

على سبيل المثال، تعود المتباينة التالية إلى ناور وشيختمان، وبشكل مستقل إلى غورو سوامي وآخرون: ^{[ 35 ]} لكل${\displaystyle n\times n}$مصفوفة${\displaystyle A=(a_{ij})}$وكل${\displaystyle p\geq 2}$،

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in \mathbb {R} ^{n},\sum _{k=1}^{n}\|x_{k}\|_{2}^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \gamma _{p}^{2}\max _{t_{1},\ldots ,t_{n}\in \mathbb {R} ,\sum _{k=1}^{n}|t_{k}|^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}t_{i}t_{j},}$

أين

${\displaystyle \gamma _{p}={\sqrt {2}}\left({\frac {\Gamma ((p+1)/2)}{\sqrt {\pi }}}\right)^{1/p}.}$

الثابت${\displaystyle \gamma _{p}^{2}}$تكون حادة في المتباينة. تشير صيغة ستيرلينغ إلى أن${\displaystyle \gamma _{p}^{2}=p/e+O(1)}$مثل${\displaystyle p\to \infty }$.