SpringerLink
Log in

Logarithmic Sobolev, isoperimetry and transport inequalities on graphs

  • Published:
Acta Mathematica Sinica, English Series Aims and scope Submit manuscript

Abstract

In this paper, we study some functional inequalities (such as Poincaré inequality, logarithmic Sobolev inequality, generalized Cheeger isoperimetric inequality, transportation-information inequality and transportation-entropy inequality) for reversible nearest-neighbor Markov processes on connected finite graphs by means of (random) path method. We provide estimates of the involved constants.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alon, N., Milman, V.: λ1, isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory, Ser. B., 38, 73–88 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  2. Barthe, F., Roberto, C.: Sobolev inequalities for probability measures on the real line. Studia Math., 159(3): 481–497 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bobkov, S., Houdré, C.: Some connections between isoperimetric and Sobolev-type inequalities. Mem. Amer. Math. Soc., 129, 1997

    Google Scholar 

  4. Bobkov, S., Götze, F.: Exponential integrability and transportation cost related to logarithmic Sobolev inequalities. J. Funct. Anal., 163, 1–28 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chen, G. Y., Liu, W.-W., Saloff-Coste, L.: The logarithmic Sobolev constant of some finite Markov chains. Ann. Fac. Sci. Toulouse Math., 17(6), 239–290 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chen, G. Y., Sheu, Y. C.: On the log-Sobolev constant for the simple random walk on the n-cycle: the even cases. J. Funct. Anal., 202, 473–485 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chen, M. F.: Analytic proof of dual variational formula for the first eigenvalue in dimension one. Sci. China Ser. A, 42(8), 805–815 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chen, M. F.: Logarithmic Sobolev inequality for symmetric forms. Sci. China Ser. A, 43(6), 601–608 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chen, M. F.: Eigenvalues, Inequalities and Ergodic Theory, Springer, London, 2005

    MATH  Google Scholar 

  10. Chen, M. F., Wang, F. Y.: Cheeger’s inequalities for general symmetric forms and existence criteria for spectral gap. Ann. Probab., 28(1), 235–257 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  11. Chung, F. R. K.: Spectral Graph Theory, CBMS Regional Conference Series in Mathematics, 92, Washington, American Mathematical Society, Providence, RI, 1997

    Google Scholar 

  12. Diaconis, P., Saloff-Coste, L.: Logarithmic Sobolev inequalities for Markov chains. Ann. App. Probab., 6(3), 695–750 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Diaconis, P., Stroock, D.: Geometric bounds for eigenvalues of Markov chains. Ann. App. Probab., 1(1), 36–62 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  14. Donsker, M. D., Varadhan, S. R. S.: Asymptotic evaluation of certain Markov process expectations for large time. IV. Comm. Pure Appl. Math., 18, 183–212 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fill, J.: Eigenvalue bounds on bonvergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. App. Probab., 1(1), 62–87 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gao, F., Quastel, J.: Exponential decay of entropy in the random transposition and Bernoulli–Laplace models. Ann. Appl. Probab., 13, 1591–1600 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  17. Guillin, A., Léonard, C., Wu, L. M., et al.: Transportation-information inequalities for Markov processes. Probab. Th. Relat. Fields, 144, 669–695 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Guillin, A., Joulin, A., Léonard, C., et al.: Transportation-information inequalities for Markov processes (III). Processes with jumps, preprint, (2013)

    Google Scholar 

  19. Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM J. Computer, 18, 1149–1178 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kahale, N.: A semidefinite bound for mixing rates of Markov chains, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, 1084, 1996, 190–203

    MathSciNet  Google Scholar 

  21. Lawler, G. F., Sokal, A. D.: Bounds on the L 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequalities. Trans. Amer. Math. Soc., 309, 557–580 (1988)

    MathSciNet  MATH  Google Scholar 

  22. Lee, T. Y., Yau, H. T.: Logarithmic Sobolev inequality for some models of random walks. Ann. Probab., 26, 1855–1873 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  23. Liu, W., Ma, Y. T., Wu, L. M.: Spectral gap, isoperimetry and concentration on trees. Sci. China Math., 59, 539–556 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  24. Roberto, C.: A path method for the logarithmic Sobolev constant. Combin. Probab. Comput., 12, 431–455 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  25. Rothaus, O.: Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities. J. Funct. Anal., 42 102–109 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  26. Rothaus, O.: Analytic inequalities, isoperimetric inequalities and logarithmic Sobolev inequalities. J. Funct. Anal., 64, 296–313 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  27. Saloff-Coste, L.: Lectures on finite Markov chains, In Lectures on Probability Theory and Statistics: École d’Été de Probabilités de St-Flour, Vol. 1665 of Lecture Notes in Mathematics, Springer, Berlin, 1996

    Google Scholar 

  28. Sammer, M., Tetali, P.: Concentration on the discrete torus using transportation. Combin. Probab. Comput., 18, 835–860 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  29. Sinclair, A.: Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput., 1, 351–370 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  30. Villani, C.: Optimal transport. Old and new. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 338, Springer-Verlag, Berlin, 2009

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences & Lab. Math. Com. Sys., Bei**g Normal University, Bei**g, 100875, P. R. China

    Yu Tao Ma

  2. School of Mathematics and Statistics, Wuhan University, Wuhan, 430072, P. R. China

    Ran Wang

  3. School of Mathematical Sciences, University of Science and Technology of China, Hefei, 230026, P. R. China

    Ran Wang

  4. Institute of Applied Math., Chinese Academy of Sciences, Bei**g, 100190, P. R. China

    Li Ming Wu

  5. Laboratoire de Math. CNRS-UMR 6620, Université Blaise Pascal, 63177, Aubière, France

    Li Ming Wu

Authors
  1. Yu Tao Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ran Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Li Ming Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yu Tao Ma.

Additional information

Supported by NSFC (Grant Nos. 11371283, 11571043, 11301498 and 11431014) and 985 Projects and the Fundamental Research Funds for the Central Universities

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ma, Y.T., Wang, R. & Wu, L.M. Logarithmic Sobolev, isoperimetry and transport inequalities on graphs. Acta. Math. Sin.-English Ser. 32, 1221–1236 (2016). https://doi.org/10.1007/s10114-016-5330-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10114-016-5330-9

Keywords

MR(2010) Subject Classification

Search

Navigation