{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T23:39:10Z","timestamp":1769125150083,"version":"3.49.0"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2011,1,27]],"date-time":"2011-01-27T00:00:00Z","timestamp":1296086400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>Extending an old conjecture of Tutte, Jaeger conjectured in 1988 that for any fixed integer <jats:italic>p<\/jats:italic> \u2265 1, the edges of any 4<jats:italic>p<\/jats:italic>-edge connected graph can be oriented so that the difference between the outdegree and the indegree of each vertex is divisible by 2<jats:italic>p<\/jats:italic>+1. It is known that it suffices to prove this conjecture for (4<jats:italic>p<\/jats:italic>+1)-regular, 4<jats:italic>p<\/jats:italic>-edge connected graphs. Here we show that there exists a finite <jats:italic>p<\/jats:italic><jats:sub>0<\/jats:sub> such that for every <jats:italic>p<\/jats:italic> &gt; <jats:italic>p<\/jats:italic><jats:sub>0<\/jats:sub> the assertion of the conjecture holds for all (4<jats:italic>p<\/jats:italic>+1)-regular graphs that satisfy some mild quasi-random properties, namely, the absolute value of each of their non-trivial eigenvalues is at most <jats:italic>c<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>p<\/jats:italic><jats:sup>2\/3<\/jats:sup> and the neighbourhood of each vertex contains at most <jats:italic>c<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>p<\/jats:italic><jats:sup>3\/2<\/jats:sup> edges, where <jats:italic>c<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>c<\/jats:italic><jats:sub>2<\/jats:sub> &gt; 0 are two absolute constants. In particular, this implies that for <jats:italic>p<\/jats:italic> &gt; <jats:italic>p<\/jats:italic><jats:sub>0<\/jats:sub> the assertion of the conjecture holds asymptotically almost surely for random (4<jats:italic>p<\/jats:italic>+1)-regular graphs.<\/jats:p>","DOI":"10.1017\/s0963548310000544","type":"journal-article","created":{"date-parts":[[2011,1,27]],"date-time":"2011-01-27T08:08:34Z","timestamp":1296115714000},"page":"321-329","source":"Crossref","is-referenced-by-count":8,"title":["Modular Orientations of Random and Quasi-Random Regular Graphs"],"prefix":"10.1017","volume":"20","author":[{"given":"NOGA","family":"ALON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PAWE\u0141","family":"PRA\u0141AT","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2011,1,27]]},"reference":[{"key":"S0963548310000544_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"S0963548310000544_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"S0963548310000544_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548310000544_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80004-2"},{"key":"S0963548310000544_ref9","unstructured":"[9] Friedman J. A proof of Alon's second eigenvalue conjecture. Mem. Amer. Math. Soc., to appear."},{"key":"S0963548310000544_ref18","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2007"},{"key":"S0963548310000544_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90112-F"},{"key":"S0963548310000544_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548310000544_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"S0963548310000544_ref8","first-page":"83","article-title":"Tutte's 3-flow conjecture and matchings in bipartite graphs.","volume":"76","author":"da Silva","year":"2005","journal-title":"Ars Combin."},{"key":"S0963548310000544_ref17","first-page":"289","volume-title":"Handbook of Combinatorics","author":"Seymour","year":"1995"},{"key":"S0963548310000544_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007017"},{"key":"S0963548310000544_ref11","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S0963548310000544_ref16","unstructured":"[16] Pra\u0142at P. and Wormald N. In preparation."},{"key":"S0963548310000544_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(65)90340-6"},{"key":"S0963548310000544_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90706-L"},{"key":"S0963548310000544_ref12","first-page":"91","volume-title":"Selected Topics in Graph Theory","author":"Jaeger","year":"1988"},{"key":"S0963548310000544_ref20","first-page":"239","volume-title":"London Mathematical Society Lecture Notes","author":"Wormald","year":"1999"},{"key":"S0963548310000544_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.08.001"},{"key":"S0963548310000544_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(91)90045-I"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000544","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T04:47:02Z","timestamp":1556340422000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000544\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,27]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["S0963548310000544"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000544","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,27]]}}}