Item request has been placed!
×
Item request cannot be made.
×
Processing Request
A Wowzer-type lower bound for the strong regularity lemma
Item request has been placed!
×
Item request cannot be made.
×
Processing Request
- المؤلفون: Kalyanasundaram, Subrahmanyam; Shapira, A
- نوع التسجيلة:
Electronic Resource
- الدخول الالكتروني :
http://raiith.iith.ac.in/48/
https://doi.org/10.1112/plms/pds045
http://raiith.iith.ac.in/48
https://doi.org/10.1112/plms/pds045
doi:10.1112/plms/pds045
- معلومة اضافية
- Publisher Information:
Oxford University Press (OUP) 2013
- نبذة مختصرة :
he regularity lemma of Szemerédi asserts that one can partition every graph into a bounded number of quasi-random bipartite graphs. In some applications however, one would like to have a strong control on how quasi-random these bipartite graphs are. Alon et al. (‘Efficient testing of large graphs’, Combinatorica 20 (2000) 451–476) obtained a powerful variant of the regularity lemma, which allows one to have an arbitrary control on this measure of quasi-randomness. However, their proof guaranteed only to produce a partition where the number of parts is given by the Wowzer function, which is the iterated version of the Tower function. We show here that a bound of this type is unavoidable by constructing a graph H, with the property that even if one wants a very mild control on the quasi-randomness of a regular partition, then the number of parts in any such partition of H must be given by a Wowzer-type function.
- الموضوع:
- Other Numbers:
INTHY oai:raiith.iith.ac.in:48
Kalyanasundaram, Subrahmanyam and Shapira, A (2013) A Wowzer-type lower bound for the strong regularity lemma. Proceedings of the London Mathematical Society, 106 (3). pp. 621-649. ISSN 0024-6115
990174739
- Contributing Source:
INDIAN INST OF TECHNOL HYDERABAD
From OAIster®, provided by the OCLC Cooperative.
- الرقم المعرف:
edsoai.ocn990174739
HoldingsOnline
No Comments.