{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T10:55:39Z","timestamp":1769511339590,"version":"3.49.0"},"reference-count":15,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2005,12,12]],"date-time":"2005-12-12T00:00:00Z","timestamp":1134345600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2006,9]]},"abstract":"Abstract<\/jats:title>We study here lifts and random lifts of graphs, as defined by Amit and Linial (Combinatorica 22 (2002), 1\u201318). We consider the Hadwiger number \u03b7 and the Haj\u00f3s number \u03c3 of \u2113\u2010lifts of K<\/jats:italic>n<\/jats:italic><\/jats:sup> and analyze their extremal as well as their typical values (that is, for random lifts). When \u2113 = 2, we show that ${n \\over 2} \\leq \\eta \\leq n$<\/jats:styled-content>, and random lifts achieve the lower bound (as n<\/jats:italic> \u2192 \u221e). For bigger values of \u2113, we show $\\Omega({n \\over {\\sqrt{\\log n}}}) \\leq \\eta \\leq n\\sqrt{\\ell}$<\/jats:styled-content>. We do not know how tight these bounds are, and in fact, the most interesting question that remains open is whether it is possible for \u03b7 to be o<\/jats:italic>(n<\/jats:italic>). When \u2113 < O<\/jats:italic>(log n<\/jats:italic>), almost every \u2113\u2010lift of K<\/jats:italic>n<\/jats:italic><\/jats:sup> satisfies \u03b7 = \u0398(n<\/jats:italic>) and for $\\Omega(\\log{n}) \\leq \\ell \\leq n^{{1 \\over 3} - \\varepsilon}$<\/jats:styled-content>, almost surely $\\eta = \\Theta({n\\sqrt{\\ell} \\over {\\sqrt{\\log{n}}}})$<\/jats:styled-content>. For bigger values of \u2113, $\\Omega({n\\sqrt{\\ell} \\over {\\sqrt{\\log{\\ell}}}}) \\leq \\eta \\leq n\\sqrt{\\ell}$<\/jats:styled-content> almost always. The Haj\u00f3s number satisfies $\\Omega(\\sqrt{n}) \\leq \\sigma \\leq n$<\/jats:styled-content>, and random lifts achieve the lower bound for bounded \u2113 and approach the upper bound when \u2113 grows. \u00a9 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006<\/jats:p>","DOI":"10.1002\/rsa.20100","type":"journal-article","created":{"date-parts":[[2005,12,12]],"date-time":"2005-12-12T20:48:41Z","timestamp":1134420521000},"page":"208-225","source":"Crossref","is-referenced-by-count":6,"title":["Minors in lifts of graphs"],"prefix":"10.1002","volume":"29","author":[{"given":"Yotam","family":"Drier","sequence":"first","affiliation":[]},{"given":"Nathan","family":"Linial","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2005,12,12]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200000"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10003"},{"key":"e_1_2_1_4_2","unstructured":"A.Amit N.Linial J.Matous\u02d8ek E.Rozenman Random lifts of graphs SODA '01 Proceedings of the twelfth annual ACM\u2010SIAM symposium on Discrete algorithms (2001) 883\u2013894."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80001-1"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0188"},{"key":"e_1_2_1_7_2","volume-title":"Decompositions of Graphs","author":"Bos\u00e1k J.","year":"1990"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215145"},{"key":"e_1_2_1_9_2","volume-title":"Geometry and Combinatorics: Selected Works of J.J. Seidel","author":"Corneil D. G.","year":"1991"},{"key":"e_1_2_1_10_2","first-page":"229","volume-title":"Recent Progress in Combinatorics","author":"Gupta R. P.","year":"1969"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830000184X"},{"key":"e_1_2_1_12_2","first-page":"37","article-title":"The minimum Hadwiger number for graphs with a given mean degree of vertices","volume":"38","author":"Kostochka A. V.","year":"1982","journal-title":"Metody Diskret. Analiz"},{"key":"e_1_2_1_13_2","unstructured":"J. J.Seidel A Survey of Two\u2010Graphs Colloquio Internazionale sulle Teorie Combinatorie I (Rome 1973) pp.481\u2013511 Rome 1976. Acc. Naz. Lincei. Reprinted in [8]."},{"key":"e_1_2_1_14_2","first-page":"689","volume-title":"Two\u2010graphs, a second survey, Algebraic Methods in Graph Theory II","author":"Seidel J. J.","year":"1981"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100061521"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20100","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T22:55:17Z","timestamp":1697496917000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,12]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1002\/rsa.20100"],"URL":"https:\/\/doi.org\/10.1002\/rsa.20100","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,12]]}}}