On minrank and forbidden subgraphs

DOI10.4230/LIPICS.APPROX-RANDOM.2018.42MaRDI QIDQ5009538zbMATH OpenFDO

Authors Ishay Haviv

Publication date 4 August 2021

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2018.42

zbMATH Keywords

circuit complexityforbidden subgraphsminrankShannon capacity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Measures of information, entropy (94A17)

Recommendations

• On minrank and forbidden subgraphs
• The minrank of random graphs over arbitrary fields
• The minrank of random graphs
• The minimum rank problem over the finite field of order 2: Minimum rank 3
• On the minimum rank of a graph over finite fields

Cites work

• H-wise independence
• A note on odd cycle-complete graph Ramsey numbers
• A note on Ramsey numbers
• Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
• Asymptotic lower bounds for Ramsey functions
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Broadcasting With Side Information: Bounding and Approximating the Broadcast Rate
• Constructive lower bounds on classical multicolor Ramsey numbers
• Cycles of nonzero elements in low rank matrices
• Explicit Ramsey graphs and orthonormal labelings
• scientific article; zbMATH DE number 3712115 (Why is no real title available?)
• scientific article; zbMATH DE number 3743861 (Why is no real title available?)
• scientific article; zbMATH DE number 3745081 (Why is no real title available?)
• scientific article; zbMATH DE number 17660 (Why is no real title available?)
• scientific article; zbMATH DE number 176871 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1787227 (Why is no real title available?)
• Index Coding With Side Information
• Information flows, graphs and their guessing numbers
• Linear index coding via semidefinite programming
• MaxCut in ${\bm H)$-Free Graphs
• Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems
• On cycle—Complete graph ramsey numbers
• On minrank and forbidden subgraphs
• On Some Problems of Lovász Concerning the Shannon Capacity of a Graph
• On the Shannon capacity of a graph
• Orthogonal representations over finite fields and the chromatic number of graphs
• Ramsey bounds for graph products
• Some structural properties of low-rank matrices related to computational complexity
• The Minrank of Random Graphs
• The probabilistic method

Cited in

(9)

• Polynomial time algorithm for min-ranks of graphs with simple tree structures
• The minrank of random graphs over arbitrary fields
• A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs
• On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
• The minrank of random graphs
• On minrank and the Lovász theta-function
• On minrank and forbidden subgraphs
• Forbidden minors to graphs with small feedback sets
• Min-rank conjecture for log-depth circuits

This page was built for publication: On minrank and forbidden subgraphs

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