Ordered graphs and large bi-cliques in intersection graphs of curves
Ordered graphs and large bi-cliques in intersection graphs of curves
复制标题
曲线交图中的有序图和大双团
DOI：
10.1016/j.ejc.2019.07.005
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
István Tomon
中科院分区：
文献类型：
--
作者：
J. Pach;István Tomon
有序图G<是顶点集上全有序<的图。长度为k−1的单调路径是一个顶点v 1< v 2<…< v k的序列，使得v i v j是G<的当且仅当| j−i|= 1的边。一个大小为m的双团是顶点类大小为m的完全二部图。我们证明了对于每一个正整数k，存在一个常数c k> 0，使得每一个有n个顶点的有序图，如果不包含长度为k的单调路径作为诱导子图，其顶点的度数至少为c k n，或它的补至少有一个大小为ck n / log n的双团。对于不包含与固定有序匹配同构的诱导有序子图的有序图，也有类似的结果。因此，我们给出了Fox和Pach定理的一个简短的组合证明。存在一个常数c> 0，使得平面上任意n条x单调曲线的集合的相交图G有一个大小至少为cn∕log n的双团，或者它的补包含一个大小至少为cn的双团（如果一条曲线的每条垂直线与它相交最多有一点，则称它为x单调曲线）。我们也证明了如果G对于某个λ > 0有最多14−λ 2条边，那么G¯包含一个线性大小的双团。我们证明，如果用更大的常数代替14，这个说法就不成立了。
An ordered graph G< is a graph with a total ordering< on its vertex set. A monotone path of length k− 1 is a sequence of vertices v 1< v 2<…< v k such that v i v j is an edge of G< if and only if| j− i|= 1. A bi-clique of size m is a complete bipartite graph whose vertex classes are of size m. We prove that for every positive integer k, there exists a constant c k> 0 such that every ordered graph on n vertices that does not contain a monotone path of length k as an induced subgraph has a vertex of degree at least c k n, or its complement has a bi-clique of size at least c k n∕ log n. A similar result holds for ordered graphs containing no induced ordered subgraph isomorphic to a fixed ordered matching. As a consequence, we give a short combinatorial proof of the following theorem of Fox and Pach. There exists a constant c> 0 such the intersection graph G of any collection of n x-monotone curves in the plane has a bi-clique of size at least c n∕ log n or its complement contains a bi-clique of size at least c n.(A curve is called x-monotone if every vertical line intersects it in at most one point.) We also prove that if G has at most 1 4− ϵ n 2 edges for some ϵ> 0, then G¯ contains a linear sized bi-clique. We show that this statement does not remain true if we replace 1 4 by any larger constants.