Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2019 | OriginalPaper | Chapter

Lovász, Vectors, Graphs and Codes

Author : Noga Alon

Published in: Building Bridges II

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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 \(\theta \)-function of a graph cannot be bounded by any function of its Shannon capacity.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
next chapter Continuous Matroids Revisited
Literature
1.
M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combinatorial Theory Ser. A 29 (1980), 354–360.MathSciNetCrossRef
2.
N. Alon, Explicit Ramsey graphs and orthonormal labelings, The Electronic J. Combinatorics 1 (1994), R12, 8pp.
3.
4.
5.
6.
N. Alon, B. Bollobás, M. Krivelevich and B. Sudakov, Maximum cuts and judicious partitions in graphs without short cycles, J. Combinatorial Theory, Ser. B 88 (2003), 329–346.MathSciNetCrossRef
7.
N. Alon, B. Bukh and Y. Polyanskiy, List-decodable zero-rate codes, IEEE Transactions on Information Theory 65 (2019), 1657–1667.MathSciNetCrossRef
8.
N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Math. 72(1988), 15–19.MathSciNetCrossRef
9.
N. Alon and M. Krivelevich, Constructive bounds for a Ramsey-type problem, Graphs and Combinatorics 13 (1997), 217–225.MathSciNetCrossRef
10.
N. Alon and N. Kahale, Approximating the independence number via the \(\theta \)-function, Math. Programming 80 (1998), 253–264.MathSciNetMATH
11.
N. Alon, M. Krivelevich and B. Sudakov, MaxCut in H-free graphs, Combinatorics, Probability and Computing 14 (2005), 629–647.MathSciNetCrossRef
12.
N. Alon and A. Orlitsky, Repeated communication and Ramsey graphs, IEEE Transactions on Information Theory 41 (1995), 1276–1289.MathSciNetCrossRef
13.
V. M. Blinovskiĭ, Bounds for codes in decoding by a list of finite length, Problemy Peredachi Informatsii 22 (1986),11–25.MathSciNet
14.
T. Bohman and P. Keevash, Dynamic Concentration of the Triangle-Free Process, The Seventh European Conference on Combinatorics, Graph Theory and Applications, 489–495, CRM Series, 16, Ed. Norm., Pisa, 2013.
15.
F. R. K. Chung, R. Cleve and P. Dagum, A note on constructive lower bounds for the Ramsey numbers \(R(3,t)\), J. Combinatorial Theory Ser. B 57 (1993), 150–155.MathSciNetCrossRef
16.
R. Cleve and P. Dagum, A constructive \(\Omega (t^{1.26})\) lower bound for the Ramsey number \(R(3,t)\), Inter. Comp. Sci. Inst. Tech. Rep. TR-89-009, 1989.
17.
F. Chung and R. L. Graham, Erdős on Graphs: His Legacy of Unsolved Problems, A. K. Peters, Ltd., Wellesley, MA, 1998.CrossRef
18.
B. Codenotti, P. Pudlák, and G. Resta, Some structural properties of low-rank matrices related to computational complexity, Theoret. Comput. Sci. 235 (2000), 89–107.MathSciNetCrossRef
19.
20.
C. S. Edwards, Some extremal properties of bipartite subgraphs, Canadian Journal of Mathematics 3 (1973), 475–485.MathSciNetCrossRef
21.
C. S. Edwards, An improved lower bound for the number of edges in a largest bipartite subgraph, Proc. \(2^{nd}\) Czechoslovak Symposium on Graph Theory, Prague, (1975), 167–181.
22.
23.
24.
P. Erdős, Problems and results in Graph Theory and Combinatorial Analysis, in: Graph Theory and Related Topics, J. A. Bondy and U. S. R. Murty (Eds.), Proc. Conf. Waterloo, 1977, Academic Press, New York, 1979, 153–163.
25.
P. Erdős, R. J. McEliece and H. Taylor, Ramsey bounds for graph products, Pacific Journal of Mathematics, 37 (1971),45–46.MathSciNetCrossRef
26.
P. Erdős and A. Rényi, On a problem in the theory of graphs (in Hungarian), Publ. Math. Inst. Hungar. Acad. Sci. 7 (1962), 215–235.
27.
U. Feige, Randomized graph products, chromatic numbers, and the Lovász \(\theta \)-function, Proc. of the 27th ACM STOC, ACM Press (1995), 635–640.
28.
29.
30.
31.
W. Haemers, An upper bound for the Shannon capacity of a graph, Colloq. Math. Soc. János Bolyai 25, Algebraic Methods in Graph Theory, Szeged, Hungary (1978), 267–272.
32.
B. S. Kashin and S. V. Konyagin, On systems of vectors in a Hilbert space, Trudy Mat. Inst. imeni V. A. Steklova 157 (1981), 64–67. English translation in: Proc. of the Steklov Institute of Mathematics (AMS 1983), 67–70.
33.
J. H. Kim, The Ramsey number \(R(3,t)\) has order of magnitude \(t^2/\log t\), Random Structures Algorithms 7 (1995), 173–207.MathSciNetCrossRef
34.
S. V. Konyagin, Systems of vectors in Euclidean space and an extremal problem for polynomials, Mat. Zametki 29 (1981), 63–74. English translation in: Mathematical Notes of the Academy of the USSR 29 (1981), 33–39.MathSciNetCrossRef
35.
36.
V. I. Levenshtein, The application of Hadamard matrices to a problem in coding, Problemy Kibernetiki, 5 (1961), 123–136. English translation in Problems of Cybernetics 5, 1964 pp. 166–184.
37.
L. Lovász, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978), no. 3, 319–324.MathSciNetCrossRef
38.
39.
L. Lovász, Combinatorial Problems and Exercises, North Holland, Amsterdam, 1979, Problem 11.8.
40.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977.MATH
41.
42.
43.
44.
J. B. Shearer, A note on bipartite subgraphs of triangle-free graphs, Random Structures and Algorithms 3 (1992), 223–226.MathSciNetCrossRef
Metadata
Title
Lovász, Vectors, Graphs and Codes
Author
Noga Alon
Copyright Year
2019
Publisher
Springer Berlin Heidelberg
Book
Building Bridges II

Print ISBN: 978-3-662-59203-8

Electronic ISBN: 978-3-662-59204-5

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-662-59204-5_1

Premium Partner

    Image Credits