{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T09:01:40Z","timestamp":1785402100219,"version":"3.56.0"},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T00:00:00Z","timestamp":1766016000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. Appl. Probab."],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study the bilateral preference graphs\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" content-type=\"simple\" xlink:href=\"S002190022510051X_inline1.png\">\n                          <jats:alt-text content-type=\"machine-generated\">upper L upper K left parenthesis n comma k right parenthesis<\/jats:alt-text>\n                        <\/jats:inline-graphic>\n                        <mml:math xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xmlns:mnf=\"http:\/\/cambridge.org\/core\/manifest\" xmlns:cup=\"http:\/\/contentservices.cambridge.org\" xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" xmlns:m=\"http:\/\/cambridge.org\/core\/metadata\" xmlns:core=\"http:\/\/cambridge.org\/core\" xmlns:c=\"http:\/\/cambridge.org\/core\/content\">\n                          <mml:mrow>\n                            <mml:mi mathvariant=\"italic\" class=\"MJX-tex-mathit\">L<\/mml:mi>\n                            <mml:mi mathvariant=\"italic\" class=\"MJX-tex-mathit\">K<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:mo stretchy=\"false\">(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>,<\/mml:mo>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:mo stretchy=\"false\">)<\/mml:mo>\n                        <\/mml:math>\n                        <jats:tex-math>$\\mathit{LK}(n, k)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of La and Kabkab, obtained as follows. Put independent and uniform [0, 1] weights on the edges of the complete graph\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" content-type=\"simple\" xlink:href=\"S002190022510051X_inline2.png\">\n                          <jats:alt-text content-type=\"machine-generated\">upper K Subscript n<\/jats:alt-text>\n                        <\/jats:inline-graphic>\n                        <mml:math xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xmlns:mnf=\"http:\/\/cambridge.org\/core\/manifest\" xmlns:cup=\"http:\/\/contentservices.cambridge.org\" xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" xmlns:m=\"http:\/\/cambridge.org\/core\/metadata\" xmlns:core=\"http:\/\/cambridge.org\/core\" xmlns:c=\"http:\/\/cambridge.org\/core\/content\">\n                          <mml:msub>\n                            <mml:mi>K<\/mml:mi>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:msub>\n                        <\/mml:math>\n                        <jats:tex-math>$K_n$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Then, each edge (\n                    <jats:italic>i<\/jats:italic>\n                    ,\n                    <jats:italic>j<\/jats:italic>\n                    ) is included in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" content-type=\"simple\" xlink:href=\"S002190022510051X_inline3.png\">\n                          <jats:alt-text content-type=\"machine-generated\">upper L upper K left parenthesis n comma k right parenthesis<\/jats:alt-text>\n                        <\/jats:inline-graphic>\n                        <mml:math xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xmlns:mnf=\"http:\/\/cambridge.org\/core\/manifest\" xmlns:cup=\"http:\/\/contentservices.cambridge.org\" xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" xmlns:m=\"http:\/\/cambridge.org\/core\/metadata\" xmlns:core=\"http:\/\/cambridge.org\/core\" xmlns:c=\"http:\/\/cambridge.org\/core\/content\">\n                          <mml:mrow>\n                            <mml:mi mathvariant=\"italic\" class=\"MJX-tex-mathit\">L<\/mml:mi>\n                            <mml:mi mathvariant=\"italic\" class=\"MJX-tex-mathit\">K<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:mo stretchy=\"false\">(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>,<\/mml:mo>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:mo stretchy=\"false\">)<\/mml:mo>\n                        <\/mml:math>\n                        <jats:tex-math>$\\mathit{LK}(n,k)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    if it is bilaterally preferred, in the sense that it is among the\n                    <jats:italic>k<\/jats:italic>\n                    edges of lowest weight incident to vertex\n                    <jats:italic>i<\/jats:italic>\n                    , and among the\n                    <jats:italic>k<\/jats:italic>\n                    edges of lowest weight incident to vertex\n                    <jats:italic>j<\/jats:italic>\n                    . We show that\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" content-type=\"simple\" xlink:href=\"S002190022510051X_inline4.png\">\n                          <jats:alt-text content-type=\"machine-generated\">k equals log left parenthesis n right parenthesis<\/jats:alt-text>\n                        <\/jats:inline-graphic>\n                        <mml:math xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xmlns:mnf=\"http:\/\/cambridge.org\/core\/manifest\" xmlns:cup=\"http:\/\/contentservices.cambridge.org\" xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" xmlns:m=\"http:\/\/cambridge.org\/core\/metadata\" xmlns:core=\"http:\/\/cambridge.org\/core\" xmlns:c=\"http:\/\/cambridge.org\/core\/content\">\n                          <mml:mi>k<\/mml:mi>\n                          <mml:mo>=<\/mml:mo>\n                          <mml:mi>log<\/mml:mi>\n                          <mml:mo>\u2061<\/mml:mo>\n                          <mml:mo stretchy=\"false\">(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo stretchy=\"false\">)<\/mml:mo>\n                        <\/mml:math>\n                        <jats:tex-math>$k = \\log(n)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is the connectivity threshold, solving a conjecture of La and Kabkab, and obtaining finer results about the window. We also investigate the asymptotic behavior of the average degree of vertices in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" content-type=\"simple\" xlink:href=\"S002190022510051X_inline5.png\">\n                          <jats:alt-text content-type=\"machine-generated\">upper L upper K left parenthesis n comma k right parenthesis<\/jats:alt-text>\n                        <\/jats:inline-graphic>\n                        <mml:math xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xmlns:mnf=\"http:\/\/cambridge.org\/core\/manifest\" xmlns:cup=\"http:\/\/contentservices.cambridge.org\" xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" xmlns:m=\"http:\/\/cambridge.org\/core\/metadata\" xmlns:core=\"http:\/\/cambridge.org\/core\" xmlns:c=\"http:\/\/cambridge.org\/core\/content\">\n                          <mml:mrow>\n                            <mml:mi mathvariant=\"italic\" class=\"MJX-tex-mathit\">L<\/mml:mi>\n                            <mml:mi mathvariant=\"italic\" class=\"MJX-tex-mathit\">K<\/mml:mi>\n                          <\/mml:mrow>\n                          <mml:mo stretchy=\"false\">(<\/mml:mo>\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo>,<\/mml:mo>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:mo stretchy=\"false\">)<\/mml:mo>\n                        <\/mml:math>\n                        <jats:tex-math>$\\mathit{LK}(n, k)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    as\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" content-type=\"simple\" xlink:href=\"S002190022510051X_inline6.png\">\n                          <jats:alt-text content-type=\"machine-generated\">n right arrow normal infinity<\/jats:alt-text>\n                        <\/jats:inline-graphic>\n                        <mml:math xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xmlns:mnf=\"http:\/\/cambridge.org\/core\/manifest\" xmlns:cup=\"http:\/\/contentservices.cambridge.org\" xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" xmlns:m=\"http:\/\/cambridge.org\/core\/metadata\" xmlns:core=\"http:\/\/cambridge.org\/core\" xmlns:c=\"http:\/\/cambridge.org\/core\/content\">\n                          <mml:mi>n<\/mml:mi>\n                          <mml:mo stretchy=\"false\">\u2192<\/mml:mo>\n                          <mml:mi mathvariant=\"normal\">\u221e<\/mml:mi>\n                        <\/mml:math>\n                        <jats:tex-math>$n\\rightarrow\\infty$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    .\n                  <\/jats:p>","DOI":"10.1017\/jpr.2025.10051","type":"journal-article","created":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T10:40:40Z","timestamp":1766054440000},"page":"552-579","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Connectivity of a family of bilateral preference random graphs"],"prefix":"10.1017","volume":"63","author":[{"given":"Hossein","family":"Dabirian","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00jmfr291","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijay","family":"Subramanian","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00jmfr291","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2025,12,18]]},"reference":[{"key":"S002190022510051X_ref1","volume-title":"The Probabilistic Method","author":"Alon","year":"2016"},{"key":"S002190022510051X_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511761942"},{"key":"S002190022510051X_ref11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21180"},{"key":"S002190022510051X_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001711"},{"key":"S002190022510051X_ref13","volume-title":"On Connected Graphs","author":"R\u00e9nyi","year":"1959"},{"key":"S002190022510051X_ref14","doi-asserted-by":"publisher","DOI":"10.1017\/jpr.2022.32"},{"key":"S002190022510051X_ref7","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"S002190022510051X_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/9781316779422"},{"key":"S002190022510051X_ref9","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctvcm4gh1"},{"key":"S002190022510051X_ref6","first-page":"290","article-title":"On random graphs, I","volume":"6","author":"Erd\u0151s","year":"1959","journal-title":"Publ. Math."},{"key":"S002190022510051X_ref12","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"key":"S002190022510051X_ref2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"S002190022510051X_ref4","volume-title":"Epidemics and Rumours in Complex Networks","author":"Draief","year":"2010"},{"key":"S002190022510051X_ref10","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2015.1022626"},{"key":"S002190022510051X_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706098"}],"container-title":["Journal of Applied Probability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002190022510051X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T08:36:31Z","timestamp":1782290191000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002190022510051X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,18]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["S002190022510051X"],"URL":"https:\/\/doi.org\/10.1017\/jpr.2025.10051","relation":{},"ISSN":["0021-9002","1475-6072"],"issn-type":[{"value":"0021-9002","type":"print"},{"value":"1475-6072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,18]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press on behalf of Applied Probability Trust","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}