On graphs decomposable into induced matchings of linear sizes
On graphs decomposable into induced matchings of linear sizes
复制标题
关于可分解为线性大小的诱导匹配的图
DOI：
10.1112/blms.12005
复制
发表时间：
2015
影响因子：
0.9
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
J. Fox;Hao;B. Sudakov
我们将图形g an（r，t）-ruzsa –szemerédi绘制图形，如果可以将其边缘集划分为t边缘 - 偶发性诱导的匹配，则每个大小为r。在本文中，我们考虑r = cn的情况，我们确定最大的t，这是一个仅根据c而定的。 as ω（logn）诱导的匹配。我们证明，当C固定在1/5和1/4之间（n/logn）。
We call a graph G an (r,t) ‐Ruzsa–Szemerédi graph if its edge set can be partitioned into t edge‐disjoint induced matchings, each of size r . These graphs were introduced in 1978 and have been extensively studied since then. In this paper, we consider the case when r=cn . For c>1/4 , we determine the maximum possible t , which is a constant depending only on c . On the other hand, when c=1/4 , there could be as many as Ω(logn) induced matchings. We prove that this bound is tight up to a constant factor. Finally, when c is fixed strictly between 1/5 and 1/4 , we give a short proof that the number t of induced matchings is O(n/logn) . We are also able to further improve the upper bound to o(n/logn) for fixed c>1/4−b for some positive constant b .