Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not necessarily an induced subgraph if G is not bipartite). Alice gets a set A of vertices, and Bob gets a disjoint set B of vertices such that |A|+|B|>K. The goal is to find a nonedge of G between A and B. We show that O(log n) bits of communication are enough for every n-vertex graph.
展开▼
机译：出于与最大Biclique问题的切割平面样张的长度的关系的缘故，在这里我们考虑在给定图形G上的以下交流游戏，双方都是已知的。令K为G的完整二部图的最大顶点数（如果G不是二部图，则不一定是诱导子图）。爱丽丝得到一组顶点A，鲍勃得到一组不相交的顶点B，使得| A | + | B |> K。目的是在A和B之间找到G的无边界。我们证明，对于每个n顶点图，通信的O（ log n）位就足够了。
展开▼
