Linyuan Lu's Research

Linyuan Lu's research

Curriculum vitae
A $100 Award for solving the Erdos problem on $f(2,3,4) < 10⁶
A book "Complex Graphs and Networks" coauthed with Fan Chung Graham

Papers sorted by research areas

Large information networks

Sang P. Chin, Linyuan Lu, and Elizabeth Reilly, Finding structures in large-scale graphs, In Proceedings of SPIE, vol. 8408, (2012) p. 840805.
Fan Chung and Linyuan Lu, Coupling on-line and off-line analyses for random power law graphs, Internet Mathematics 1 (4), 2005, 409-461.
Reid Andersen, Fan Chung, and Linyuan Lu, Modeling the small-world Phenomenon with local network flow, Internet Mathematics 2 (2005), No 3, 359-385.
Fan Chung and Linyuan Lu, The small world phenomenon in hybrid power law graphs, Lect. Notes Phys. 650 (2004), 89-104.
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.
Ju Wang, Linyuan Lu, and Andrew.~A.~Chien, Tolerating Denial-of-Service Attacks using Overlay Networks - Impact of Overlay Network Topology, First ACM Workshop on Survivable and Self-Regenerative Systems , October 31, 2003, Fairfax, VA.
William Aiello, Fan Chung, and Linyuan Lu, Random evolution in massive graphs, Handbook on Massive Data Sets, (Eds. James Abello et al.), (2001), 97--122. Extended abstract is first published in Proceedings of the Forty-Second Annual Symposium on Foundations of Computer Science, (2001), 510--519.
William Aiello, Fan Chung, and Linyuan Lu, A random graph model for power law graphs, Experiment. Math., 10(1), (2001), 53--66.
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.

Sparse Random graphs

Fan Chung, Linyuan Lu, and Paul Horn, The giant component in a random subgraph of a given graph, Proceedings of WAW2009, Lecture Notes in Computer Science 5427, 38--49.
Fan Chung, Linyuan Lu, and Paul Horn, Diameter of random spanning trees in a given graph, accepted by JGT.
Fan Chung and Linyuan Lu, The volume of the giant component for a random graph with given expected degrees, SIAM J. Discrete Math., 20 (2006), No. 2, 395-411.
Fan Chung and Linyuan Lu, The average distance in random graphs with given expected degrees (full version), 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 and Linyuan Lu, Connected compnents in a random graph with given degree sequences, Annals of Combinatorics 6, (2002), 125--145.
Fan Chung and Linyuan Lu, The diameter of random sparse graphs, Adv. in Appl. Math. 26(4), (2001), 257--279.

Spectral theory on graphs and hypergraphs

Linyuan Lu and Xing Peng, Loose Laplacian spectra of random hypergraphs, submitted.

Linyuan Lu and 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.
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, and Van Vu, Eigenvalues of random power law graphs, Annals of Combinatorics 7, (2003), 21--33.

Ramsey type problems

Linyuan Lu, Xing Peng, Monochromatic 4-term arithmetic progressions in 2-colorings of Z_n, submitted.
Linyuan Lu, Explicit construction of small Folkman graphs, Siam Journal of Discrete Math, 21 No. 4 (2007), 1053-1060.

Graph theory

Andrew King, Linyuan Lu, and Xing Peng, A fractional anology of the Brooks Theorem, submitted.

Linyuan Lu and Xing Peng, The fractional chromatic number of triangle-free graphs with maximum degrees at most 3, submitted.
Jingfen Lan, Linyuan Lu, and Lingsheng Shi, Graphs with Diameter $n-e$ Minimizing the Spectral Radius, submitted.

Linyuan Lu and Xing Peng, On Meyniel's conjecture of the cop number, to appear in Journal of Graph Theory.

