Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

On Minrank and Forbidden Subgraphs

On Minrank and Forbidden Subgraphs 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 Fn n such that Mi, i 0 for every i, and Mi, 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 article, 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 ( n/ log n) for the triangle H=K3. For the real field, we prove by an explicit construction that for every non-bipartite graph H, g(n,H, R) n for some = (H)> 0. As a by-product of this construction, we disprove a conjecture of Codenotti et al. [11]. The results are motivated by questions in information theory, circuit complexity, and geometry. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

On Minrank and Forbidden Subgraphs

Haviv, Ishay
ACM Transactions on Computation Theory (TOCT) , Volume 11 (4): 13 – May 7, 2019
Download PDF
13 pages

Loading next page...
 
/lp/association-for-computing-machinery/on-minrank-and-forbidden-subgraphs-QL6oo8VrXc
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3322817
Publisher site
See Article on Publisher Site

Abstract

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 Fn n such that Mi, i 0 for every i, and Mi, 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 article, 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 ( n/ log n) for the triangle H=K3. For the real field, we prove by an explicit construction that for every non-bipartite graph H, g(n,H, R) n for some = (H)> 0. As a by-product of this construction, we disprove a conjecture of Codenotti et al. [11]. The results are motivated by questions in information theory, circuit complexity, and geometry.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: May 7, 2019

Keywords: Minrank

References

  • A note on Ramsey numbers
    Ajtai, Miklós; Komlós, János; Szemerédi, Endre
  • Explicit Ramsey graphs and orthonormal labelings
    Alon, Noga
  • Graph powers
    Alon, Noga
  • Multilinear polynomials and Frankl--Ray-Chaudhuri--Wilson type intersection theorems
    Alon, Noga; Babai, László; Suzuki, H.
  • The minrank of random graphs over arbitrary fields
    Alon, Noga; Balla, Igor; Gishboliner, Lior; Mond, Adva; Mousset, Frank
  • The Probabilistic Method (4th ed
    Alon, Noga; Spencer, Joel H.
  • Index coding with side information
    Bar-Yossef, Ziv; Birk, Yitzhak; Jayram, T. S.; Kol, Tomer
  • Broadcasting with side information: Bounding and approximating the broadcast rate
    Blasiak, Anna; Kleinberg, Robert; Lubetzky, Eyal
  • Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
    Caro, Yair; Li, Yusheng; Rousseau, Cecil C.; Zhang, Yuming
  • Linear index coding via semidefinite programming
    Chlamtáč, Eden; Haviv, Ishay
  • Some structural properties of low-rank matrices related to computational complexity
    Codenotti, Bruno; Pudlák, Pavel; Resta, Giovanni
  • Graph Theory (5th ed
    Diestel, Reinhard
  • On cycle-complete graph Ramsey numbers
    Erdös, Paul; Faudree, Ralph J.; Rousseau, Cecil C.; Schelp, Richard H.
  • Problems and results on 3-chromatic hypergraphs and some related questions
    Erdös, Paul; Lovász, László
  • Ramsey bounds for graph products
    Erdös, Paul; McEliece, Robert J.; Taylor, Herbert
  • The minrank of random graphs
    Golovnev, Alexander; Regev, Oded; Weinstein, Omri
  • On some problems of Lovász concerning the Shannon capacity of a graph
    Haemers, Willem
  • An upper bound for the Shannon capacity of a graph
    Haemers, Willem
  • On minrank and the Lovász theta function
    Haviv, Ishay
  • H-wise independence
    Haviv, Ishay; Langberg, Michael
  • Systems of vectors in Hilbert space
    Kashin, B. S.; Konyagin, S. V.
  • Systems of vectors in Euclidean space and an extremal problem for polynomials
    Konyagin, S. V.
  • On the Shannon capacity of a graph
    Lovász, László
  • Orthogonal representations over finite fields and the chromatic number of graphs
    Peeters, René
  • Cycles of nonzero elements in low rank matrices
    Pudlák, Pavel
  • Boolean circuits, tensor ranks, and communication complexity
    Pudlák, Pavel; Rödl, Vojtech; Sgall, Jirí
  • Information flows, graphs and their guessing numbers
    Riis, Søren
  • Almost orthogonal lines in Ed
    Rosenfeld, Moshe
  • The zero error capacity of a noisy channel
    Shannon, Claude E.
  • Asymptotic lower bounds for Ramsey functions
    Spencer, Joel
  • A note on odd cycle-complete graph Ramsey numbers
    Sudakov, Benny
  • Graph-theoretic arguments in low-level complexity
    Valiant, Leslie G.
  • Why is Boolean complexity theory difficult? In Poceedings of the London Mathematical Society Symposium on Boolean Function Complexity, Vol
    Valiant, Leslie G.
  • Constructive lower bounds on classical multicolor Ramsey numbers
    Xu, Xiaodong; Zheng, Xie; Exoo, Geoffrey; Radziszowski, Stanislaw P.