Lovász, Vectors, Graphs and Codes

Noga Alon

doi:10.1007/978-3-662-59204-5_1

Lovász, Vectors, Graphs and Codes

Noga Alon

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 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 language	English (US)
Title of host publication	Building Bridges II - Mathematics of László Lovász
Editors	Imre Bárány, Gyula O. Katona, Attila Sali
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	1-16
Number of pages	16
ISBN (Print)	9783662592038
DOIs	https://doi.org/10.1007/978-3-662-59204-5_1
State	Published - 2019
Event	Mathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018 - Budapest, Hungary Duration: Jul 2 2018 → Jul 6 2018

Publication series

Name	Bolyai Society Mathematical Studies
Volume	28
ISSN (Print)	1217-4696

Conference

Conference	Mathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018
Country/Territory	Hungary
City	Budapest
Period	7/2/18 → 7/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

Access to Document

10.1007/978-3-662-59204-5_1

Cite this

@inproceedings{7941159a7a2241069ba17bea66f2ffd8,

title = "Lov{\'a}sz, Vectors, Graphs and Codes",

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{\'a}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{\'a}sz (formula presented)-function of a graph cannot be bounded by any function of its Shannon capacity.",

keywords = "Cayley graphs, List decodable codes, Maxcut, Ramsey graphs, Shannon capacity of graphs, The -function",

author = "Noga Alon",

note = "Publisher Copyright: {\textcopyright} 2019, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.; Mathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018 ; Conference date: 02-07-2018 Through 06-07-2018",

year = "2019",

doi = "10.1007/978-3-662-59204-5_1",

language = "English (US)",

isbn = "9783662592038",

series = "Bolyai Society Mathematical Studies",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "1--16",

editor = "Imre B{\'a}r{\'a}ny and Katona, {Gyula O.} and Attila Sali",

booktitle = "Building Bridges II - Mathematics of L{\'a}szl{\'o} Lov{\'a}sz",

address = "Germany",

}

Alon, N 2019, Lovász, Vectors, Graphs and Codes. in I Bárány, GO Katona & A Sali (eds), Building Bridges II - Mathematics of László Lovász. Bolyai Society Mathematical Studies, vol. 28, Springer Science and Business Media Deutschland GmbH, pp. 1-16, Mathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018, Budapest, Hungary, 7/2/18. https://doi.org/10.1007/978-3-662-59204-5_1

TY - GEN

T1 - Lovász, Vectors, Graphs and Codes

AU - Alon, Noga

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Cayley graphs

KW - List decodable codes

KW - Maxcut

KW - Ramsey graphs

KW - Shannon capacity of graphs

KW - The -function

UR - http://www.scopus.com/inward/record.url?scp=85098815877&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85098815877&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-59204-5_1

DO - 10.1007/978-3-662-59204-5_1

M3 - Conference contribution

AN - SCOPUS:85098815877

SN - 9783662592038

T3 - Bolyai Society Mathematical Studies

SP - 1

EP - 16

BT - Building Bridges II - Mathematics of László Lovász

A2 - Bárány, Imre

A2 - Katona, Gyula O.

A2 - Sali, Attila

PB - Springer Science and Business Media Deutschland GmbH

T2 - Mathematical Conference to celebrate 70th birthday of Laszlo Lovasz, 2018

Y2 - 2 July 2018 through 6 July 2018

ER -

Lovász, Vectors, Graphs and Codes

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this