{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:13Z","timestamp":1750221133134,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T00:00:00Z","timestamp":1557187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>\n            The\n            <jats:italic>minrank<\/jats:italic>\n            over a field F of a graph\n            <jats:italic>G<\/jats:italic>\n            on the vertex set { 1,2,\u2026 ,\n            <jats:italic>n<\/jats:italic>\n            } is the minimum possible rank of a matrix\n            <jats:italic>M<\/jats:italic>\n            \u2208 F\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n              \u00d7\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            such that\n            <jats:italic>M<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i, i<\/jats:italic>\n            <\/jats:sub>\n            \u2260 0 for every\n            <jats:italic>i<\/jats:italic>\n            , and\n            <jats:italic>M<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i, j<\/jats:italic>\n            <\/jats:sub>\n            =0 for every distinct non-adjacent vertices\n            <jats:italic>i<\/jats:italic>\n            and\n            <jats:italic>j<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            . For an integer\n            <jats:italic>n<\/jats:italic>\n            , a graph\n            <jats:italic>H<\/jats:italic>\n            , and a field F, let\n            <jats:italic>g<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ,\n            <jats:italic>H<\/jats:italic>\n            , F) denote the maximum possible minrank over F of an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph whose complement contains no copy of\n            <jats:italic>H<\/jats:italic>\n            . In this article, we study this quantity for various graphs\n            <jats:italic>H<\/jats:italic>\n            and fields F. For finite fields, we prove by a probabilistic argument a general lower bound on\n            <jats:italic>g<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ,\n            <jats:italic>H<\/jats:italic>\n            ,F), which yields a nearly tight bound of \u03a9 (\u221a\n            <jats:italic>n<\/jats:italic>\n            \/ log\n            <jats:italic>n<\/jats:italic>\n            ) for the triangle\n            <jats:italic>H<\/jats:italic>\n            =\n            <jats:italic>K<\/jats:italic>\n            <jats:sub>3<\/jats:sub>\n            . For the real field, we prove by an explicit construction that for every non-bipartite graph\n            <jats:italic>H<\/jats:italic>\n            ,\n            <jats:italic>g<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ,\n            <jats:italic>H<\/jats:italic>\n            , R) \u2265\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03b4<\/jats:sup>\n            for some \u03b4 = \u03b4 (\n            <jats:italic>H<\/jats:italic>\n            )&gt; 0. As a by-product of this construction, we disprove a conjecture of Codenotti et\u00a0al. [11]. The results are motivated by questions in information theory, circuit complexity, and geometry.\n          <\/jats:p>","DOI":"10.1145\/3322817","type":"journal-article","created":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T14:11:11Z","timestamp":1557324671000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On Minrank and Forbidden Subgraphs"],"prefix":"10.1145","volume":"11","author":[{"given":"Ishay","family":"Haviv","sequence":"first","affiliation":[{"name":"School of Computer Science, The Academic College of Tel Aviv-Yaffo, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,5,7]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/0097-3165(80)90030-8"},{"key":"e_1_2_1_2_1","article-title":"Explicit Ramsey graphs and orthonormal labelings","volume":"1","author":"Alon Noga","year":"1994","journal-title":"Electr. J. Comb."},{"doi-asserted-by":"crossref","unstructured":"Noga Alon. 2002. Graph powers. In Contemporary Combinatorics B. Bollob\u00e1s (Ed.). Springer 11--28.  Noga Alon. 2002. Graph powers. In Contemporary Combinatorics B. Bollob\u00e1s (Ed.). Springer 11--28.","key":"e_1_2_1_3_1","DOI":"10.1017\/S0963548301004965"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/0097-3165(91)90058-O"},{"unstructured":"Noga Alon Igor Balla Lior Gishboliner Adva Mond and Frank Mousset. 2018. The minrank of random graphs over arbitrary fields. Arxiv abs\/1809.01873 (2018).  Noga Alon Igor Balla Lior Gishboliner Adva Mond and Frank Mousset. 2018. The minrank of random graphs over arbitrary fields. Arxiv abs\/1809.01873 (2018).","key":"e_1_2_1_5_1"},{"unstructured":"Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method (4th ed.). Wiley Publishing.   Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method (4th ed.). Wiley Publishing.","key":"e_1_2_1_6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/FOCS.2006.42"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/TIT.2013.2264472"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1016\/S0012-365X(99)00399-4"},{"doi-asserted-by":"crossref","unstructured":"Eden Chlamt\u00e1\u010d and Ishay Haviv. 2014. Linear index coding via semidefinite programming. Combinatorics Probability 8 Computing 23 2 (2014) 223--247. Preliminary version in SODA\u201912.  Eden Chlamt\u00e1\u010d and Ishay Haviv. 2014. Linear index coding via semidefinite programming. Combinatorics Probability 8 Computing 23 2 (2014) 223--247. Preliminary version in SODA\u201912.","key":"e_1_2_1_10_1","DOI":"10.1017\/S0963548313000564"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1016\/S0304-3975(99)00185-1"},{"doi-asserted-by":"crossref","unstructured":"Reinhard Diestel. 2017. Graph Theory (5th ed.). Graduate texts in mathematics Vol. 173. Springer-Verlag Berlin..   Reinhard Diestel. 2017. Graph Theory (5th ed.). Graduate texts in mathematics Vol. 173. Springer-Verlag Berlin..","key":"e_1_2_1_12_1","DOI":"10.1007\/978-3-662-53622-3_7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1002\/jgt.3190020107"},{"unstructured":"Paul Erd\u00f6s and L\u00e1szl\u00f3 Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets A. Hajnal R. Rado and V. T. S\u00f3s (Eds.). North-Holland Amsterdam 609--627.  Paul Erd\u00f6s and L\u00e1szl\u00f3 Lov\u00e1sz. 1975. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets A. Hajnal R. Rado and V. T. S\u00f3s (Eds.). North-Holland Amsterdam 609--627.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.2140\/pjm.1971.37.45"},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"The minrank of random graphs","volume":"46","author":"Golovnev Alexander","year":"2017","journal-title":"Randomization and Approximation Techniques in Computer Science (RANDOM)."},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1109\/TIT.1979.1056027"},{"volume-title":"Algebraic Methods in Graph Theory","year":"1981","author":"Haemers Willem","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","volume-title":"International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u201918)","volume":"116","author":"Haviv Ishay","year":"2018"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/2422436.2422495"},{"key":"e_1_2_1_21_1","first-page":"64","article-title":"Systems of vectors in Hilbert space. In Number Theory, Mathematical Analysis, and Their Applications","volume":"157","author":"Kashin B. S.","year":"1981","journal-title":"Trudy Mat. Inst. Steklov."},{"key":"e_1_2_1_22_1","first-page":"63","article-title":"Systems of vectors in Euclidean space and an extremal problem for polynomials","volume":"29","author":"Konyagin S. V.","year":"1981","journal-title":"Mat. Zametki"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/TIT.1979.1055985"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1007\/BF01261326"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1007\/s004930200015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.1137\/S0097539794264809"},{"key":"e_1_2_1_27_1","article-title":"Information flows, graphs and their guessing numbers","volume":"14","author":"Riis S\u00f8ren","year":"2007","journal-title":"Electr. J. Comb."},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1090\/dimacs\/004\/38"},{"doi-asserted-by":"crossref","unstructured":"Claude E. Shannon. 1956. The zero error capacity of a noisy channel. Institute of Radio Engineers Transactions on Information Theory IT-2 (1956) 8--19.  Claude E. Shannon. 1956. The zero error capacity of a noisy channel. Institute of Radio Engineers Transactions on Information Theory IT-2 (1956) 8--19.","key":"e_1_2_1_29_1","DOI":"10.1109\/TIT.1956.1056798"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"e_1_2_1_31_1","article-title":"A note on odd cycle-complete graph Ramsey numbers","volume":"9","author":"Sudakov Benny","year":"2002","journal-title":"Electr. J. Comb."},{"volume-title":"6th Symposium. 162--176","year":"1977","author":"Valiant Leslie G.","key":"e_1_2_1_32_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.5555\/167687.167712"},{"key":"e_1_2_1_34_1","article-title":"Constructive lower bounds on classical multicolor Ramsey numbers","volume":"11","author":"Xu Xiaodong","year":"2004","journal-title":"Electr. J. Comb."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322817","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3322817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:26Z","timestamp":1750208546000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3322817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,7]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3322817"],"URL":"https:\/\/doi.org\/10.1145\/3322817","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,5,7]]},"assertion":[{"value":"2018-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}