{"entities":{"Q6081372":{"pageid":13215679,"ns":120,"title":"Item:Q6081372","lastrevid":93869906,"modified":"2026-06-05T05:19:29Z","type":"item","id":"Q6081372","labels":{"en":{"language":"en","value":"Bounded cutoff window for the non-backtracking random walk on Ramanujan graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7745880"}},"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":"Q6081372$DD0C7040-CDDB-4BEC-980E-B57D2A025EFA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"989002489db656a9186f2a4b9d82e0fe2d56af6b","datavalue":{"value":{"text":"Bounded cutoff window for the non-backtracking random walk on Ramanujan graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6081372$52F70D14-C2D4-4933-9597-FA435BA69674","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"67a6115f91e87323baf6432e50e77134c5d27184","datavalue":{"value":{"entity-type":"item","numeric-id":6081371,"id":"Q6081371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081372$D65CC148-7606-4225-A9BA-566862ADA5EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2fb3efc1b176c7169f7654b4c46edbc8bd805500","datavalue":{"value":{"entity-type":"item","numeric-id":1061767,"id":"Q1061767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081372$CD31F3E4-2F65-4F43-9DDD-B84AEF4E0809","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081372$5C9016C2-0389-46AF-9382-B6A6BEB62787","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31c936eef8b332040242af2e27eaff5bc37458f1","datavalue":{"value":{"time":"+2023-10-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6081372$F8A9B256-D0D8-4737-9655-007C80AF89DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d0467807be95defe82a18c70f4c4f9315014d427","datavalue":{"value":"https://arxiv.org/abs/2103.15176","type":"string"},"datatype":"url"},"type":"statement","id":"Q6081372$CE74C086-7F8B-43BF-B9FD-DADD57A27449","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e5d2705e1972db2793b14bd5adcece39ad8f59f","datavalue":{"value":"``We prove that the non-backtracking random walk on Ramanujan graphs with large girth exhibits the fastest possible cutoff with a bounded window.''   Let \\(X\\) be a \\(d\\)-regular graph on \\(n\\) vertices without self-loops or multiple edges. The non-backtracking random walk (NBRW) on \\(X\\) mixes faster than the simple random walk, as shown by \\textit{N. Alon} et al. [Commun. Contemp. Math. 9, No 4, 585--603 (2007; Zbl 1140.60301)]. For \\(\\eta \\in (0,1)\\), the total variation distance \\(d(t)\\) between the distribution of the NBRW at time \\(t\\) and the uniform distribution on \\(X\\) is less than \\(\\eta \\) at times \\(t_n \\) of the order of \\( \\log_p n \\) where \\(p = d-1\\). The authors are interested in graphs \\(X\\) for which this \\(t_n\\) is indeed the cutoff time for the NBRW on \\(X\\). The main result shows that the NBRW on a Ramanujan graph \\(X\\) with a large girth exhibits cutoff at \\(\\log_p n\\) with a bounded window. Next, the authors drop the Ramanujan condition and investigate conditions on graphs for cutoff to occur.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081372$1DB96925-6531-4AD6-9684-E56B8BC37F11","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e82054dbe76edf1369718a193428eb5d834d46f2","datavalue":{"value":{"entity-type":"item","numeric-id":580809,"id":"Q580809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081372$5F95357F-E04E-428C-8EA5-96ABB528227F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081372$E5BC2B61-9823-4FF1-BED5-B3960C8A6458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5aff02389d3918a330b0fc4c8d97ee0424df96a7","datavalue":{"value":"20C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081372$FD41BA8E-8B7F-46E0-A13C-0F5B3506E50C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8de4726dadd4d804f8da0a9b26e1822a2c0c7b53","datavalue":{"value":"05E99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081372$CBDE9474-2E2A-42D0-8497-9CDBC4CAE4CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"225c74ca5a5cac6813bd060fc76407571cafe213","datavalue":{"value":"7745880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081372$5C02A4D6-514F-48E3-9711-88FF000E5BBF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64b8e829dbc4a8585f0a0e6ee8c1ef1e4b75a5b8","datavalue":{"value":"non-backtracking random walk","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081372$DC4F86D1-2DEC-4A63-A29D-125E5AEFB851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52de7c482db54da68ab655f9186ae1cdf87630f3","datavalue":{"value":"cutoff","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081372$6392C230-E876-4397-BCBE-409B8EDE7713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96db3a21ba245b613ab80af81387cac56d8ecad3","datavalue":{"value":"window","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081372$FC23928B-4A3D-4CC1-87A1-66C626236458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91374151259bf9db2ea71c4dcb94d5fe11a3527f","datavalue":{"value":"almost diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081372$9F68AB8D-EA19-4477-A640-2223FA557BC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d60950ded64cfa433489bb0caa7f75def7b4e412","datavalue":{"value":"density hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081372$9FDDC808-CDDA-4A01-A3EC-F101D3D0198F","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":"Q6081372$BE99AE64-93EA-48CA-B4B9-9DE0CE5C9F89","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"62d63f7039e384a03fc4576da82ea680b46dcd58","datavalue":{"value":"W3147437636","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081372$42282FAD-8049-4158-B308-2F5D8A257B19","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dcde8fc188c726dbbbcc054c7602d5b7c1956833","datavalue":{"value":"10.1007/S00493-023-00017-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081372$A089979E-0AF1-4F30-ADAE-1DC26DB4E613","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0741fd6b812bd642b95c0d7168c5a7d7801dccbb","datavalue":{"value":{"entity-type":"item","numeric-id":343522,"id":"Q343522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90959548d7e889277ceb2e62a5dd34bf1b763147","datavalue":{"value":{"amount":"+0.8645751476287842","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081372$ED90309D-C731-4907-A31C-41B2EA7F9D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a68c743eaf861775aa1cbbb948ee04244b35221b","datavalue":{"value":{"entity-type":"item","numeric-id":2012250,"id":"Q2012250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e1ed27d532717ffa47bb858dd1c91cce43530a0","datavalue":{"value":{"amount":"+0.8531299829483032","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081372$69A745E8-627D-4CCA-B055-2402175D4A79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3afe2aa968c6d640436f36f0476c79a6b7b14148","datavalue":{"value":{"entity-type":"item","numeric-id":984454,"id":"Q984454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"455f3d1680f652c7e3b931e76dafb3fe5a69aa20","datavalue":{"value":{"amount":"+0.8416717648506165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081372$145C935D-9269-4A26-92AB-F8BE8DFC09D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d92a35684439c161548d39698512f76daab2e76f","datavalue":{"value":{"entity-type":"item","numeric-id":2411767,"id":"Q2411767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"689475dac5ac4c04fed661fd741a4f5ce95a1011","datavalue":{"value":{"amount":"+0.8246639370918274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081372$53A9D99A-5324-48CD-A2A5-D1DF4B2DA276","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2d391b07af6be9124e6d030636fd8fa1b1054e8","datavalue":{"value":{"entity-type":"item","numeric-id":829365,"id":"Q829365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0719750e8ab7ac9d28f6c0065018e8a86620b228","datavalue":{"value":{"amount":"+0.8201899528503418","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6081372$80321685-661D-4BE7-9A4A-FBE4B3D280C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded cutoff window for the non-backtracking random walk on Ramanujan graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_cutoff_window_for_the_non-backtracking_random_walk_on_Ramanujan_graphs"}}}}}