DOI: https://doi.org/10.1007/s00208-026-03355-2
PMID: https://pubmed.ncbi.nlm.nih.gov/41727700
تاريخ النشر: 2026-02-18
المؤلف: Zhenyun Du وآخرون
الموضوع الرئيسي: الحدود والهياكل في نظرية الرسوم البيانية
نظرة عامة
في هذا القسم، يوضح المؤلفون أن المصفوفات البوليانية ذات $\gamma_2$-norm المحدود أو ذات معيار الأثر الطبيعي المحدود تحتوي بالضرورة على مصفوفة فرعية بحجم خطي تتكون إما بالكامل من الواحدات أو الأصفار. تؤكد هذه النتيجة فرضية طرحها هامباردزميان، حاتمي، وحاتمي. بالإضافة إلى ذلك، يقدم المؤلفون رؤى هيكلية إضافية حول المصفوفات البوليانية ذات $\gamma_2$-norm المحدود ويستكشفون آثارها عبر مجالات متنوعة، بما في ذلك تعقيد الاتصال، نظرية المشغل، نظرية الرسوم الطيفية، والتركيبات القصوى.
تطبيق مهم لنتائجهم هو نظرية عكسية لمشكلة MaxCut. يشيرون إلى نتيجة معروفة من قبل إدواردز، التي تنص على أن أي رسم بياني $G$ يحتوي على $m$ حافة له قطع بحجم لا يقل عن $\frac{m}{2} + \frac{\sqrt{8m + 1} – 1}{8}$، محققًا المساواة للرسوم البيانية الكاملة ذات عدد فردي من الرؤوس. بالمقابل، يثبت المؤلفون أنه إذا كانت MaxCut لـ $G$ لا تتجاوز $\frac{m}{2} + O(\sqrt{m})$، فإن $G$ يجب أن تحتوي على مجموعة من الحجم $\Theta(\sqrt{m})$.
مقدمة
في هذا القسم، يقدم المؤلفون معيار التحليل $\gamma_2(M)$ لمصفوفة $m \times n$ $M$، المعرفة بأنها الحد الأدنى من $U$ و $V$ بحيث $M = UV$، حيث تمثل $U_{\text{row}}$ و $V_{\text{col}}$ أقصى معايير $\ell_2$ للصفوف من $U$ والأعمدة من $V$، على التوالي. يعمل هذا المعيار كبديل “ناعم” لرتبة المصفوفة، مما يعكس تشويه عمل المصفوفة على متجه عند تحليلها عبر فضاء $\ell_2$. تستكشف الورقة الآثار الهيكلية لمعيار $\gamma_2$، خاصة فيما يتعلق بتعقيد الاتصال والخصائص التركيبية.
تؤكد النتيجة الرئيسية للورقة فرضية من هامباردزميان، حاتمي، وحاتمي بشأن المصفوفات البوليانية ذات $\gamma_2$-norm المحدود. على وجه التحديد، يوضح المؤلفون أنه إذا كانت مصفوفة بوليانية $M$ تحقق $\gamma_2(M) \leq \gamma$، فإنه يجب أن تحتوي على مصفوفة فرعية بحجم $\delta_1 m \times \delta_2 n$ تتكون بالكامل من إما الأصفار أو الواحدات، حيث $\delta_1, \delta_2 \geq 2^{-O(\gamma^3)}$. بالإضافة إلى ذلك، يوسع المؤلفون نتائجهم إلى فرضية أقوى تتعلق بمعايير الأثر الطبيعي المحدودة، موضحين أن نتائجهم توفر نتيجة بسيطة لنظرية الرئيسية.
نقاش
في هذا القسم، يناقش المؤلفون عدة نتائج فرعية ونظريات تتعلق بخصائص المصفوفات البوليانية والعددية، مع التركيز بشكل خاص على معيار $\gamma_2$ وآثاره على هياكل المصفوفات الفرعية. تؤكد النتيجة الفرعية 1.2 أن مصفوفة بوليانية $m \times n$ $M$ مع $\text{tr}(M) \sqrt{mn} \leq \gamma$ تحتوي على مصفوفة فرعية بحجم $\delta_1 m \times \delta_2 n$ تتكون إما من الأصفار بالكامل أو الواحدات بالكامل، حيث $\delta_1, \delta_2 \geq 2^{-O(\gamma^3)}$. النتيجة الفرعية 1.3 توسع هذه النتيجة إلى المصفوفات العددية، مشيرة إلى أنه إذا كانت $\gamma_2(M) \leq \gamma$، فإن مصفوفة فرعية ثابتة من حجم مشابه موجودة، مع $\delta_1, \delta_2 \geq 2^{-\gamma O(\gamma)}$. كما يؤكد المؤلفون أن الحدود المقدمة من النظرية 1.1 قريبة من المثالية.
تتناول النظريتان 1.4 و 1.5 هيكل المصفوفات البوليانية، كاشفة أن مصفوفة بوليانية خالية من الدورات الرباعية مع انحراف $d$ لها معيار $\gamma_2$ يساوي $\sqrt{d}$. هذه النتيجة مهمة لأنها تربط معيار $\gamma_2$ بالمعلمات التركيبية، مما يسهل فهم وجود المصفوفات الفرعية فيما يتعلق بانحراف المصفوفة. تستكشف النظريتان 1.6 و 1.7 المزيد من آثار هذه النتائج في سياق مشاكل MaxCut في الرسوم البيانية، موضحة علاقة بين حجم القطوع ووجود المجموعات في الرسوم البيانية ذات كثافات الحواف المحدودة. بشكل عام، يبرز هذا القسم التفاعل بين معايير المصفوفات، الخصائص الهيكلية، وتطبيقاتها في مجالات متنوعة من الرياضيات وعلوم الكمبيوتر، بما في ذلك تعقيد الاتصال ونظرية التباين.
DOI: https://doi.org/10.1007/s00208-026-03355-2
PMID: https://pubmed.ncbi.nlm.nih.gov/41727700
Publication Date: 2026-02-18
Author(s): Zhenyun Du et al.
Primary Topic: Limits and Structures in Graph Theory
Overview
In this section, the authors demonstrate that Boolean matrices with a bounded $\gamma_2$-norm or a bounded normalized trace norm necessarily contain a submatrix of linear size that is either entirely composed of ones or zeros. This finding confirms a conjecture posited by Hambardzumyan, Hatami, and Hatami. Additionally, the authors provide further structural insights into Boolean matrices with bounded $\gamma_2$-norm and explore their implications across various fields, including communication complexity, operator theory, spectral graph theory, and extremal combinatorics.
A significant application of their results is an inverse theorem for the MaxCut problem. They reference a well-known result by Edwards, which states that any graph $G$ with $m$ edges has a cut of size at least $\frac{m}{2} + \frac{\sqrt{8m + 1} – 1}{8}$, achieving equality for complete graphs with an odd number of vertices. In contrast, the authors establish that if the MaxCut of $G$ is at most $\frac{m}{2} + O(\sqrt{m})$, then $G$ must contain a clique of size $\Theta(\sqrt{m})$.
Introduction
In this section, the authors introduce the factorization norm $\gamma_2(M)$ for an $m \times n$ matrix $M$, defined as the minimum of $U$ and $V$ such that $M = UV$, where $U_{\text{row}}$ and $V_{\text{col}}$ represent the maximum $\ell_2$-norms of the rows of $U$ and the columns of $V$, respectively. This norm serves as a “smooth” analogue to matrix rank, reflecting the distortion of a matrix’s action on a vector when factored through $\ell_2$ space. The paper explores the structural implications of the $\gamma_2$-norm, particularly in relation to communication complexity and combinatorial properties.
The main result of the paper confirms a conjecture by Hambardzumyan, Hatami, and Hatami regarding Boolean matrices with bounded $\gamma_2$-norm. Specifically, the authors demonstrate that if a Boolean matrix $M$ satisfies $\gamma_2(M) \leq \gamma$, then it must contain a submatrix of size $\delta_1 m \times \delta_2 n$ that is entirely composed of either zeros or ones, where $\delta_1, \delta_2 \geq 2^{-O(\gamma^3)}$. Additionally, the authors extend their findings to a stronger conjecture involving bounded normalized trace norms, showing that their results provide a straightforward corollary to the main theorem.
Discussion
In this section, the authors discuss several corollaries and theorems related to the properties of Boolean and integer matrices, particularly focusing on the $\gamma_2$-norm and its implications for submatrix structures. Corollary 1.2 establishes that an $m \times n$ Boolean matrix $M$ with $\text{tr}(M) \sqrt{mn} \leq \gamma$ contains a submatrix of size $\delta_1 m \times \delta_2 n$ that is either all-zeros or all-ones, where $\delta_1, \delta_2 \geq 2^{-O(\gamma^3)}$. Corollary 1.3 extends this result to integer matrices, indicating that if $\gamma_2(M) \leq \gamma$, then a constant submatrix of similar size exists, with $\delta_1, \delta_2 \geq 2^{-\gamma O(\gamma)}$. The authors also assert that the bounds provided by Theorem 1.1 are close to optimal.
Theorems 1.4 and 1.5 delve into the structure of Boolean matrices, revealing that a four cycle-free Boolean matrix with degeneracy $d$ has a $\gamma_2$-norm equal to $\sqrt{d}$. This finding is significant as it connects the $\gamma_2$-norm to combinatorial parameters, facilitating the understanding of submatrix existence in relation to the degeneracy of the matrix. Theorems 1.6 and 1.7 further explore the implications of these findings in the context of MaxCut problems in graphs, establishing a relationship between the size of cuts and the presence of cliques in graphs with bounded edge densities. Overall, this section emphasizes the interplay between matrix norms, structural properties, and their applications in various areas of mathematics and computer science, including communication complexity and discrepancy theory.