Lovász, Vectors, Graphs and Codes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


A family of high-degree triangle-free pseudo-random Cayley graphs has been constructed in (Alon, Electro J Combin 1(R12):8, 1994 [2]), motivated by a geometric question of Lovász. These graphs turned out to be useful in tackling a variety of additional extremal problems in Graph Theory and Coding Theory. Here we describe the graphs and their applications, and mention several intriguing related open problems. This is mainly a survey, but it contains several new results as well. One of these is a construction showing that the Lovász (formula presented)-function of a graph cannot be bounded by any function of its Shannon capacity.

Original languageEnglish (US)
Title of host publicationBuilding Bridges II - Mathematics of László Lovász
EditorsImre Bárány, Gyula O. Katona, Attila Sali
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages16
ISBN (Print)9783662592038
StatePublished - 2019
EventMathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018 - Budapest, Hungary
Duration: Jul 2 2018Jul 6 2018

Publication series

NameBolyai Society Mathematical Studies
ISSN (Print)1217-4696


ConferenceMathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Applied Mathematics


  • Cayley graphs
  • List decodable codes
  • Maxcut
  • Ramsey graphs
  • Shannon capacity of graphs
  • The -function


Dive into the research topics of 'Lovász, Vectors, Graphs and Codes'. Together they form a unique fingerprint.

Cite this