Linyuan Lu's Research

Linyuan Lu's research

Curriculum vitae
Research statement
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

Selected papers sorted by research areas

Large information networks

Fan Chung, 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 vol. 2 (2005), No 3, 359-385.
Fan Chung, 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.
Fan Chung, Linyuan Lu, and Van Vu, Eigenvalues of random power law graphs, Annals of Combinatorics 7, (2003), 21--33.
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, Paul Horn, The giant component in a random subgraph of a given graph, submitted.
Fan Chung, Linyuan Lu, Paul Horn, Diameter of random spanning trees in a given graph, submitted.
Fan Chung, 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, Linyuan Lu, The average distance in random graphs with given expected degrees (full version), Internet Mathematics 1 (1), 2003, 91-114.
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 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.

Probabilistic methods

Linyuan Lu, On a problem of Erdos and Lovasz on coloring non-uniform hypergraphs, submitted.
Linyuan Lu, Laszlo Szekely, Using Lovasz Local Lemma in the space of random injections, The Electronic Journal of Combinatorics, Volume 14(1) #63 (2007).
Fan Chung, 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, Linyuan Lu On families of subsets with a forbidden subposet, submitted.
Linyuan Lu, Yi Zhao, An exact result and its application on hypergraph Turan numbers, submitted.
Linyuan Lu, Explicit construction of small Folkman graphs, Siam Journal of Discrete Math, 21 No. 4 (2007), 1053-1060.
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 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.

Linyuan Lu's full publication list

A book

Fan Chung and Linyuan Lu, Complex graphs and networks, CBMS Regional Conference Series in Mathematics; number 107, (2006), 264+vii pages. ISBN-10: 0-8218-3657-9, ISBN-13: 978-0-8218-3657-6.

Journal papers and recent papers

Fan Chung, Linyuan Lu, Paul Horn The giant component in a random subgraph of a given graph, submitted.
Josh Cooper, Linyuan Lu, Graphs with scale-free sequence, submitted.
Fan Chung, Linyuan Lu, Paul Horn, Diameter of random spanning trees in a given graph, submitted.
Jerry Griggs, Linyuan Lu On families of subsets with a forbidden subposet, submitted.
Linyuan Lu, Yi Zhao, An exact result and its application on hypergraph Turan numbers, submitted.
Linyuan Lu, On a problem of Erdos and Lovasz on coloring non-uniform hypergraphs, submitted.
Linyuan Lu, Explicit construction of small Folkman graphs, Siam Journal of Discrete Math, 21 No. 4 (2007), 1053-1060.
Linyuan Lu, Laszlo Szekely, Using Lovasz Local Lemma in the space of random injections, The Electronic Journal of Combinatorics, Volume 14(1) #63 (2007).
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, Linyuan Lu Concentration inequalities and martingale inequalities --- a survey , Internet Mathematics, 3 (2006), No. 1, 79-127.
Fan Chung, 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.
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.
Fan Chung, Linyuan Lu, Coupling on-line and off-line analyses for random power law graphs, Internet Mathematics 1 (4), 2005, 409-461.
Fan Chung, Linyuan Lu, The small world phenomenon in hybrid power law graphs, Lect. Notes Phys. 650 (2004), 89-104.
Fan Chung, Ronald Graham, and Linyuan Lu. Guessing secrets with inner product questions (full version), Internet Mathematics, 1, no. 2, (2004), 193-217.
Fan Chung, Linyuan Lu, The average distance in random graphs with given expected degrees (full version), Internet Mathematics 1 (1), 2003, 91-114.
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 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, An upper bound for the Turán number t₃(n,4) , J. Combin. Theory Ser. A 87(2), (1999), 381--389.

Fan Chung and Linyuan Lu. The diameter of random sparse graphs, Adv. in Appl. Math. 26(4), (2001), 257--279.

William Aiello, Fan Chung, and Linyuan Lu. A random graph model for power law graphs, Experiment. Math., 10(1), (2001), 53--66.
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.

Book Contributions.

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.

Refereed Conference papers.

Reid Anderson, Fan Chung, and Linyuan Lu. Drawing power law graph, 12th international symposium on Graph Drawing, NYC, Sept. 29 -- Oct. 2, 2004.
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, October 2004 Rome, Italy.
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.
Fan Chung, Ronald Graham, and Linyuan Lu. Guessing secrets with inner product questions, Proceedings of the Thirteenth ACM-SIAM Symposium on Discrete Algorithms, (2002), 247--253.
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. A random graph model for massive graphs, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, (2000), 171--180.
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.