{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:54:41Z","timestamp":1787324081659,"version":"build-2736575974"},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE40-0009-01"],"award-info":[{"award-number":["ANR-16-CE40-0009-01"]}],"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-18-CE40-0032"],"award-info":[{"award-number":["ANR-18-CE40-0032"]}],"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-01"],"award-info":[{"award-number":["ANR-21-CE48-0014-01"]}],"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-11-LABX-0025"],"award-info":[{"award-number":["ANR-11-LABX-0025"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For any hereditary graph class [Formula: see text], we construct optimal adjacency labeling schemes for the classes of subgraphs and induced subgraphs of Cartesian products of graphs in [Formula: see text]. As a consequence, we show that if [Formula: see text] admits efficient adjacency labels (or, equivalently, small induced-universal graphs) meeting the information-theoretic minimum, then so do the classes of subgraphs and induced subgraphs of Cartesian products of graphs in [Formula: see text]. Our proof uses ideas from randomized communication complexity, hashing, and additive combinatorics and improves upon recent results of Chepoi, Labourel, and Ratel [ J. Graph Theory, 93 (2020), pp. 64\u201387].<\/jats:p>","DOI":"10.1137\/23m1587713","type":"journal-article","created":{"date-parts":[[2024,7,22]],"date-time":"2024-07-22T04:01:22Z","timestamp":1721620882000},"page":"2181-2193","source":"Crossref","is-referenced-by-count":2,"title":["Optimal Adjacency Labels for Subgraphs of Cartesian Products"],"prefix":"10.1137","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6200-0514","authenticated-orcid":true,"given":"Louis","family":"Esperet","sequence":"first","affiliation":[{"name":"CNRS, Laboratoire G-SCOP, Grenoble, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathaniel","family":"Harms","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, CH-1015, Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, Liverpool, L69 3BX, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,7,22]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2023.113573"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.11.002"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940874"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80001-9"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056557"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22469"},{"key":"ref7","unstructured":"L. Esperet, N. Harms, and A. Kupavskii, Sketching distances in monotone graph classes, in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX\/RANDOM 2022, September 19\u201321, 2022, University of Illinois, Urbana-Champaign), virtual conference, LIPIcs 245, A. Chakrabarti and C. Swamy, eds. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2022, pp. 18:1\u201318:23."},{"key":"ref8","unstructured":"L. Esperet, N. Harms, and V. Zamaraev, Optimal adjacency labels for subgraphs of cartesian products, in Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023, July 10\u201314, 2023, Paderborn, Germany), LIPIcs 261, K. Etessami, U. Feige, and G. Puppis, eds. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2023, pp. 57:1\u201357:11."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1970.tb56468.x"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"T. Hagerup and T. Tholey, Efficient minimal perfect hashing in nearly minimal space, in Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001), Springer, 2001, pp. 317\u2013326.","DOI":"10.1007\/3-540-44693-1_28"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2022.07.023"},{"key":"ref12","unstructured":"N. Harms, Universal communication, universal graphs, and graph labeling, in Proceedings of the\u00a011th Innovations in Theoretical Computer Science Conference (ITCS 2020, Seattle, WA), LIPIcs 151, T. Vidick, ed. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020, pp. 33:1\u201333:27."},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"N. Harms, S. Wild, and V. Zamaraev, Randomized communication and implicit graph representations, in Proceedings of the 54th Annual Symposium on Theory of Computing (STOC 2022), 2022, pp.\u00a01220\u20131233.","DOI":"10.1145\/3519935.3519978"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"H. Hatami and P. Hatami, The implicit graph conjecture is false, in Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022), 2022, pp. 1134\u20131137.","DOI":"10.1109\/FOCS54457.2022.00109"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90052-7"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/0405049"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(69)80038-4"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69672-5"},{"key":"ref19","series-title":"CRC Press Ser. Discrete Math. Appl.","volume-title":"Handbook of Applied Cryptography","author":"Menezes A. J.","year":"1997"},{"key":"ref20","unstructured":"J. H. Muller, Local Structure in Graph Classes, Ph.D. thesis, Georgia Institute of Technology, School of Information & Computer Science, Atlanta, GA,\u00a01988."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00025-4"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1090\/fim\/019"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"A. C.C. Yao, On the power of quantum fingerprinting, in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC), 2003, pp. 77\u201381.","DOI":"10.1145\/780542.780554"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1587713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:18:25Z","timestamp":1787321905000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1587713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,22]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1137\/23M1587713"],"URL":"https:\/\/doi.org\/10.1137\/23m1587713","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,22]]}}}