{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:25:27Z","timestamp":1787340327833,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"Digraphs","award":["ANR-19-CE48-0013"],"award-info":[{"award-number":["ANR-19-CE48-0013"]}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-21-CE48-0014"],"award-info":[{"award-number":["ANR-21-CE48-0014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013589","name":"Research England","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013589","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"publisher","award":["IES\/R1\/231083"],"award-info":[{"award-number":["IES\/R1\/231083"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T004878\/1"],"award-info":[{"award-number":["EP\/T004878\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We show that for any natural number [Formula: see text], there is a constant [Formula: see text] and a subgraph-closed class having, for any natural [Formula: see text], at most [Formula: see text] graphs on [Formula: see text] vertices up to isomorphism, but no adjacency labeling scheme with labels of size at most [Formula: see text]. In other words, for every [Formula: see text], there is a small\u2014even tiny\u2014monotone class without universal graphs of size [Formula: see text]. Prior to this result, it was not excluded that every small class has an almost linear universal graph, or equivalently a labeling scheme with labels of size [Formula: see text]. The existence of such a labeling scheme, a scaled-down version of the recently disproved Implicit Graph Conjecture, was repeatedly raised [Gavoille and Labourel, Proceedings of the 15 th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci. 4698, Springer, 2007, pp. 582\u2013593; Dujmovi\u0107 et al., J. ACM, 68 (2021), pp. 1\u201333; Bonamy, Gavoille, and Pilipczuk, SIAM J. Discrete Math., 36 (2022), pp. 2082\u20132099; Bonnet et al., Comb. Theory, 2 (2022)]. Furthermore, our small monotone classes have unbounded twin-width and thus simultaneously disprove the already-refuted Small conjecture, but this time with a self-contained proof, not relying on elaborate group-theoretic constructions. As our main ingredient, we show that with high probability an Erd\u0151s\u2013R\u00e9nyi random graph [Formula: see text] with [Formula: see text] has, for every [Formula: see text], at most [Formula: see text] subgraphs on [Formula: see text] vertices, up to isomorphism. As a barrier to our general method of producing even more complex tiny classes, we show that when [Formula: see text], the latter no longer holds. More concretely, we provide an explicit lower bound on the number of unlabeled [Formula: see text]-vertex induced subgraphs of [Formula: see text] when [Formula: see text]. We thereby obtain a threshold for the property of having exponentially many unlabeled induced subgraphs: if [Formula: see text] with [Formula: see text], then with high probability even the number of all unlabeled (not necessarily induced) subgraphs is [Formula: see text], whereas if [Formula: see text] for sufficiently large [Formula: see text], then with high probability the number of unlabeled induced subgraphs is [Formula: see text]. This result supplements the study of counting unlabeled induced subgraphs that was initiated by Erd\u0151s and R\u00e9nyi with a question on the number of unlabeled induced subgraphs of Ramsey graphs, eventually answered by Shelah.<\/jats:p>","DOI":"10.1137\/23m1618661","type":"journal-article","created":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T04:55:22Z","timestamp":1729054522000},"page":"1578-1601","source":"Crossref","is-referenced-by-count":0,"title":["Small but Unwieldy: A Lower Bound on Adjacency Labels for Small Classes"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":true,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"Universit\u00e9 de Lyon, ENS de Lyon, UCBL, CNRS, LIP, Lyon, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Julien","family":"Duron","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon, ENS de Lyon, UCBL, CNRS, LIP, Lyon, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6543-2934","authenticated-orcid":true,"given":"John","family":"Sylvester","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8763-9533","authenticated-orcid":true,"given":"Maksim","family":"Zhukovskii","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Sheffield, Sheffield, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,10,16]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113573"},{"key":"ref2","first-page":"3","volume":"4","author":"Alekseev V. E.","year":"1997","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.37236\/124"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90074-5"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01789457"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3088513"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/100789403"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"A. Banerjee, An adjacency labeling scheme based on a decomposition of trees into caterpillars, in Combinatorial Algorithms: 33rd International Workshop, Springer, New York, 2022, pp. 114\u2013127.","DOI":"10.1007\/978-3-031-06678-8_9"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.03.001"},{"key":"ref10","unstructured":"R. L. Blankenship, Book Embeddings of Graphs, Doctoral Dissertation, Louisiana State University and Agricultural & Mechanical College, 2003."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/20M1330464"},{"key":"ref12","series-title":"Languages, and Programming, LIPIcs 297","first-page":"31:1","volume-title":"Proceedings of the 51st International Colloquium on Automata","author":"Bonnet \u00c9.","year":"2024"},{"key":"ref13","volume":"2","author":"Bonnet \u00c9.","year":"2022","journal-title":"Comb. Theory"},{"key":"ref14","unstructured":"\u00c9. Bonnet, C. Geniet, R. Tessera, and S. Thomass\u00e9, Twin-width VII: Groups, preprint, arXiv:2204.12330, 2022."},{"key":"ref15","first-page":"4","volume":"20","author":"Bonnet \u00c9.","year":"2024","journal-title":"Log. Methods Comput. Sci."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113565"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/3477542"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90085-X"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.2307\/1968802"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113842"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1017\/9781009260268"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_52"},{"key":"ref23","volume-title":"Ramsey Theory","author":"Graham R. L.","year":"1980"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2022.07.023"},{"key":"ref25","unstructured":"N. Harms, Universal communication, universal graphs, and graph labeling, in Proceedings of the 11th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2020."},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"N. Harms, S. Wild, and V. Zamaraev, Randomized communication and implicit graph representations, in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, 2022, pp. 1220\u20131233.","DOI":"10.1145\/3519935.3519978"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"H. Hatami and P. Hatami, The Implicit Graph Conjecture is false, in Proceedings of the 63rd Annual Symposium on Foundations of Computer Science, IEEE, 2022, pp. 1134\u20131137.","DOI":"10.1109\/FOCS54457.2022.00109"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"S. Kannan, M. Naor, and S. Rudich, Implicit representation of graphs, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 334\u2013343.","DOI":"10.1145\/62212.62244"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"ref31","unstructured":"J. H. Muller, Local Structure in Graph Classes, Ph.D. thesis, Georgia Institute of Technology, 1988."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.006"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.4310\/ACTA.2020.v225.n1.a3"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2845"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1618661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:30:14Z","timestamp":1787337014000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1618661"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,16]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1137\/23M1618661"],"URL":"https:\/\/doi.org\/10.1137\/23m1618661","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,16]]}}}