On minrank and the Lovász theta-function

DOI10.4230/LIPICS.APPROX-RANDOM.2018.13MaRDI QIDQ5009505FDOQ5009505

Authors: Ishay Haviv 

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1802.03920

Recommendations

• The minrank of random graphs over arbitrary fields
• On minrank and forbidden subgraphs
• On minrank and forbidden subgraphs
• Lovász, vectors, graphs and codes
• A comparison of the Delsarte and Lovász bounds

zbMATH Keywords

Shannon capacitytheta functionmultivariate polynomialsminrankhigher incidence matrices

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Forbidden Intersections
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• The ellipsoid method and its consequences in combinatorial optimization
• Intersection theorems with geometric consequences
• A counterexample to Borsuk’s conjecture
• Network information flow
• Information flows, graphs and their guessing numbers
• Title not available (Why is that?)
• On the complexity of approximating the independent set problem
• The sandwich theorem
• Approximating the independence number via the \(\vartheta\)-function
• On t-designs
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Automata, Languages and Programming
• Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems
• Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers
• The Shannon capacity of a union
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• Orthogonal representations over finite fields and the chromatic number of graphs
• Matching vector codes
• Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
• Index Coding With Side Information
• On the Sperner capacity of the cyclic triangle
• The Lovász Number of Random Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonlinear Index Coding Outperforming the Linear Optimum
• The Minrank of Random Graphs
• A note on Euclidean Ramsey theory and a construction of Bourgain
• Title not available (Why is that?)
• Index Coding—An Interference Alignment Perspective
• \(H\)-wise independence
• On the Hardness of Approximating the Network Coding Capacity
• Linear index coding via semidefinite programming
• Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
• On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
• Topological Interference Management Through Index Coding

Cited In (4)

• A comparison of the Delsarte and Lovász bounds
• Lovász, vectors, graphs and codes
• The minrank of random graphs over arbitrary fields
• On Minrank and the Lov\'asz Theta Function

This page was built for publication: On minrank and the Lovász theta-function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009505)