Linyuan Lu

Professor
Department of Mathematics
University of South Carolina
Columbia, SC 29208, USA

Office: LC 400I
Phone: (803) 576-5822
Fax:   (803) 777-3783
Email:


Linyuan Lu  (Ph.D., UCSD, 2002)
Large information networks, probabilistic methods, spectral graph theory, random graphs, extremal problems on hypergraphs and posets, algorithms, and graph theory.

Journal of Combinatorics      |     USC Combinatorics Seminar

Curriculum Vitae  |   Research  |   Papers on MathScinet  |   Graph Gallery

Grants: NSF DMS-1600811, NSF DMS-1300547, ONR N00014-13-1-0717, NSF DUE-CCLI-1020692, NSF DMS-1000475, NSF DMS-0701111.
Awards: Prize for Solution to Erdos Problem

Publications

Preprints

  1. (With Arthur L.B. Yang) A combinatorial identity on Galton-Watson process, submitted.
  2. (With Richard P. Anstee) Unavoidable Multicoloured Families of Configurations, submitted.
  3. (With Shoudong Man) Connected Hypergraphs with Small Spectral Radius, Linear Algebra and its Application, 509, (2016), 206-227.
  4. (With Travis Johnston) Strong Jumps and Lagrangians of Nono-Uniform Hypergraphs, submitted.
  5. (With Xing Peng) High Order Phase Transition in Random Hypergrpahs, in preprint.

    (2015+)

  6. (With Kevin G. Milans) Set families with forbidden subposets, J. Combin. Theory Ser. A., to appear.
  7. (With Travis Johnston and Kevin Milans) Boolean algebras and Lubell functions, J. Combin. Theory Ser. A., to appear
  8. (With Laszlo Szekely) A new asymptotic enumeration technique: the Lovasz Local Lemma, J. Combin. Theory Ser., to appear.
  9. (2014)

  10. (With Travis Johnston) Turan Problems on Non-uniform Hypergraphs, Electronic Journal of Combinatorics, 21 (4), (2014), P22.
  11. (With Edward Boehnlein, Peter Chin, and Amit Sinha) Computing Diffusion State Distance using Green's Function and Heat Kernel on Graphs, accepted by the 11th Workshop on Algorithms and Models for the Web Graph, WAW2014.
  12. On crown-free families of subsets, J. Combin. Theory Ser. A., 126, (2014), Pages 216-231.
  13. (With Yong Lin and S.-T. Yau) Ricci-flat graphs with girth at least five, to appear in Communications in Analysis and Geometry.
  14. (With Steve Butler and Ron Graham) Unrolling residues to avoid progressions, Math. Mag. 87 (2014) 83-94.

    (2013)

  15. (With Xing Peng) Spectra of edge-independent random graphs, Electronic Journal of Combinatorics, 20 (4), (2013) P27.
  16. (With Richard Anstee) Repeated columns and an old chestnut, Electronic Journal of Combinatorics, 20 (4), (2013) P2.
  17. (With Jingfen Lan) Diameter of Graphs with Spectral Radius at most 322, Linear Algebra and its Application, 438, No. 11, (2013), 4382-4407.
  18. (With Austin Mohr and Laszlo Szekely) Connected Balanced Subgraphs in Random Regular Multigraphs Under the Configuration Model, accepted by JCMCC.
  19. (With Xing Peng) High-ordered Random Walks and Generalized Laplacians on Hypergraphs, Internet Mathematics, 9, No. 1, (2013) 3-32.

    (2012)

  20. (With Austin Mohr and Laszlo Szekely) Quest for Negative Dependency Graphs, in Recent Advances in Harmonic Analysis and Applications: In Honor of Konstantin Oskolkov (Eds. D. Bilyk, L. DeCarli, A. Petukhov, A. M. Stokolos, B. D. Wick) Springer Proceedings in Mathematics & Statistics, (2012), 243-258.
  21. (With Xing Peng) The fractional chromatic number of triangle-free graphs with maximum degrees at most 3, Discrete Mathematics 312, No. 24, (2012), 3502-3516.
  22. (With Jingfen Lan, Lingsheng Shi) Graphs with Diameter $n-e$ Minimizing the Spectral Radius, Linear Algebra and its Applications , 437, No. 11, (2012), 2823-2850.
  23. (With Xing Peng) Loose Laplacian spectra of random hypergraphs , Random Structures & Algorithms, 41 No. 4, (2012), 521-545.
  24. (With Sang P. Chin and Elizabeth Reilly) Finding structures in large-scale graphs, In Proceedings of SPIE, vol. 8408, (2012) p. 840805.
  25. (With Xing Peng) Monochromatic 4-term arithmetic progressions in 2-colorings of Zn, J. Combin. Theory Ser. A., 119 No. 5, (2012), 1048-1065.
  26. (With Andrew D. King, Xing Peng) A fractional analogue of Brooks' Theorem, SIAM J. Discrete Math. 26, No. 2, 452-471.
  27. (With Xing Peng) On Meyniel's conjecture of the cop number, Journal of Graph Theory, 71, No. 2, (2012),192-205.
  28. (With Jerry Griggs, Wei-Tian Li) Diamond-free Families, J. Combin. Theory Ser. A. 119 (2012) 310-322.
  29. (With Paul Horn and Fan Chung) Diameter of random spanning trees in a given graph, Journal of Graph Theory, 69 No.3 (2012), 223-240.

    (2011)

  30. (With Yong Lin, S.T. Yau) Ricci Curvature of graphs, Tohoku mathematics journal, 63 No. 4, (2011), 605-627.
  31. (With Xing Peng) High-ordered Random Walks and Generalized Laplacians on Hypergraphs (exended abstract), Algorithms and Models for the Web-Graph: 8th International Workshop, WAW 2011, Atlanta, GA, USA, May 27-29, 2011, Proceedings.
  32. (With Yiting Yang) A theorem on Randic index and the diameter of a graph Discrete Mathematics Volume 311, Issue 14, (2011) 1333-1343.
  33. (With Joshua Cooper) Graphs with Asymptotically Invariant Degree Sequence under Restriction, Internet Mathematics, 7 1, (2011), 67-80.

    (2010)

  34. (With Wei-Tian Li and Yiting Yang) Routing numbers of Cycles, Complete Bipartite Graphs, and Hypercubes, SIAM J. Discrete Math. 24, (2010), pp. 1482-1494.
  35. (With Yiting Yang) A Lower bound of transposition diameter for permutations, SIAM J. Discrete Math. 24 (2010) 1242-1249.

    (2009)

  36. (With Paul Horn and Fan Chung) The giant component in a random subgraph of a given graph, Proceedings of WAW2009, Lecture Notes in Computer Science 5427, 38--49.
  37. (With Paul Horn and Fan Chung) Percolation in General Graphs, Internet Mathematics, 6 (2009), No. 3, 331-347.
  38. (With Jerry Griggs) On families of subsets with a forbidden subposet, Combinatorics, Probability and Computing, Volume 18, Special Issue 05, (2009), 731-748.
  39. (With Yi Zhao) An exact result and its application on hypergraph Turan numbers, SIAM J. Discrete Math. 23 (2009) 1324-1334.

    (2004--2008)

  40. Explicit construction of small Folkman graphs, Siam Journal of Discrete Math, 21 No. 4 (2008), 1053-1060.
  41. (With Szekely)Using Lovasz Local Lemma in the space of random injections, The Electronic Journal of Combinatorics, Volume 14(1) #63 (2007).
  42. (With Reid Andersen and Fan Chung), Drawing power law graphs using a local/global decomposition, Algorithmica 47 (2007), no. 4, 379--397.
  43. (With Fan Chung) Concentration inequalities and martingale inequalities --- a survey , Internet Mathematics, 3 (2006), No. 1, 79-127.
  44. (With Fan Chung) The volume of the giant component for a random graph with given expected degrees, SIAM J. Discrete Math., 20 (2006), No. 2, 395-411.
  45. Reid Andersen, Fan Chung, and Linyuan Lu, Modeling the small-world Phenomenon with local network flow, Internet Mathematics vol. 2 (2005), No 3, 359-385.
  46. Reid Anderson, Fan Chung, and Linyuan Lu, Drawing power law graph, (extended abstract), in Graph Drawing, Lecture Notes in Computer Science 3383, (2005), 12-17.
  47. Fan Chung and Linyuan Lu, Coupling on-line and off-line analyses for random power law graphs, Internet Mathematics, 1 No. 4, (2004), 409-461.
  48. Reid Anderson, Fan Chung, and Linyuan Lu Analyzing the small world phenomenon using a hybrid model with local network flow, Third Workshop on Algorithms and Models for the Web-Graph (WAW 2004), October 2004 Rome, Italy.
  49. (With Fan Chung) The Small World Phenomenon in Hybrid Power Law Graphs, Lect. Notes Phys., 650, 89-104, (2004).
  50. Fan Chung, Ronald Graham, Linyuan Lu, Guessing Secrets with Inner Product Questions (full paper), Internet Mathematics 1 (2), 2004, 177-192.

    (2001--2003)

  51. Fan Chung, Linyuan Lu, and Van Vu, The spectra of random graphs with given expected degrees, Proceedings of National Academy of Science, 100, No. 11, (2003), 6313-6318.
  52. Fan Chung, Linyuan Lu, Gregory Dewey, and David J. Galas. Duplication models for biological networks, Journal of Computational Biology, 10, No. 5 (2003), 677-688.
  53. Fan Chung, Linyuan Lu, and Van Vu, Eigenvalues of random power law graphs, Annals of Combinatorics 7, (2003), 21--33.
  54. Ju Wang, Linyuan Lu and Andrew. A. Chien, Tolerating denial-of-service attacks using overlay networks - Impact of overlay network topology, Proceedings of the 2003 ACM workshop on Survivable and self-regenerative systems: in association with 10th ACM Conference on Computer and Communications Security, (2003), 43-52.
  55. Fan Chung, Linyuan Lu, The average distance in random graphs with given expected degrees (full paper), Internet Mathematics 1 (1), 2003, 91-114.
  56. Fan Chung and Linyuan Lu. Connected components in a random graph with given degree sequences, Annals of Combinatorics, 6 (2002), 125-145.
  57. Fan Chung and Linyuan Lu The average distance in random graphs with given expected degrees, Proceedings of National Academy of Science, 99 (2002), 15879-15882.
  58. Fan Chung, Ronald Graham, and Linyuan Lu. Guessing secrets with inner product questions (extended abstract), Proceedings of the Thirteenth ACM-SIAM Symposium on Discrete Algorithms, (2002), 247--253.
  59. Ke Liang, Zixin Hou, and Linyuan Lu, On sheets of orbit covers for classical semisimple Lie Groups, Sci. China Ser. A, 45(2), (2002), 155-164.
  60. Linyuan Lu. The diameter of random massive graphs, Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms, (2001), 912--921.
  61. William Aiello, Fan Chung, and Linyuan Lu. Random evolution in massive graphs (extended abstract), Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science, (2001), 510--519.
  62. Fan Chung and Linyuan Lu. The diameter of random sparse graphs, Adv. in Appl. Math. 26 (2001), 257-279.

    (before 2000)

  63. William Aiello, Fan Chung, and Linyuan Lu. A random graph model for power law graphs, Experiment. Math. 10(1), (2000), 53-66.
  64. William Aiello, Fan Chung, and Linyuan Lu. A random graph model for massive graphs, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, (2000), 171--180.
  65. Fan Chung and Linyuan Lu, An upper bound for the Turán number t3(n,4) , J. Combin. Theory Ser. A 87(2), (1999), 381--389.
  66. Zixin Hou and Linyuan Lu. A class of homogeneous semisimple spaces, Chinese Ann. Math. Ser. B 19(3), (1998), 321--330.
  67. Ke Liang and Linyuan Lu. Sheets and rigid orbit covers of exceptional Lie groups, Chinese Sci. Bull. 43(20), (1998), 1702--1706.