Premium
On graphs decomposable into induced matchings of linear sizes
Author(s) -
Fox Jacob,
Huang Hao,
Sudakov Benny
Publication year - 2017
Publication title -
bulletin of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 2.396
H-Index - 48
eISSN - 1469-2120
pISSN - 0024-6093
DOI - 10.1112/blms.12005
Subject(s) - combinatorics , mathematics , disjoint sets , upper and lower bounds , constant (computer programming) , graph , enhanced data rates for gsm evolution , binary logarithm , discrete mathematics , mathematical analysis , telecommunications , computer science , programming language
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 = c n . 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 Ω ( log n ) 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 / log n ) . We are also able to further improve the upper bound to o ( n / log n ) for fixed c > 1 / 4 − b for some positive constant b .