Linyuan Lu and Yiting Yang, A theorem on Randic index and the diameter of a graph Discrete Mathematics Volume 311, Issue 14, (2011) 1333-1343.
Wei-Tian Li, Linyuan Lu, and Yiting Yang, Routing numbers of Cycles, Complete Bipartite Graphs, and Hypercubes, SIAM J. Discrete Math. 24, (2010), pp. 1482-1494.
Linyuan Lu and Yiting Yang, A Lower bound of transposition diameter for permutations, SIAM J. Discrete Math. 24 (2010) 1242-1249.

Probabilistic methods

Linyuan Lu and Laszlo Szekely, A new asymptotic enumeration technique: the Lovasz Local Lemma, submitted.

Linyuan Lu, On a problem of Erdos and Lovasz on coloring non-uniform hypergraphs, submitted.
Linyuan Lu and Laszlo Szekely, Using Lovasz Local Lemma in the space of random injections, The Electronic Journal of Combinatorics, Volume 14(1) #63 (2007).
Fan Chung and Linyuan Lu, Concentration inequalities and martingale inequalities --- a survey , Internet Mathematics, 3 (2006), No. 1, 79-127.

Extremal problems on hypergraphs and posets

Jerry Griggs, Wei-Tian Li, and Linyuan Lu, Diamond-free Families, J. Combin. Theory Ser. A 119 (2012) 310-322.
Jerry Griggs and Linyuan Lu, On families of subsets with a forbidden subposet, Combinatorics, Probability and Computing, Volume 18, Special Issue 05, (2009), 731-748.
Linyuan Lu and Yi Zhao, An exact result and its application on hypergraph Turan numbers, SIAM J. Discrete Math. 23 (2009) 1324-1334.
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.

Algorithms

Reid Andersen, Fan Chung, and Linyuan Lu, Drawing power law graphs using a local/global decomposition, Algorithmica 47 (2007), no. 4, 379--397.

Fan Chung, Ronald Graham, and Linyuan Lu, Guessing secrets with inner product questions (full version), Internet Mathematics, 1, no. 2, (2004), 193-217.

Lie groups and differetial geometry

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

Zixin Hou and Linyuan Lu, A class of homogeneous semisimple spaces, Chinese Ann. Math. Ser. B 19(3), (1998), 321--330.
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.

Slides of Recent talks

A series of 5 talks on selected topics on Spectral Graph Theory.
A short course on probablistic methods at the Mathematical Sciences Center of Tsinghua University, China, November 16 - December 30, 2011.
The Giant Component in a Random Subgraph of a Given Graph: an invited one hour talk at Atlanta Lecture Series in Combinatorics \& Graph Theory IV Georgia State University, November 5-6, 2011.
Monochromatic 4-term arithmetic progressions in 2-colorings of Z_n, Integers Conference, Carrollton, GA, October 26-29, 2011.
A series of six 90-minute lectures on complex graphs and networks at a workshop in Guiyang, China, July 27 - August 3, 2008.
Diameter of Random Spanning Trees in a Given Graph at SIAM Annual Meeting, San Diego, CA, July 7-11, 2008.
Probabilistic Methods for Complex Graphs at Center for Combinatorics, Nankai University, Tianjin, China, June 2-5, 2008.
An exact result and its application on hypergraph Turan numbers USC Seminar.
Explicit Construction of Small Folkman Graphs, The 22nd Clemson mini-conference, Clemson University, Clemson, SC, October 11-12, 2007. Also at AMS Spring Central Section Meeting, University of Indiana, Bloomington, IN, April 4-6, 2008.
On Families of Subsets with a Forbidden Subposet, AMS 2007 Central Section Meeting, Chicago, IL, October 5-6, 2007. Also at Mini-Conference on Applied Combinatorics, University of South Carolina, Columbia, SC October 15-16, 2007.
On a Problem of Erdos and Lovasz on Coloring Non-Uniform Hypergraphs, AMS Southeastern Section Meeting, Fayetteville, AR, November 3--4, 2006.
Coloring Non-Uniform Hypergraphs Red and Blue, Combinatorics Seminar at Georgia Institute of Technology, Atlanta, GA, May. 25, 2006.