Lovász, Vectors, Graphs and Codes

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

4 Scopus citations

Abstract

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
Pages1-16
Number of pages16
ISBN (Print)9783662592038
DOIs
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
Volume28
ISSN (Print)1217-4696

Conference

ConferenceMathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018
Country/TerritoryHungary
CityBudapest
Period7/2/187/6/18

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

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

Fingerprint

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

Cite this