{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T18:28:40Z","timestamp":1712773720735},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,9,6]],"date-time":"2023-09-06T00:00:00Z","timestamp":1693958400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,9,6]],"date-time":"2023-09-06T00:00:00Z","timestamp":1693958400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00493-023-00016-9","type":"journal-article","created":{"date-parts":[[2023,9,6]],"date-time":"2023-09-06T09:01:48Z","timestamp":1693990908000},"page":"853-884","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Prague Dimension of Random Graphs"],"prefix":"10.1007","volume":"43","author":[{"given":"He","family":"Guo","sequence":"first","affiliation":[]},{"given":"Kalen","family":"Patton","sequence":"additional","affiliation":[]},{"given":"Lutz","family":"Warnke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,6]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF02579381","volume":"6","author":"N Alon","year":"1986","unstructured":"Alon, N.: Covering graphs by the minimum number of equivalence relations. Combinatorica 6, 201\u2013206 (1986)","journal-title":"Combinatorica"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Alweiss, R.: On the product dimension of clique factors. Eur. J. Combin. 86, 103097 10 (2020)","DOI":"10.1016\/j.ejc.2020.103097"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1016\/j.aim.2009.02.018","volume":"221","author":"T Bohman","year":"2009","unstructured":"Bohman, T.: The triangle-free process. Adv. Math. 221, 1653\u20131677 (2009)","journal-title":"Adv. Math."},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1112\/jlms.12242","volume":"100","author":"T Bohman","year":"2019","unstructured":"Bohman, T., Warnke, L.: Large girth approximate steiner triple systems. J. Lond. Math. Soc. 100, 895\u2013913 (2019)","journal-title":"J. Lond. Math. Soc."},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01202786","volume":"13","author":"B Bollob\u00e1s","year":"1993","unstructured":"Bollob\u00e1s, B., Erd\u0151s, P., Spencer, J., West, D.: Clique coverings of the edges of a random graph. Combinatorica 13, 1\u20135 (1993)","journal-title":"Combinatorica"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/BF02579256","volume":"6","author":"D de Caen","year":"1986","unstructured":"de Caen, D.: Extremal clique coverings of complementary graphs. Combinatorica 6, 309\u2013314 (1986)","journal-title":"Combinatorica"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"2011","DOI":"10.1016\/j.disc.2007.04.041","volume":"308","author":"M Cavers","year":"2008","unstructured":"Cavers, M., Verstra\u00ebte, J.: Clique partitions of complements of forests and bounded degree graphs. Discrete Math. 308, 2011\u20132017 (2008)","journal-title":"Discrete Math."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1017\/S0963548313000448","volume":"23","author":"D Conlon","year":"2014","unstructured":"Conlon, D., Fox, J., Sudakov, B.: Short proofs of some extremal results. Combin. Probab. Comput. 23, 8\u201328 (2014)","journal-title":"Combin. Probab. Comput."},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/130947076","volume":"45","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M.: Known algorithms for edge clique cover are probably optimal. SIAM J. Comput. 45, 67\u201383 (2016)","journal-title":"SIAM J. Comput."},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01300127","volume":"16","author":"N Eaton","year":"1996","unstructured":"Eaton, N., R\u00f6dl, V.: Graphs of small dimensions. Combinatorica 16, 59\u201385 (1996)","journal-title":"Combinatorica"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1017\/S0963548320000280","volume":"29","author":"S Ehard","year":"2020","unstructured":"Ehard, S., Glock, S., Joos, F.: Pseudorandom hypergraph matchings. Combin. Probab. Comput. 29, 868\u2013885 (2020)","journal-title":"Combin. Probab. Comput."},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0012-365X(88)90197-5","volume":"72","author":"P Erd\u0151s","year":"1988","unstructured":"Erd\u0151s, P., Faudree, R., Ordman, E.: Clique partitions and clique coverings. Discrete Math. 72, 93\u2013101 (1988)","journal-title":"Discrete Math."},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"106","DOI":"10.4153\/CJM-1966-014-3","volume":"18","author":"P Erd\u0151s","year":"1966","unstructured":"Erd\u0151s, P., Goodman, A., P\u00f3sa, L.: The representation of a graph by set intersections. Can. J. Math. 18, 106\u2013112 (1966)","journal-title":"Can. J. Math."},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1017\/S0963548300000808","volume":"2","author":"P Erd\u0151s","year":"1993","unstructured":"Erd\u0151s, P., Ordman, E., Zalcstein, Y.: Clique partitions of chordal graphs. Combin. Probab. Comput. 2, 409\u2013415 (1993)","journal-title":"Combin. Probab. Comput."},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1214\/aop\/1176996452","volume":"3","author":"D Freedman","year":"1975","unstructured":"Freedman, D.: On tail probabilities for martingales. Ann. Probab. 3, 100\u2013118 (1975)","journal-title":"Ann. Probab."},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01192522","volume":"15","author":"A Frieze","year":"1995","unstructured":"Frieze, A., Reed, B.: Covering the edges of a random graph by cliques. Combinatorica 15, 489\u2013497 (1995)","journal-title":"Combinatorica"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"F\u00fcredi, Z.: On the Prague dimension of Kneser graphs. In: Numbers. Information and Complexity (Bielefeld, 1998), pp. 143\u2013150. Kluwer Acad. Publ, Boston (2000)","DOI":"10.1007\/978-1-4757-6048-4_12"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.1137\/17M1114703","volume":"32","author":"Z F\u00fcredi","year":"2018","unstructured":"F\u00fcredi, Z., Kantor, I.: Kneser ranks of random graphs and minimum difference representations. SIAM J. Discrete Math. 32, 1016\u20131028 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00493-019-3921-7","volume":"40","author":"H Guo","year":"2020","unstructured":"Guo, H., Warnke, L.: Packing nearly optimal Ramsey $${R}(3, t)$$ graphs. Combinatorica 40, 63\u2013103 (2020)","journal-title":"Combinatorica"},{"key":"16_CR20","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"key":"16_CR21","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley-Interscience, New York (2000)"},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jcta.1996.0001","volume":"73","author":"J Kahn","year":"1996","unstructured":"Kahn, J.: Asymptotically good list-colorings. J. Combin. Theory Ser. A 73, 1\u201359 (1996)","journal-title":"J. Combin. Theory Ser. A"},{"key":"16_CR23","unstructured":"Kahn, J., Park,J.: Tuza\u2019s conjecture for random graphs. Rand. Struct. Algor. To appear. arXiv:2007.04351"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"5","DOI":"10.4171\/OWR\/2017\/1","volume":"14","author":"J Kahn","year":"2017","unstructured":"Kahn, J., Steger, A., Sudakov, B.: Combinatorics. Oberwolfach Rep. 14, 5\u201381 (2017)","journal-title":"Oberwolfach Rep."},{"key":"16_CR25","unstructured":"Kantor, I.: Graphs, codes, and colorings. PhD thesis, University of Illinois at Urbana-Champaign (2010). Available at http:\/\/hdl.handle.net\/2142\/18247"},{"key":"16_CR26","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/S0012-365X(00)00283-1","volume":"235","author":"J K\u00f6rner","year":"2001","unstructured":"K\u00f6rner, J., Marton, K.: Relative capacity and dimension of graphs. Discrete Math. 235, 307\u2013315 (2001)","journal-title":"Discrete Math."},{"key":"16_CR27","doi-asserted-by":"publisher","first-page":"2207","DOI":"10.1109\/18.720537","volume":"44","author":"J K\u00f6rner","year":"1998","unstructured":"K\u00f6rner, J., Orlitsky, A.: Zero-error information theory. IEEE Trans. Inform. Theory 44, 2207\u20132229 (1998)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"16_CR28","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/359340.359346","volume":"21","author":"L Kou","year":"1978","unstructured":"Kou, L., Stockmeyer, L., Wong, C.: Covering edges by cliques with regard to keyword conflicts and intersection graphs. Comm. ACM 21, 135\u2013139 (1978)","journal-title":"Comm. ACM"},{"key":"16_CR29","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1137\/130942292","volume":"29","author":"V Kurauskas","year":"2015","unstructured":"Kurauskas, V., Rybarczyk, K.: On the chromatic index of random uniform hypergraphs. SIAM J. Discrete Math. 29, 541\u2013558 (2015)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR30","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(80)90043-X","volume":"29","author":"L Lov\u00e1sz","year":"1980","unstructured":"Lov\u00e1sz, L., Ne\u0161et\u0159il, J., Pultr, A.: On a product dimension of graphs. J. Combin. Theory Ser. B 29, 47\u201367 (1980)","journal-title":"J. Combin. Theory Ser. B"},{"key":"16_CR31","doi-asserted-by":"crossref","unstructured":"McDiarmid, C.: Concentration. In: Probabilistic methods for Algorithmic Discrete Mathematics, pp.\u00a0195\u2013248. Springer, Berlin\u00a0(1998)","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"16_CR32","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<376::AID-RSA10>3.0.CO;2-0","volume":"17","author":"M Molloy","year":"2000","unstructured":"Molloy, M., Reed, B.: Near-optimal list colorings. Rand. Struct. Algor. 17, 376\u2013402 (2000)","journal-title":"Rand. Struct. Algor."},{"key":"16_CR33","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Pultr, A.: A Dushnik-Miller type dimension of graphs and its complexity. In Fundamentals of Computation Theory (Proc. Internat. Conf., Pozna\u0144-K\u00f3rnik, 1977), pp.\u00a0482\u2013493. Springer, Berlin\u00a0(1977)","DOI":"10.1007\/3-540-08442-8_119"},{"key":"16_CR34","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0012-365X(78)90186-3","volume":"23","author":"J Ne\u0161et\u0159il","year":"1978","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: A simple proof of the Galvin-Ramsey property of the class of all finite graphs and a dimension of a graph. Discrete Math. 23, 49\u201355 (1978)","journal-title":"Discrete Math."},{"key":"16_CR35","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: Products of graphs and their applications. In: Graph Theory (\u0141ag\u00f3w, 1981), pp.\u00a0151\u2013160. Springer, Berlin\u00a0(1983)","DOI":"10.1007\/BFb0071625"},{"key":"16_CR36","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"80","author":"J Orlin","year":"1977","unstructured":"Orlin, J.: Contentment in graph theory: covering graphs with cliques. Indag. Math. 80, 406\u2013424 (1977)","journal-title":"Indag. Math."},{"key":"16_CR37","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/0097-3165(89)90074-5","volume":"51","author":"N Pippenger","year":"1989","unstructured":"Pippenger, N., Spencer, J.: Asymptotic behavior of the chromatic index for hypergraphs. J. Combin. Theory Ser. A 51, 24\u201342 (1989)","journal-title":"J. Combin. Theory Ser. A"},{"key":"16_CR38","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0166-218X(81)90007-X","volume":"3","author":"S Poljak","year":"1981","unstructured":"Poljak, S., R\u00f6dl, V., Turz\u00edk, D.: Complexity of representation of graphs by set systems. Discrete Appl. Math. 3, 301\u2013312 (1981)","journal-title":"Discrete Appl. Math."},{"key":"16_CR39","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0166-218X(85)90061-7","volume":"10","author":"F Roberts","year":"1985","unstructured":"Roberts, F.: Applications of edge coverings by cliques. Discrete Appl. Math. 10, 93\u2013109 (1985)","journal-title":"Discrete Appl. Math."},{"key":"16_CR40","unstructured":"\u0160ileikis, M., Warnke, L.: Counting extensions revisited. Rand. Struct. Algor. To Appear. arXiv:1911.03012"},{"key":"16_CR41","doi-asserted-by":"crossref","unstructured":"Skums, P., Bunimovich, L.: Graph fractal dimension and structure of fractal networks: a combinatorial perspective. J. Complex Netw. 8(4), cnaa037 (2020)","DOI":"10.1093\/comnet\/cnaa037"},{"key":"16_CR42","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02579286","volume":"2","author":"W Wallis","year":"1982","unstructured":"Wallis, W.: Asymptotic values of clique partition numbers. Combinatorica 2, 99\u2013101 (1982)","journal-title":"Combinatorica"},{"key":"16_CR43","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1017\/S0963548315000103","volume":"25","author":"L Warnke","year":"2016","unstructured":"Warnke, L.: On the method of typical bounded differences. Combin. Probab. Comput. 25, 269\u2013299 (2016)","journal-title":"Combin. Probab. Comput."},{"key":"16_CR44","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s11856-017-1546-3","volume":"221","author":"L Warnke","year":"2017","unstructured":"Warnke, L.: Upper tails for arithmetic progressions in random subsets. Israel J. Math. 221, 317\u2013365 (2017)","journal-title":"Israel J. Math."},{"key":"16_CR45","unstructured":"Warnke, L.: On Wormald\u2019s differential equation method. Combin. Probab. Comput. To Appear. arXiv:1905.08928"},{"key":"16_CR46","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.jctb.2019.05.003","volume":"140","author":"L Warnke","year":"2020","unstructured":"Warnke, L.: On the missing log in upper tail estimates. J. Combin. Theory Ser. B 140, 98\u2013146 (2020)","journal-title":"J. Combin. Theory Ser. B"},{"key":"16_CR47","volume-title":"Introduction to Graph Theory","author":"D West","year":"1996","unstructured":"West, D.: Introduction to Graph Theory. Prentice Hall, New Jersey (1996)"},{"key":"16_CR48","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N Wormald","year":"1995","unstructured":"Wormald, N.: Differential equations for random processes and random graphs. Ann. Appl. Probab. 5, 1217\u20131235 (1995)","journal-title":"Ann. Appl. Probab."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00016-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-023-00016-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-023-00016-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,1]],"date-time":"2023-10-01T19:02:15Z","timestamp":1696186935000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-023-00016-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,6]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["16"],"URL":"https:\/\/doi.org\/10.1007\/s00493-023-00016-9","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,6]]},"assertion":[{"value":"10 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}