2026-07-25T12:38:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9446 2024-03-06T10:44:25Z ddc:004 open_access

On Minrank and Forbidden Subgraphs Haviv, Ishay Minrank Forbidden subgraphs Shannon capacity Circuit Complexity The minrank over a field F of a graph G on the vertex set {1,2,...,n} is the minimum possible rank of a matrix M in F^{n x n} such that M_{i,i} != 0 for every i, and M_{i,j}=0 for every distinct non-adjacent vertices i and j in G. For an integer n, a graph H, and a field F, let g(n,H,F) denote the maximum possible minrank over F of an n-vertex graph whose complement contains no copy of H. In this paper we study this quantity for various graphs H and fields F. For finite fields, we prove by a probabilistic argument a general lower bound on g(n,H,F), which yields a nearly tight bound of Omega(sqrt{n}/log n) for the triangle H=K_3. For the real field, we prove by an explicit construction that for every non-bipartite graph H, g(n,H,R) >= n^delta for some delta = delta(H)>0. As a by-product of this construction, we disprove a conjecture of Codenotti, Pudlák, and Resta. The results are motivated by questions in information theory, circuit complexity, and geometry. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ishay Haviv 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.42 urn:nbn:de:0030-drops-94461 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.42 eng https://creativecommons.org/licenses/by/3.0/legalcode