分因数规范和MaxCut的反向定理
Igor Balla1, Lianna Hambardzumyan2, István Tomon3
1Faculty of Mathematics and Computer Science, Leipzig University, 04109 Leipzig, Germany.
Mathematische annalen
|February 23, 2026
概括
有边界的gamma_2-norm或规范化微量规范的布尔矩阵包含大型全为1的/全为0的子矩阵. 这验证了一个猜想,并给出了MaxCut的逆定理,显示近最大切割的图形必须包含大群.
科学领域:
- 组合学是一种组合学.
- 线性代数 线性代数
- 图形理论 图形理论
背景情况:
- 布尔矩阵在离散数学和计算机科学中是基本的.
- 玛2规范和规范化微量规范是矩阵性质的关键指标.
- 该MaxCut问题寻求分割图的顶点,以最大限度地削减边缘.
研究的目的:
- 证明具有边界gamma_2-norm或规范化微量规范的布尔矩阵包含线性大小的全为1或全为0的子矩阵.
- 为了验证Hambardzumyan,Hatami和Hatami的猜测.
- 为MaxCut问题建立一个反向定理.
主要方法:
- 使用光谱图理论和极端组合学.
- 开发布尔矩阵的结构结果.
- 将矩阵规范属性应用于图形切割问题.
主要成果:
- 有边界的gamma_2-norm或规范化微量规范的布尔矩阵必然包含一个线性大小的全为1的或全为0的子矩阵.
- 建立了MaxCut的逆定理:图形的MaxCut最多为m/2 + O (((sqrt ((m)) 必须包含一个Omega (((sqrt ((m)) 的小组.
- 这项研究为布尔矩阵及其应用提供了进一步的结构见解.
结论:
- 这些发现证实了布尔矩阵理论中的一个重要的猜测.
- 对MaxCut的逆定理为具有特定切割属性的图形结构提供了新的视角.
- 这项研究将线性代数,组合学和理论计算机科学的概念结合起来.
相关概念视频
01:30Fundamental Theorem of Algebra
324
The Fundamental Theorem of Algebra is central to the study of polynomial equations, asserting that every non-constant polynomial with complex coefficients has at least one complex zero. This means that a polynomial of degree n ≥ 1, written as: with an ≠ 0, has at least one solution in the complex number system. Since the set of real numbers is a subset of complex numbers, this theorem applies equally to polynomials with real coefficients.Building on this result, the...
324
01:14Extraction: Partition and Distribution Coefficients
5.2K
The distribution law or Nernst's distribution law is the law that governs the distribution of a solute between two immiscible solvents. This law, also known as the partition law, states that if a solute is added to the mixture of two immiscible solvents at a constant temperature, the solute is distributed between the two solvents in such a way that the ratio of solute concentrations in the solvents remains constant at equilibrium.
For extracting a solute from an aqueous phase into an...
For extracting a solute from an aqueous phase into an...
5.2K
01:28Partial Fractions
256
A partial fraction is a component of a rational expression represented as the sum of simpler fractions. When a rational function is expressed as a ratio of two polynomials, it can often be decomposed into a sum of fractions whose denominators are simpler polynomials, typically linear or irreducible quadratic factors. This process is called partial fraction decomposition, and it is used to simplify complex expressions for integration, solving equations, or analysis.Partial fraction decomposition...
256
01:27Real Zeros of Polynomials
219
Polynomials are algebraic expressions of terms with variables raised to non-negative integer powers. A central aspect of analyzing polynomial functions is determining their real zeros—values of the variable for which the polynomial evaluates to zero. These values represent the x-intercepts of the polynomial’s graph.The Rational Zeros Theorem lists possible rational solutions for a polynomial equation with integer coefficients. If f(x)=anxn+....+a0, then every rational zero is...
219
01:29Complex Zeros
317
Complex zeros are the solutions to polynomial equations that include imaginary numbers, specifically, numbers of the form a + bi, where a and b are real numbers and i is the imaginary unit defined by i2=-1. These zeros satisfy the equation P(x) = 0, where P(x) is a polynomial with real or complex coefficients. Since the complex number system includes all real numbers, it provides a complete framework for analyzing all possible roots of a polynomial.Every polynomial of degree n≥1 can be...
317
01:12Theorems of Pappus and Guldinus: Problem Solving
1.1K
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
1.1K