Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T18:53:24.213Z Has data issue: false hasContentIssue false
  • English
  • Français

Modular Orientations of Random and Quasi-Random Regular Graphs

Published online by Cambridge University Press:  27 January 2011

NOGA ALON  and
PAWEŁ PRAŁAT
NOGA ALON
Affiliation:
Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel and Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: [email protected])
PAWEŁ PRAŁAT
Affiliation:
Department of Mathematics, West Virginia University, Morgantown, WV 26506-6310, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Extending an old conjecture of Tutte, Jaeger conjectured in 1988 that for any fixed integer p ≥ 1, the edges of any 4p-edge connected graph can be oriented so that the difference between the outdegree and the indegree of each vertex is divisible by 2p+1. It is known that it suffices to prove this conjecture for (4p+1)-regular, 4p-edge connected graphs. Here we show that there exists a finite p0 such that for every p > p0 the assertion of the conjecture holds for all (4p+1)-regular graphs that satisfy some mild quasi-random properties, namely, the absolute value of each of their non-trivial eigenvalues is at most c1p2/3 and the neighbourhood of each vertex contains at most c2p3/2 edges, where c1, c2 > 0 are two absolute constants. In particular, this implies that for p > p0 the assertion of the conjecture holds asymptotically almost surely for random (4p+1)-regular graphs.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 20 , Issue 3 , May 2011 , pp. 321 - 329
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N. (1986) Eigenvalues and expanders. Combinatorica 6 83–96.Google Scholar
[2]Alon, N. and Chung, F. R. K. (1988) Explicit construction of linear sized tolerant networks. Discrete Math. 72 15–19.Google Scholar
[3]Alon, N., Krivelevich, M. and Sudakov, B. (2005) MaxCut in H-free graphs. Combin. Probab. Comput. 14 629–647.Google Scholar
[4]Alon, N., Linial, N. and Meshulam, R. (1991) Additive bases of vector spaces over prime fields. J. Combin. Theory Ser. A 57 203–210.CrossRefGoogle Scholar
[5]Alon, N. and Milman, V. D. (1985) λ1, isoperimetric inequalities for graphs and superconcentrators. J. Combin. Theory Ser. B 38 73–88.CrossRefGoogle Scholar
[6]Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, 3rd edition, Wiley.Google Scholar
[7]Bollobás, B. (1980) A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Europ. J. Combin. 1 311–316.Google Scholar
[8]da Silva, C. N. and Dahab, R. (2005) Tutte's 3-flow conjecture and matchings in bipartite graphs. Ars Combin. 76 83–95.Google Scholar
[9]Friedman, J. A proof of Alon's second eigenvalue conjecture. Mem. Amer. Math. Soc., to appear.Google Scholar
[10]Hakimi, S. L. (1965) On the degrees of the vertices of a directed graph. J. Franklin Institute 279 290–308.Google Scholar
[11]Hoory, S., Linial, N. and Wigderson, A. (2006) Expander graphs and their applications. Bull. Amer. Math. Soc. (NS) 43 439–561.Google Scholar
[12]Jaeger, F. (1988) Nowhere-zero flow problems. In Selected Topics in Graph Theory (Beineke, L. et al. , eds), Vol. 3, Academic Press, pp. 91–95.Google Scholar
[13]Lai, H.-J., Shao, Y., Wu, H. and Zhou, J. (2009) On mod(2p+1)-orientations of graphs. J. Combin. Theory Ser. B 99 399–406.Google Scholar
[14]Lai, H.-J. and Zhang, C. Q. (1992) Nowhere-zero 3-flows of highly connected graphs. Discrete Math. 110 179–183.Google Scholar
[15]Nilli, A. (1991) On the second eigenvalue of a graph. Discrete Math. 91 207–210.Google Scholar
[16]Prałat, P. and Wormald, N. In preparation.Google Scholar
[17]Seymour, P. D. (1995) Nowhere-zero flows. In Handbook of Combinatorics, North-Holland, Amsterdam, pp. 289–299.Google Scholar
[18]Sudakov, B. (2001) Nowhere-zero flows in random graphs. J. Combin. Theory Ser. B 81 209–223.Google Scholar
[19]Tutte, W. T. (1966) On the algebraic theory of graph colorings. J. Combin. Theory 1 15–50.Google Scholar
[20]Wormald, N. C. (1999) Models of random regular graphs. In Surveys in Combinatorics 1999 (Lamb, J. D. and Preece, D. A., eds), Vol. 276 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 239–298.Google Scholar