Linyuan Lincoln Lu's Homepage

Linyuan Lu

	Associate Professor Department of Mathematics University of South Carolina Columbia, SC 29208, USA Office: LC 400I Phone: (803) 576-5822 Fax: (803) 777-3783 Email:

A recent book Try first 3 chapters.	Linyuan Lu (Ph.D., UCSD, 2002) Large information networks, combinatorial probabilistic methods, extremal graph theory, algorithms, computational geometry, computational biology, and Internet computing.

Journal of Combinatorics | USC Combinatorics Seminar

Teaching

No teaching (currently on sabbatical leave)
previous courses archive

Curriculum Vitae | Research | List by AMS | Graph Gallery

Grants: NSF DUE-CCLI-1020692, NSF DMS-1000475, NSF DMS-0701111.

Awards: Prize for Solution to Erdos Problem

Publications

Preprints

(With Xing Peng) On the spectral radius of general random graphs, in preparation.
(With Yong Lin and S.-T. Yau) Ricci-flat graphs with girth at least five, in preparation.
(With Austin Mohr and Laszlo Szekely) Connected Balanced Subgraphs in Random Regular Multigraphs Under the Configuration Model, submitted.
(With Austin Mohr and Laszlo Szekely) Quest for Negative Dependency Graphs, submitted.
(With Jingfen Lan) Diameter of Graphs with Spectral Radius at most ³⁄₂√2, submitted.
(With Laszlo Szekely) A new asymptotic enumeration technique: the Lovasz Local Lemma, preprint.
(With Xing Peng) Loose Laplacian spectra of random hypergraphs , new revision available.
(With Jingfen Lan, Lingsheng Shi) Graphs with Diameter $n-e$ Minimizing the Spectral Radius, submitted.
(With Xing Peng) The fractional chromatic number of triangle-free graphs with maximum degrees at most 3, submitted.

(2011+)

(With Xing Peng) Monochromatic 4-term arithmetic progressions in 2-colorings of Z_n, accepted by J. Combin. Theory Ser. A.
(With Andrew D. King, Xing Peng) A fractional analogue of Brooks' Theorem, accepted by SIAM J. Discrete Math.
(With Jerry Griggs, Wei-Tian Li) Diamond-free Families, accepted by J. Combin. Theory Ser. A.
(With Yong Lin, S.T. Yau) Ricci Curvature of graphs, accepted by Tohoku mathematics journal.
(With Paul Horn and Fan Chung) Diameter of random spanning trees in a given graph, accepted by JGT.
(With Xing Peng) On Meyniel's conjecture of the cop number, to appear in Journal of Graph Theory.
(With Xing Peng) High-ordered Random Walks and Generalized Laplacians on Hypergraphs, Algorithms and Models for the Web-Graph: 8th International Workshop, WAW 2011, Atlanta, GA, USA, May 27-29, 2011, Proceedings. The full version is submitted.
(With Yiting Yang) A theorem on Randic index and the diameter of a graph Discrete Mathematics Volume 311, Issue 14, (2011) 1333-1343.
(With Joshua Cooper) Graphs with Asymptotically Invariant Degree Sequence under Restriction, Internet Mathematics, 7 1, (2011), 67-80.

(2010)

(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.
(With Yiting Yang) A Lower bound of transposition diameter for permutations, SIAM J. Discrete Math. 24 (2010) 1242-1249.

(2009)

(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.
(With Paul Horn and Fan Chung) Percolation in General Graphs, Internet Mathematics, 6 (2009), No. 3, 331-347.
(With Jerry Griggs) On families of subsets with a forbidden subposet, Combinatorics, Probability and Computing, Volume 18, Special Issue 05, (2009), 731-748.
(With Yi Zhao) An exact result and its application on hypergraph Turan numbers, SIAM J. Discrete Math. 23 (2009) 1324-1334.

(2004--2008)

Explicit construction of small Folkman graphs, Siam Journal of Discrete Math, 21 No. 4 (2008), 1053-1060.
(With Szekely)Using Lovasz Local Lemma in the space of random injections, The Electronic Journal of Combinatorics, Volume 14(1) #63 (2007).
(With Reid Andersen and Fan Chung), Drawing power law graphs using a local/global decomposition, Algorithmica 47 (2007), no. 4, 379--397.
(With Fan Chung) Concentration inequalities and martingale inequalities --- a survey , Internet Mathematics, 3 (2006), No. 1, 79-127.
(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.
(With R. Andersen, and Fan Chung) Modeling the small-world Phenomenon with local network flow, Internet Mathematics vol. 2 (2005), No 3, 359-385.
(With Fan Chung) Coupling on-line and off-line analyses for random power law graphs, Internet Mathematics, 1 No. 4, (2004), 409-461.
(With R. Anderson, F. Chung) Drawing power law graph, 12th international symposium on Graph Drawing, NYC, Sept. 29 -Oct. 2, 2004.
(With R. Anderson, F. Chung) 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.
(With Fan Chung) The Small World Phenomenon in Hybrid Power Law Graphs, Lect. Notes Phys., 650, 89-104, (2004).
Fan Chung, Ronald Graham, Linyuan Lu, Guessing Secrets with Inner Product Questions (full paper), Internet Mathematics 1 (2), 2004, 177-192.

(2001--2003)

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.
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.
Fan Chung, Linyuan Lu, and Van Vu, Eigenvalues of random power law graphs, Annals of Combinatorics 7, (2003), 21--33.
Fan Chung, Linyuan Lu, The average distance in random graphs with given expected degrees (full paper), Internet Mathematics 1 (1), 2003, 91-114.
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.
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.
Ke Liang, Zixin Hou, and Linyuan Lu, On sheets of orbit covers for classical semisimple Lie Groups, Sci.
Linyuan Lu. The diameter of random massive graphs, Proceedings of the Twelfth ACM-SIAM Symposium on Discrete Algorithms, (2001), 912--921.
William Aiello, Fan Chung, and Linyuan Lu. Random evolution in massive graphs, Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science, (2001), 510--519.

(before 2000)

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.
Fan Chung and Linyuan Lu, An upper bound for the Turán number t₃(n,4) , J. Combin. Theory Ser. A 87(2), (1999), 381--389.
Zixin Hou and Linyuan Lu. A class of homogeneous semisimple spaces, Chinese Ann. Math. Ser. B 19(3), (1998), 321--330.

Ke Liang and Linyuan Lu. Sheets and rigid orbit covers of exceptional Lie groups, Chinese Sci. Bull. 43(20), (1998), 1702--1706.