On minrank and the Lovász theta-function

DOI10.4230/LIPICS.APPROX-RANDOM.2018.13MaRDI QIDQ5009505zbMATH OpenFDO

Authors Ishay Haviv

Publication date 4 August 2021

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

zbMATH Keywords

Shannon capacitytheta functionmultivariate polynomialsminrankhigher incidence matrices

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(4)

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

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)