{"entities":{"Q2111926":{"pageid":2122669,"ns":120,"title":"Item:Q2111926","lastrevid":42176591,"modified":"2025-05-27T11:18:32Z","type":"item","id":"Q2111926","labels":{"en":{"language":"en","value":"Connectivity of friends-and-strangers graphs on random pairs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7643136"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$FCA441C3-DC69-47DD-8B65-C5599E484FB9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"591af65bd93fd7641d9b0456d5dd37d19c507719","datavalue":{"value":{"text":"Connectivity of friends-and-strangers graphs on random pairs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2111926$459432AA-386A-405B-A165-46EE9F24898E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"070f6b043d57ccce2a782a88e104a98aac2a11be","datavalue":{"value":{"entity-type":"item","numeric-id":2111925,"id":"Q2111925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$8E8FB36A-8370-4CA9-B156-A412E1F9672E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95bc2c100151014de97828713c6ba612127193cf","datavalue":{"value":{"entity-type":"item","numeric-id":186274,"id":"Q186274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$EC5A86BB-6EBE-42EA-89E2-131D08A99653","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$3D369F27-7D0F-45B8-80B9-CCE66987D633","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"957af406b21c0dd147c281b56551aa32e3ad16a3","datavalue":{"value":{"time":"+2023-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2111926$38D0C99F-A76F-427B-A710-A69137C826F9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"98d6676f1992a8204590b5412e883df85a4748b0","datavalue":{"value":"https://arxiv.org/abs/2208.00801","type":"string"},"datatype":"url"},"type":"statement","id":"Q2111926$1308ED32-9B29-41F9-8112-F4605478945E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"13399465b4fab189cc2cbbc191850907c1538045","datavalue":{"value":"Consider \\(n\\) people being placed in \\(n\\) positions. A move consists in exchanging the positions of two people, but it is valid only if they are friends, and in adjacent positions. If \\(X\\) denotes the ``friendship graph'', and \\(Y\\) denotes the graph modeling the positions, then the friends-and-strangers graph \\(\\mathrm{FS}(X,Y)\\) is the graph whose vertices are the possible configurations of people (i.e.\\ bijections \\(\\sigma:V(X)\\to V(Y)\\)) and whose edges are the valid moves between them.  The article shows that \\(\\mathrm{FS}(X,Y)\\) is connected with high probability if \\(X\\) and \\(Y\\) are independent Erd\u0151s-R\u00e9nyi graphs \\(X\\sim \\mathcal{G}(n,p_1)\\), \\(Y\\sim \\mathcal{G}(n,p_2)\\), with \\(p_1p_2 \\geq p_0^2\\) and \\(\\min(p_1,p_2)\\geq 2p_0 / (\\log n)^{1/3}\\), where \\(p_0=\\exp(2(\\log n)^{2/3})/n^{1/2}\\). This result extends the symmetric case \\(p_1=p_2\\) which was studied by \\textit{N. Alon} et al. [J. Comb. Theory, Ser. B 158, Part 1, 3--42 (2023; Zbl 1504.05146)].  The idea is to prove that with high probability, for every pair of vertices \\(u,v\\in V(Y)\\) and every bijection \\(\\sigma:V(X)\\to V(Y)\\), there exists a finite sequence of valid moves from \\(\\sigma\\) to \\(\\tau_{uv}\\circ\\sigma\\), where \\(\\tau_{uv}\\) is the transposition of \\(u\\) and \\(v\\). To show this, the authors show that with high probability one can embed two specific small sparse graphs \\(G^\\ast\\) and \\(H^\\ast\\) in \\(X\\) and \\(Y\\), whose structures ensure us that \\(u\\) and \\(v\\) can be exchanged from any \\(\\sigma\\), in the sense described above.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2111926$D38EDED7-413C-4DE4-AA61-444443B4800A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9475d262ec55242fd2469ab2c99e8e63adbb04ff","datavalue":{"value":{"entity-type":"item","numeric-id":1617122,"id":"Q1617122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$9ACF1C47-3DD6-4098-BB59-366EC6EF0AA9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111926$9A535E00-1AD2-48B5-846B-0A7CFDF84778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111926$6F9880FE-FED9-4E77-9867-3C09CCBADDCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111926$FCFA4E2D-3419-4632-8288-691CA39FF565","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"86f1da722a6a79aa43e4dd64dddc3134595adeba","datavalue":{"value":"7643136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111926$EA55312A-2E79-43C7-A9FE-4FC15253DD9D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2111926$5C3FE22E-3E34-4BB9-A4EF-8848A78B50FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68199b9563768a578126812eda3086c160af262d","datavalue":{"value":"friends-and-strangers graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2111926$74522117-1B75-44D5-8750-EA65300CCA85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2111926$39066B53-5E33-409F-B101-11D68AF53B04","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$CC86E3F9-7BE9-4131-A4DA-431A89B0C2FA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"80b04f350bc1d1c5c7769ccf1f3b3e488452ba79","datavalue":{"value":"W4309734294","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111926$FB4A4EFB-5BC6-4A61-BCA6-FFAC128E2B73","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be671db4219eebd2c9dbca53851b55fa9756f98a","datavalue":{"value":{"entity-type":"item","numeric-id":2099406,"id":"Q2099406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$619D1A02-1B05-4D28-99D4-88FD11724706","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$29199C0C-1A85-47E2-9ADF-FC1BB82AE3A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"321aecce83510cedb73119114762afbcd667422e","datavalue":{"value":{"entity-type":"item","numeric-id":2143395,"id":"Q2143395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$C5E0F881-3528-452F-84D3-009BA4BE23D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"406ed5fc1829b79c7d5ef3d8c3f7732bf2df0aae","datavalue":{"value":{"entity-type":"item","numeric-id":1846887,"id":"Q1846887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$067C3F14-AA68-49AB-AC14-A8B672C5E3F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca1f16496e0b934b2e2f104b858e14c68d55fdcb","datavalue":{"value":{"entity-type":"item","numeric-id":5048443,"id":"Q5048443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$4A26887C-668B-49BF-8EB3-23DEB847687C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d27dacc5c86087ff2495c99b8279b01d00250f","datavalue":{"value":{"entity-type":"item","numeric-id":2716030,"id":"Q2716030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$C9240477-47FD-4324-B522-04434CB7BF8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb6635157d46ee699421ac79239513d8a4715c8c","datavalue":{"value":{"entity-type":"item","numeric-id":754889,"id":"Q754889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$A2998DEF-0DAA-4F3C-9569-8ADBED374735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0fb4f4fb686ff9995b8a241b68264c1a7fd1b92","datavalue":{"value":{"entity-type":"item","numeric-id":1844853,"id":"Q1844853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2111926$FA2FA575-2BD9-4751-8564-8463242A7F63","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6dd025f7934971bea51626456f8fc945883f7284","datavalue":{"value":"10.1016/J.DISC.2022.113266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2111926$9F4AF0F8-48B0-4A62-8B12-8FFC2ED40A6F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eab73a00f1708a537d84d41607a2dcb0121f7e1d","datavalue":{"value":{"entity-type":"item","numeric-id":2099406,"id":"Q2099406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b429bbd3f6812e96d7cbb670609a3bc45c58399f","datavalue":{"value":{"amount":"+0.824276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$AFA4AD1D-6683-4682-92BF-EF56A123D25C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79414807855a439f28d56d3aecd12f0d2e1c8664","datavalue":{"value":{"entity-type":"item","numeric-id":2143395,"id":"Q2143395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03cc5fbee4aa25bf5ddf850acdc2993247565fb4","datavalue":{"value":{"amount":"+0.768376","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$EE5A42FC-D423-47C9-8D4D-73B9CF31B9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b69a8bd0d97384ec3301ac22ad403358615693b","datavalue":{"value":{"entity-type":"item","numeric-id":2680899,"id":"Q2680899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c75914a0e5db304d15a8b65d1fae87d6e388606","datavalue":{"value":{"amount":"+0.7507838","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$99CDC4BA-B1E8-4A52-8361-D54C784145FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c388161b64fd674e4b31c4639798ce062e9c684","datavalue":{"value":{"entity-type":"item","numeric-id":4885227,"id":"Q4885227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"496447b7a7910ad87e3aabd618255f59f2f1486f","datavalue":{"value":{"amount":"+0.74804914","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$C93C6FF9-A63A-466E-B579-88D9FF1B4365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b9443b0644c87e692e916cc1c6ea3aeaadb240e","datavalue":{"value":{"entity-type":"item","numeric-id":6041578,"id":"Q6041578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff54466621928584ae0ea45955ca25df41f42442","datavalue":{"value":{"amount":"+0.74083304","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$7493413D-91CA-4E1B-A7BD-7F1AB2F5DF1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb1df56882f68ff551b0da8f6878927dde098f34","datavalue":{"value":{"entity-type":"item","numeric-id":4583882,"id":"Q4583882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e84f72813ce8a7bd36f3e9ea4d27f5156f6d112","datavalue":{"value":{"amount":"+0.71452636","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$46FA9732-8D11-4C5A-BDD8-1AE6B4403EC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb942cbeac0ce7f56d93edc77ae56fb1fbc29f0c","datavalue":{"value":{"entity-type":"item","numeric-id":2818476,"id":"Q2818476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9242c1a0368b10c4a90e52124d9a4c7a5435a806","datavalue":{"value":{"amount":"+0.7053735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$D0848607-06C9-426D-8E8A-879DDDEE7224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f54863776be5ae93e2c12f668a64a5d63b19f285","datavalue":{"value":{"entity-type":"item","numeric-id":3203053,"id":"Q3203053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6aadce7c4cf065a839e67360a2b310c9ee1a2c62","datavalue":{"value":{"amount":"+0.70396435","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2111926$31AF012E-332D-4AAB-8491-1F4B3E3C44EF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2111926","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2111926"}}}}}