Factor-of-iid balanced orientation of non-amenable graphs

https://m2.mtmt.hu/ hun 2026-05-01 15:36 JournalArticle 34134348 VALIDATED true Export Date: 11 September 2023 CODEN: EJOCD Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, KKP-133921, KKP-139502 Funding text 1: The authors would like to thank Miklós Abért, Jan Grebík, Matthieu Joseph, Gábor Kun, Gábor Pete, and Václav Rozhoň for inspiring discussions about various parts of this work. The first author was supported by the NKFIH (National Research, Development and Innovation Office, Hungary) grant KKP-133921 , “Structure, chaos and simplification”. The second and third authors were partially supported by the NKFIH grant KKP-139502 , “Groups and graph limits”. 0 false 2026-02-17T12:25:10.930+0000 2023-10-17T11:48:49.546+0000 2023-09-11T10:52:37.424+0000 true 10015168 Szakonyi Erzsebet /api/admin/10015168 Admin Szakonyi Erzsebet (RAMKI admin 4) true 10015168 2025-02-27T12:24:37.473+0000 2025-02-27T12:24:37.473+0000 2023-10-17T11:40:08.819+0000 true 10015168 Szakonyi Erzsebet /api/admin/10015168 Admin Szakonyi Erzsebet (RAMKI admin 4) true 10015168 2023-11-12T12:33:43.901+0000 true 521 Szuper Admin /api/admin/521 Admin Szuper Admin (admin) true Admin 10014568 /api/admin/10014568 Vándor Andrea (VA, admin) Vándor Andrea true 10014568 true 2025-05-12T14:53:19.529+0000 true false true 24 24 /api/publicationtype/24 PublicationType Folyóiratcikk 1 true 24 JournalArticle true 10000059 Article true 24 24 /api/publicationtype/24 PublicationType Folyóiratcikk 1 true 24 JournalArticle /api/subtype/10000059 Szakcikk SubType Szakcikk (Folyóiratcikk) 101 true 10000059 true 1 /api/category/1 Category Tudományos true 1 Bencs, F. Factor-of-iid balanced orientation of non-amenable graphs true true /api/journal/1417130 REVIEWED EUROPEAN JOURNAL OF COMBINATORICS 0195-6698 1095-9971 true false 1417130 false 1417130 true 0195-6698 1095-9971 Journal FOREIGN 115 103784 103784 2024 We show that if a non-amenable, quasi-transitive, unimodular graph G has all degrees even then it has a factor-of-iid balanced orientation, meaning each vertex has equal in- and outdegree. This result involves extending earlier spectral-theoretic results on Bernoulli shifts to the Bernoulli graphings of quasi-transitive, unimodular graphs. As a consequence, we also obtain that when G is regular (of either odd or even degree) and bipartite, it has a factor-of-iid perfect matching. This generalizes a result of Lyons and Nazarov beyond transitive graphs. © 2023 The Author(s) 2023 true true true false false GOLD 2026-02-17 true https://doi.org/10.1016/j.ejc.2023.103784 7 0 1 0 0 1 1 1 1 1 1 0 0 4 3 0 7 4 1 0 0 5 5 Folyóiratcikk Journal Article 24 1 Könyvrészlet Chapter in Book 25 0 Könyv Book 23 0 Egyéb konferenciaközlemény Conference paper 31 0 Egyéb konferenciakötet Conference proceedings 32 0 Oltalmi formák Protection forms 26 0 Disszertáció Thesis 28 2 Egyéb Miscellaneous 29 4 Alkotás Achievement 22 0 Kutatási adat Research data 33 0 Folyóiratcikk Journal Article 24 0 0 0 Könyvrészlet Chapter in Book 25 0 0 0 Könyv Book 23 0 0 0 Egyéb konferenciaközlemény Conference paper 31 0 0 0 Egyéb konferenciakötet Conference proceedings 32 0 0 0 Oltalmi formák Protection forms 26 0 0 0 Disszertáció Thesis 28 0 0 0 Egyéb Miscellaneous 29 0 0 0 Alkotás Achievement 22 0 0 0 Kutatási adat Research data 33 0 0 0 2021 0 1 1 1 1 2022 0 0 0 0 0 2023 0 2 2 2 2 2024 0 1 0 1 0 2025 0 3 1 3 1 D1 false 10076734 false false false 2023-09-10T10:55:07.027+0000 Mesterséges Intelligencia (HRN RAMKI) 3 11 1 3 0 true 10014568 Language 10002 /api/language/10002 Angol Angol English true 2 true PersonAuthorship 109837494 /api/authorship/109837494 Bencs, F. [Bencs, Ferenc (gráfelmélet), szerző] Mesterséges Intelligencia (HRN RAMKI) 1 0.333 true false false Author 10055509 /api/author/10055509 Bencs Ferenc (gráfelmélet) Bencs Ferenc true 10055509 true Bencs F. true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 109837495 /api/authorship/109837495 Hrušková, A. [Hruskova, Aranka (matematika), szerző] Mesterséges Intelligencia (HRN RAMKI) 2 0.333 false false false Author 10087872 /api/author/10087872 Hruskova Aranka (matematika) Hruskova Aranka true true Hrušková A. true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PersonAuthorship 109837496 /api/authorship/109837496 Tóth, László Márton [Tóth, László Márton (csoportelmélet), szerző] 3 0.333 false true false Author 10076734 /api/author/10076734 Tóth László Márton (csoportelmélet) Tóth László Márton true true Tóth László Márton true false false AuthorshipType 1 /api/authorshiptype/1 Szerző 0 true 0 true false true PublicationIdentifier 24358688 /api/publicationidentifier/24358688 DOI: 10.1016/j.ejc.2023.103784 PlainSource 6 /api/publicationsource/6 DOI PublicationSourceType 10001 /api/publicationsourcetype/10001 DOI true true true DOI DOI https://doi.org/@@@ true true 6 true GOLD true IDENTICAL 10.1016/j.ejc.2023.103784 https://doi.org/10.1016/j.ejc.2023.103784 false true PublicationIdentifier 24534366 /api/publicationidentifier/24534366 WoS: 001059514900001 PlainSource 1 /api/publicationsource/1 WoS PublicationSourceType 10003 /api/publicationsourcetype/10003 Indexelő adatbázis false true true WoS WoS https://www.webofscience.com/wos/woscc/full-record/@@@ true true 1 true IDENTICAL 001059514900001 https://www.webofscience.com/wos/woscc/full-record/001059514900001 false true PublicationIdentifier 25384350 /api/publicationidentifier/25384350 REAL: 186622 SwordSource 36 /api/publicationsource/36 REAL PublicationSourceType 10007 /api/publicationsourcetype/10007 Repozitórium true true true REAL REAL http://real.mtak.hu/@@@ true true 36 true GOLD true 186622 http://real.mtak.hu/186622 false true PublicationIdentifier 24358687 /api/publicationidentifier/24358687 Scopus: 85166985897 PlainSource 3 /api/publicationsource/3 Scopus PublicationSourceType 10003 /api/publicationsourcetype/10003 Indexelő adatbázis false true true Scopus Scopus http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-@@@ true true 3 true IDENTICAL 85166985897 http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85166985897 false true Classification 10015 /api/classification/10015 Differenciálegyenletek és dinamikai rendszerek true true Classification 10018 /api/classification/10018 Diszkrét matematika és kombinatorika true true Classification 10004 /api/classification/10004 Elméleti és alkalmazott matematika true true Classification 10029 /api/classification/10029 Statisztika és valószínűség (benne a statisztikai módszerek kutatása; nem tartalmazza az alkalmazott statisztikai módszereket, amik az adott szakterületek - gazdaságtudomány, szociológia, stb. - részeinek tekintendők.) true true Classification 10030 /api/classification/10030 Valószínűség true true SjrRating 11450252 /api/sjrrating/11450252 sjr:D1 (2024) Scopus - Computational Theory and Mathematics EUROPEAN JOURNAL OF COMBINATORICS 0195-6698 1095-9971 16 0.1 journal RatingType 10002 /api/ratingtype/10002 sjr sjr true true ClassificationExternal 1703 /api/classificationexternal/1703 Scopus - Computational Theory and Mathematics true 1703 true D1 DIRECT true true Reference 44945943 /api/reference/44945943 1. Mihail, M., Winkler, P., On the number of Eulerian orientations of a graph (1996) Algorithmica 1 false true Reference 44945944 /api/reference/44945944 2. Lyons, R., Nazarov, F., Perfect matchings as IID factors on non-amenable groups (2011) European J. Combin., 32 (7), pp. 1115-1125 2 false true Reference 44945945 /api/reference/44945945 3. Csóka, E., Lippner, G., Invariant random perfect matchings in Cayley graphs (2017) Groups, Geom., Dyn., 11 (1), pp. 211-244 3 false true Reference 44945946 /api/reference/44945946 4. Thornton, R., Orienting Borel graphs (2022) Proc. Amer. Math. Soc., 150 (4), pp. 1779-1793 4 false true Reference 44945947 /api/reference/44945947 5. Backhausz, Á., Szegedy, B., Virág, B., Ramanujan graphings and correlation decay in local algorithms (2015) Random Struct. Algorithms, 47 (3), pp. 424-435 5 false true Reference 44945948 /api/reference/44945948 6. Kesten, H., Full Banach mean values on countable groups (1959) Math. Scand., pp. 146-156 6 false true Reference 44945938 /api/reference/44945938 7. Lyons, R., Factors of IID on trees (2017) Combin. Probab. Comput., 26 (2), p. 285 7 false true Reference 44945939 /api/reference/44945939 8. Tóth, L.M., Invariant Schreier decorations of unimodular random networks (2021) Ann. Henri Lebesgue, 4, pp. 1705-1726 8 false true Reference 44945940 /api/reference/44945940 9. Bencs, F., Hrušková, A., Tóth, L.M., Factor of iid Schreier decoration of lattices in Euclidean spaces (2021), Preprint 9 false true Reference 44945941 /api/reference/44945941 10. Thornton, R., Factor maps for automorphism groups via Cayley diagrams (2020), arXiv preprint 10 false true Reference 44945942 /api/reference/44945942 11. Schrijver, A., Bounds on the number of Eulerian orientations (1983) Combinatorica, 3 (3-4), pp. 375-380 11 false true Reference 44945949 /api/reference/44945949 12. Balliu, A., Sebastian, B., Efron, Y., Hirvonen, J., Maus, Y., Olivetti, D., Suomela, J., Classification of distributed binary labeling problems (2020) International Symposium on Distributed Computing, , Schloss Dagstuhl–Leibniz-Zentrum für Informatik 12 false true Reference 44945950 /api/reference/44945950 13. Fischer, M., Ghaffari, M., Sublogarithmic distributed algorithms for lovász local lemma, and the complexity hierarchy (2017) 31st International Symposium on Distributed Computing (DISC 2017), , Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik 13 false true Reference 44945951 /api/reference/44945951 14. Kun, G., Expanders have a spanning Lipschitz subgraph with large girth (2013), Preprint 14 false true Reference 44945952 /api/reference/44945952 15. Bernshteyn, A., Measurable versions of the Lovász Local Lemma and measurable graph colorings (2019) Adv. Math., 353, pp. 153-223 15 false true Reference 44945953 /api/reference/44945953 16. Lyons, R., Peres, Y., Probability on Trees and Networks, Vol. 42 (2017), Cambridge University Press 16 false true Reference 44945954 /api/reference/44945954 17. Aldous, D., Lyons, R., Processes on unimodular random networks (2007) Electron. J. Probab., 12, pp. 1454-1508 17 false true Reference 44945955 /api/reference/44945955 18. Lovász, L., Large Networks and Graph Limits, Vol. 60 (2012), American Mathematical Soc 18 false true Reference 44945956 /api/reference/44945956 19. Bowen, M., Kun, G., Sabok, M., Perfect matchings in hyperfinite graphings (2021), arXiv preprint 19 false true Reference 44945957 /api/reference/44945957 20. Pikhurko, O., Borel combinatorics of locally finite graphs (2020), Preprint 20 false true Reference 44945958 /api/reference/44945958 21. Beringer, D., Pete, G., Timár, Á., On percolation critical probabilities and unimodular random graphs (2017) Electron. J. Probab., 22, p. 26 21 false true Reference 44945959 /api/reference/44945959 22. Kowalski, E., An Introduction To Expander Graphs (2019), Société Mathématique de France 22 false true Reference 44945960 /api/reference/44945960 23. Ball, K., Factors of independent and identically distributed processes with non-amenable group actions (2005) Ergodic Theory Dynam. Systems, pp. 711-730 23 false true /api/publication/34134348 Bencs F. et al. Factor-of-iid balanced orientation of non-amenable graphs. (2024) EUROPEAN JOURNAL OF COMBINATORICS 0195-6698 1095-9971 115<div class="JournalArticle Publication long-list"> <div class="authors"> <img title="Forrásközlemény" style="float: left" src="/frontend/resources/grid/publication-core-icon.png"> <img title="Idézőközlemény" style="float: left" src="/frontend/resources/grid/publication-citation-icon.png"> <div class="autype autype0"> <span class="author-name" mtid="10055509"><a href="/gui2/?type=authors&mode=browse&sel=10055509" target="_blank">Bencs F. (<span class="authorship-author-name">Bencs Ferenc</span> <span class="authorAux-mtmt"> gráfelmélet</span>) </a> </span> <span class="author-affil"><span title="HUN-REN Rényi Alfréd Matematikai Kutatóintézet">HRN RAMKI</span>/Mesterséges Intelligencia</span> ;    <span class="author-name" mtid="10087872"><a href="/gui2/?type=authors&mode=browse&sel=10087872" target="_blank">Hrušková A. (<span class="authorship-author-name">Hruskova Aranka</span> <span class="authorAux-mtmt"> matematika</span>) </a> </span> <span class="author-affil"><span title="HUN-REN Rényi Alfréd Matematikai Kutatóintézet">HRN RAMKI</span>/Mesterséges Intelligencia</span> ;    <span class="author-name" mtid="10076734"><a href="/gui2/?type=authors&mode=browse&sel=10076734" target="_blank">Tóth László Márton (<span class="authorship-author-name">Tóth László Márton</span> <span class="authorAux-mtmt"> csoportelmélet</span>) </a> </span> </div> </div> <div class="title"><a href="/gui2/?mode=browse&params=publication;34134348" target="_blank">Factor-of-iid balanced orientation of non-amenable graphs</a></div> <div> <span class="journal-title">EUROPEAN JOURNAL OF COMBINATORICS</span> <span class="journal-issn">(<a target="_blank" href="https://portal.issn.org/resource/ISSN/0195-6698">0195-6698</a> <a target="_blank" href="https://portal.issn.org/resource/ISSN/1095-9971">1095-9971</a>)</span>: <span class="journal-volume">115</span> <span class="page"> Paper 103784. </span> <span class="year">(2024)</span> </div> <div class="pub-footer"> <span class="language" xmlns="http://www.w3.org/1999/html">Nyelv: Angol | </span> <span class="identifiers"> <span class="id identifier oa_GOLD" title=" Gold "> <a style="color:blue" title="10.1016/j.ejc.2023.103784" target="_blank" href="https://doi.org/10.1016/j.ejc.2023.103784"> DOI </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="001059514900001" target="_blank" href="https://www.webofscience.com/wos/woscc/full-record/001059514900001"> WoS </a> </span> <span class="id identifier oa_GOLD" title=" Gold "> <a style="color:black" title="186622" target="_blank" href="http://real.mtak.hu/186622"> REAL </a> </span> <span class="id identifier oa_none" title="none"> <a style="color:blue" title="85166985897" target="_blank" href="http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85166985897"> Scopus </a> </span> </span> <OnlyViewableByAuthor><div class="ratings"> <div class="journal-subject">Folyóirat szakterülete: Scopus - Computational Theory and Mathematics   SJR indikátor: D1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Discrete Mathematics and Combinatorics   SJR indikátor: D1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Geometry and Topology   SJR indikátor: D1</div> <div class="journal-subject">Folyóirat szakterülete: Scopus - Theoretical Computer Science   SJR indikátor: Q1</div> </div></OnlyViewableByAuthor> <div class="publication-citation" style="margin-left: 0.5cm;"> <span title="Nyilvános idézőközlemények összesen, említések nélkül" class="citingPub-count">Nyilvános idéző összesen: 7</span> | Független: 4 | Függő: 3 | Nem jelölt: 0 | WoS jelölt: 1 | Scopus jelölt: 1 | WoS/Scopus jelölt: 1 | DOI jelölt: 1 </div> <div class="publication-citation"> <a target="_blank" href="/api/publication?cond=citations.related;eq;34134348&sort=publishedYear,desc&sort=title"> Idézett közlemények száma: 5 </a> </div> <div class="mtid"><span class="long-pub-mtid">Közlemény: 34134348</span> | <span class="status-data status-VALIDATED"> Egyeztetett </span> Forrás Idéző | <span class="type-subtype">Folyóiratcikk ( Szakcikk ) </span> | <span class="pub-category">Tudományos</span> | <span class="publication-sourceOfData">Scopus</span> </div> <div class="notDuplums"><a target="_blank" href="/api/publication/34134348/notduplums">1 Nem duplumnak jelölés</a> </div> <div class="lastModified">Utolsó módosítás: 2023.10.17. 13:48 Szakonyi Erzsebet (RAMKI admin 4) </div> <div class="lockedBy">Központi kezelésű 2025.05.12. 16:53 Vándor Andrea (VA, admin) </div> <pre class="comment" style="margin-top: 0; margin-bottom: 0;"><u>Megjegyzés</u>: Export Date: 11 September 2023 CODEN: EJOCD Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH, KKP-133921, KKP-139502 Funding text 1: The authors would like to thank Miklós Abért, Jan Grebík, Matthieu Joseph, Gábor Kun, Gábor Pete, and Václav Rozhoň for inspiring discussions about various parts of t...</pre> </div></div>