
arXiv: 1806.00638
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 ∈ F n × 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 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 = K 3 . 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.
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT), 004, Shannon capacity, Computer Science - Data Structures and Algorithms, Minrank, FOS: Mathematics, Forbidden subgraphs, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Circuit Complexity, ddc: ddc:004
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT), 004, Shannon capacity, Computer Science - Data Structures and Algorithms, Minrank, FOS: Mathematics, Forbidden subgraphs, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), Circuit Complexity, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
