{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T04:41:02Z","timestamp":1758084062631,"version":"3.44.0"},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T00:00:00Z","timestamp":1751241600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline1.png\"\/><jats:tex-math>\n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is said to be <jats:italic>common<\/jats:italic> if the number of monochromatic labelled copies of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline2.png\"\/><jats:tex-math>\n$H$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in a red\/blue edge colouring of a large complete graph is asymptotically minimised by a random colouring in which each edge is equally likely to be red or blue. We extend this notion to an off-diagonal setting. That is, we define a pair <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline3.png\"\/><jats:tex-math>\n$(H_1,H_2)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> of graphs to be <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline4.png\"\/><jats:tex-math>\n$(p,1-p)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-common if a particular linear combination of the density of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline5.png\"\/><jats:tex-math>\n$H_1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in red and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline6.png\"\/><jats:tex-math>\n$H_2$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> in blue is asymptotically minimised by a random colouring in which each edge is coloured red with probability <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline7.png\"\/><jats:tex-math>\n$p$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and blue with probability <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000094_inline8.png\"\/><jats:tex-math>\n$1-p$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Our results include off-diagonal extensions of several standard theorems on common graphs and novel results for common pairs of graphs with no natural analogue in the classical setting.<\/jats:p>","DOI":"10.1017\/s0963548325000094","type":"journal-article","created":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T03:16:38Z","timestamp":1751253398000},"page":"649-670","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Common pairs of graphs"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6616-1606","authenticated-orcid":false,"given":"Natalie","family":"Behague","sequence":"first","affiliation":[{"name":"University of Victoria"},{"name":"Mathematics Institute, University of Warwick"}]},{"given":"Natasha","family":"Morrison","sequence":"additional","affiliation":[{"name":"University of Victoria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8281-8249","authenticated-orcid":false,"given":"Jonathan A.","family":"Noel","sequence":"additional","affiliation":[{"name":"University of Victoria"}]}],"member":"56","published-online":{"date-parts":[[2025,6,30]]},"reference":[{"key":"S0963548325000094_ref27","doi-asserted-by":"publisher","DOI":"10.37236\/614"},{"key":"S0963548325000094_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22881"},{"key":"S0963548325000094_ref26","unstructured":"[26] Kr\u00e1\u013e, D. , Volec, J. and Wei, F. (2022) Common graphs with arbitrary chromatic number. E-print arXiv:\u00a02206.05800v1."},{"key":"S0963548325000094_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20256"},{"key":"S0963548325000094_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-024-2649-2"},{"key":"S0963548325000094_ref30","unstructured":"[30] Noel, J. A. (2020) Non-bipartite $k$ -common graphs, Online seminar talk, youtu.be\/BY1_3glImS0, September 2020. Extremal and Probabilistic Combinatorics Webinar, Organizers: Hladk\u00fd, J. , Piguet, D. , Volec, J. and Yepremyan, L. ."},{"key":"S0963548325000094_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21099"},{"key":"S0963548325000094_ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-024-09675-6"},{"key":"S0963548325000094_ref32","first-page":"264","article-title":"On a Problem of Formal Logic","volume":"30","author":"Ramsey","year":"1929","journal-title":"Proc. London Math. Soc"},{"key":"S0963548325000094_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196136"},{"key":"S0963548325000094_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190040403"},{"key":"S0963548325000094_ref10","first-page":"1","article-title":"Graphs containing triangles are not 3-common","volume":"2","author":"Cummings","year":"2011","journal-title":"J. Comb"},{"key":"S0963548325000094_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2023.105792"},{"key":"S0963548325000094_ref34","first-page":"125","article-title":"Ramsey multiplicity of linear patterns in certain finite abelian groups","volume":"68","author":"Saad","year":"2017","journal-title":"Q. J. Math"},{"key":"S0963548325000094_ref23","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6487"},{"key":"S0963548325000094_ref38","unstructured":"[38] Szegedy, B. (2015) An information theoretic approach to Sidorenko\u2019s conjecture. E-print arXiv:\u00a01406.6738v3."},{"key":"S0963548325000094_ref42","first-page":"53","article-title":"Common and Sidorenko equations in Abelian groups","volume":"14","author":"Versteegen","year":"2023","journal-title":"J. Comb"},{"key":"S0963548325000094_ref28","volume-title":"Large networks and graph limits","volume":"60","author":"Lov\u00e1sz","year":"2012"},{"key":"S0963548325000094_ref15","first-page":"39","article-title":"Ramsey multiplicity and the Tur\u00e1n coloring","volume":"2","author":"Fox","year":"2023","journal-title":"Adv. Comb"},{"key":"S0963548325000094_ref20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000107"},{"key":"S0963548325000094_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-020-4499-9"},{"key":"S0963548325000094_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548322000074"},{"key":"S0963548325000094_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0005-1"},{"key":"S0963548325000094_ref39","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-39.2.246"},{"key":"S0963548325000094_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1475-4"},{"key":"S0963548325000094_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.06.001"},{"key":"S0963548325000094_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2465-x"},{"key":"S0963548325000094_ref8","first-page":"13","article-title":"Sidorenko\u2019s conjecture for blow-ups","volume":"2","author":"Conlon","year":"2021","journal-title":"Discrete Anal."},{"key":"S0963548325000094_ref33","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350785"},{"key":"S0963548325000094_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0097-0"},{"key":"S0963548325000094_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199605)8:3<229::AID-RSA6>3.0.CO;2-#"},{"key":"S0963548325000094_ref16","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1959.11989408"},{"key":"S0963548325000094_ref37","first-page":"72","article-title":"Cycles in graphs and functional inequalities","volume":"46","author":"Sidorenko","year":"104, 1989","journal-title":"Mat. Zametki"},{"key":"S0963548325000094_ref6","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12142"},{"key":"S0963548325000094_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02988307"},{"key":"S0963548325000094_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2017.05.009"},{"key":"S0963548325000094_ref5","first-page":"49","volume-title":"Surveys in combinatorics","volume":"424","author":"Conlon","year":"2015"},{"key":"S0963548325000094_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01300130"},{"volume-title":"Die Grundlehren der mathematischen Wissenschaften","year":"1970","author":"Mitrinovi\u0107","key":"S0963548325000094_ref29"},{"key":"S0963548325000094_ref14","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/haaa068"},{"key":"S0963548325000094_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1625342"},{"key":"S0963548325000094_ref11","first-page":"459","article-title":"On the number of complete subgraphs contained in certain graphs","volume":"7","author":"Erd\u0151s","year":"1962","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T00:12:18Z","timestamp":1757981538000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000094\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,30]]},"references-count":42,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["S0963548325000094"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000094","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2025,6,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}