Graph coloring and semidefinite rank
Graph coloring and semidefinite rank
复制标题
图着色和半定秩
DOI：
10.1007/978-3-031-06901-7_29
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Williamson, David P.
中科院分区：
文献类型：
--
作者：
Mirka, Renee;Smedira, Devin;Williamson, David P.
本文考虑半定规划，矩阵秩，图着色之间的相互作用。Karger等人（J ACM 45（2）：246-265，1998）给出了一个向量程序，其中图的着色可以被编码为低秩的半定矩阵。利用半定规划的互补松弛性条件，若最优对偶解的秩较高，则最优原解的秩一定较低。我们试图刻画图形，我们可以证明，相应的对偶最优解必须有足够高的秩的原始解决方案编码的着色。在原Karger，Motwani，和苏丹向量程序的情况下，我们表明，任何图是ak-树有足够高的对偶秩，我们可以提取相应的低秩原始解决方案的着色。我们还可以证明，如果一个图不是唯一可着色的，那么就不存在足够高秩的对偶最优解。这使我们能够完全刻画平面图的对偶最优解具有足够高的对偶秩，因为它是已知的，唯一可着色的平面图正是平面3-树。然后，我们修改的半定规划有一个目标函数的成本，并探讨当我们可以创建一个目标函数，使最佳的对偶解决方案具有足够高的排名。我们表明，它总是可以构造这样一个目标函数给定的图着色。目标函数的构造给出了4-着色平面图的算法。我们列举了所有诱导顶点数不超过14个的极大平面图，并成功地找到了其中99.75%的图的4-着色。我们的研究动机是试图使用半定规划来证明四色定理，该定理指出每个平面图都可以用四种颜色着色。Karger-Motwani-Sudan半定程序与Colin de Verdière图不变量有一个有趣的联系（J Combin. Theory Ser B 50：11-21，1990）（以及Colin de Verdière的一个相应猜想），其中在图是某种类型的情况下，与半定规划的对偶可行矩阵有一些相似性的矩阵必须具有高秩;例如，平面图的秩意味着半定规划的原始解编码为4-着色。
This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger et al. (J ACM 45(2):246–265, 1998) give a vector program in which a coloring of a graph can be encoded as a semidefinite matrix of low rank. By complementary slackness conditions of semidefinite programming, if an optimal dual solution has high rank, any optimal primal solution must have low rank. We attempt to characterize graphs for which we can show that the corresponding dual optimal solution must have rank high enough that the primal solution encodes a coloring. In the case of the original Karger, Motwani, and Sudan vector program, we show that any graph which is ak-tree has sufficiently high dual rank, and we can extract the coloring from the corresponding low-rank primal solution. We can also show that if a graph is not uniquely colorable, then no sufficiently high rank dual optimal solution can exist. This allows us to completely characterize the planar graphs for which dual optimal solutions have sufficiently high dual rank, since it is known that the uniquely colorable planar graphs are precisely the planar 3-trees. We then modify the semidefinite program to have an objective function with costs, and explore when we can create an objective function such that the optimal dual solution has sufficiently high rank. We show that it is always possible to construct such an objective function given the graph coloring. The construction of the objective function gives rise to heuristics for 4-coloring planar graphs. We enumerated all maximal planar graphs with an inducedof up to 14 vertices; the heuristics successfully found a 4-coloring for 99.75% of them. Our research was motivated by trying to use semidefinite programming to prove the four-color theorem, which states that every planar graph can be colored with four colors. There is an intriguing connection of the Karger–Motwani–Sudan semidefinite program with the Colin de Verdière graph invariant (J Combin. Theory Ser B 50:11-21, 1990) (and a corresponding conjecture of Colin de Verdière), in which matrices that have some similarities to the dual feasible matrices of the semidefinite program must have high rank in the case that graphs are of a certain type; for instance, planar graphs have rank that would imply that the primal solution of the semidefinite program encodes a 4-coloring.
肯普对四色定理第二部分的证明有多错误？
DOI：
--
发表时间：
2009
期刊：
影响因子：
--
作者：
G. Ellen;Bopanna Kallichanda;Alexander S. Mentis;Sarah Braudrick;S. Chawla;Andrew Clune;Rachel Drummond;Panagiota Evans;William Roche;Nao Takano
通讯作者：
Nao Takano