{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:06Z","timestamp":1787321106878,"version":"build-2736575974"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"name":"European Research Council Advanced Investigators","award":["267195"],"award-info":[{"award-number":["267195"]}]},{"name":"National Research, Development and Innovation Office NKFIH","award":["K116769"],"award-info":[{"award-number":["K116769"]}]},{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura Cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["16-01602Y"],"award-info":[{"award-number":["16-01602Y"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["317487"],"award-info":[{"award-number":["317487"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v \\mapsto A_v$ to the vertices $v\\in V$ such that $A_u$ and $A_v$ are disjoint if and only if $uv\\in E$. The smallest such $k$ is called the Kneser rank of $G$ and denoted by $f_{\\rm Kneser}(G)$. As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $0&lt; p&lt; 1$ there exist constants $c_i=c_i(p)&gt;0$, $i=1,2$, such that $G\\in {\\mathcal G}(n, p)$ satisfies with high probability $ c_1 n\/(\\log n)&lt; f_{\\rm Kneser}(G) &lt; c_2 n\/(\\log n). $ We apply this for other graph representations defined by Boros, Gurvich, and Meshulam. A $k$-min-difference representation of a graph $G$ is an assignment of a set $A_i$ to each vertex $i\\in V(G)$ such that $ ij\\in E(G) \\,\\, \\Leftrightarrow \\, \\, \\min \\{|A_i\\setminus A_j|,|A_j\\setminus A_i| \\}\\geq k. $ The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $f_{\\min}(G)$. Balogh and Prince proved in 2009 that for every $k$ there is a graph $G$ with $f_{\\min}(G)\\geq k$. We prove that there are constants $c''_1, c''_2&gt;0$ such that $c''_1 n\/(\\log n)&lt; f_{\\min}(G) &lt; c''_2n\/(\\log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.<\/jats:p>","DOI":"10.1137\/17m1114703","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T12:02:15Z","timestamp":1525780935000},"page":"1016-1028","source":"Crossref","is-referenced-by-count":1,"title":["Kneser Ranks of Random Graphs and Minimum Difference Representations"],"prefix":"10.1137","volume":"32","author":[{"given":"Zolt\u00e1n","family":"F\u00fcredi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ida","family":"Kantor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,8]]},"reference":[{"key":"atypb1","unstructured":"N. Alon and J. H. Spencer,\n                      The Probabilistic Method\n                      , 4th ed., Wiley Ser. Discrete Math, Optim., John Wiley & Sons, New York, 2016."},{"key":"atypb2","unstructured":"R. P. Anstee and L. Lu,\n                      Unavoidable Multicoloured Families of Configurations\n                      , preprint, arxiv:1409.4123, 2014."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-005-0039-x"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-010-0875-3"},{"key":"atypb5","unstructured":"E. Boros, R. Collado, V. Gurvich, and A. Kelmans,\n                      On 2-Representable Graphs\n                      , DIMACS REU report, 2000."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00321-2"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302966"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01300127"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1966-014-3"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192522"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010205"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/080722898"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucinski,\n                      Random Graphs\n                      , Wiley Ser. Discrete Math. Optim, Wiley, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480198348343"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90043-X"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"T. A. McKee and F. R. McMorris,\n                      Topics in Intersection Graph Theory\n                      , Discrete Math. Appl., SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719802"},{"key":"atypb17","first-page":"631","author":"Poljak S.","year":"1981","journal-title":"Amsterdam"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1114703","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:05:45Z","timestamp":1787317545000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1114703"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1114703"],"URL":"https:\/\/doi.org\/10.1137\/17m1114703","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}