Linyuan Lu's research
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
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
t3(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 Zn, 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.