Some recent papers of Fan Chung

• Sparse quasi-random graphs
  Combinatorica, to appear.
  (with R. L. Graham)
  Abstract: Quasi-random graph properties form a large equivalence class of graph properties which are all shared by random graphs. In recent years, various aspects of these properties have been treated by a number of authors. Almost all of these results deal with dense graphs, that is, graphs on n vertices having cn^2 edges for some c > 0 as n approaches infinity. In this paper, we extend our study of quasi-randomness to sparse graphs, i.e., graphs on n vertices with o(n^2) edges. It will be shown that many of the quasi-random properties for dense graphs have analogous for sparse graphs, while others do not, at least not without additional hypotheses. In general, sparse graphs are more difficult to deal with than dense graphs, due for ex ample to the possible absence of certain local structures, such as 4-cycles.
• The average distances in random graphs with given expected degrees
  (with L. Lu)
  Abstract: Random graph theory is used to examine the "small-world phenomenon" -- any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees, the average distance is almost surely of order log n / log \tilde d where \tilde d is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree k is proportional to 1/k^β for some fixed exponent β . For the case of β > 3 , we prove that the average distance of the power law graphs is almost surely of order log n / log \tilde d . However, many Internet, social and citation networks are power law graphs with exponents in the range 2 < β < 3 for which the power law random graphs have average distance almost surely of order log log n, but have diameter of order log n (provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, that we call the core, having n ^{c/\log log n} vertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core.
• Connected components in random graphs with given degree sequences
  (with L. Lu)
  Abstract: We consider a family of random graphs with a given expected degree sequence. Each edge is chosen independently with probability proportional to the product of the expected degrees of its two endpoints. We show that the distribution of its connected components are primarily determined by the average degree d, independent of the weight distribution. We prove that the size of the second largest component of such a random graph on n vertices is at most (2+o(1)) log n / log (1+(d-1)^2) and this is best possible when the expected average degree d is large.
• Guessing secrets
  Electronic Journal of Combinatorics, 8,(2001), #R13.
  (with Ronald Graham and F. Tom Leighton)
  Abstract: We consider a variant of the familiar ``20 questions" problem in which one tries to discover the identity of some unknown ``secret" by asking binary questions. In this variation, there is now a set of two (or more) secrets. For each questio n asked, an adversary gets to choose which of the secrets to use in supply ing the answer, which in any case must be truthful. We will describe a number of algorithms for dealing with this problem, although we are still far from a complete understanding of the situation. Problems of thi s type have recently arisen in connection with certain Internet traffic routing applications.
• Random evolution of massive graphs
  Handbook on Massive Data Sets, (Eds. James Abello et al.), to appear.
  Extended abstract appeared in FOCS 2001, 510-519.
  (with W. Aiello and L. Lu)
  Abstract: Many massive graphs (such as WWW graphs and Call graphs) share certain universal characteristics which can be described by so-called the ``power law". In this paper, we will first briefly survey the history and previous work on power law graphs. Then we will give four evolution models for generating power law graphs by adding one node/edge at a time. We will show that for any given edge density and desired distributions for in-degrees and out-degrees (not necessarily the same, but adhered to certain general conditions), the resulting graph will almost surely satisfy the power law and the in/out-degree conditions. We will show that our most general directed and undirected models include nearly all known models as special cases. In addition, we consider another crucial aspects of massive graphs that is called ``scale-free" in the sense that the frequency of sampling (w.r.t. the growth rate) is independent of the parameter of the resulting power law graphs. We will show that our evolution models generate scale-free power law graphs.
• On sparse sets hitting linear forms
  Journal of Number Theory, to appear.
  (with Paul Erdös and Ronald Graham)
  Abstract: Let a_1 < a_2 < . . . < a_s be given integers and let [n] denote the set { 1,2, . . ., n } . In this note we investigate the size of minimum subsets of [n] which intersect every set in [n] of the form {a_1 x , a_2 x, . . ., a_s x } for some x in [n] . For the most part, we can only estimate this extremal density although there is an interesting class of a_i 's for which we can find the exact answer.
• Combinatorics for the East model,
  (with Persi Diaconis and Ronald Graham)
  Abstract: We study the number of configurations in the East model of statistical physics. This may be pictured as sites in a line. The site at zero is always occupied. The site at i > 0 can only be changed if site i-1 is occupied. If at most n occupied sites are permitted, we establish upper and lower bounds of the form
  2^{ n choose 2} n! c^n where c < 1 for the number of possible configurations.
• A chip firing game and Dirichlet eigenvalues, (with Robert Ellis)
  Abstract: We consider a variation of the chip-firing game in an induced subgraph S of a graph G. Starting from a given chip configuration, if a vertex $v$ has at least as many chips as its degree, we can fire v by sending one chip along each edge from v to its neighbors. The game continues until no vertex can be fired. We will give an upper bound, in terms of Dirichlet eigenvalues, for the number of firings needed before a game terminates. We also examine the relations among three equinumerous families, the set of spanning forests on S with roots in the boundary of S, a set of "critical" configurations of chips, and a coset group, called the sandpile group associated with S.
• Distance realization problems with applications to Internet tomography (with Mark Garrett, Ronald Graham and David Shallcross).
  Abstract: In recent years, a variety of graph optimization problems have arisen in which the graphs involved are much too large for the usual algorithms to be effective. In these cases, even though we are not able to examine the entire graph (which may be changing dynamically), we would still like to deduce various properties of it, such as the size of a connected component, the set of neighbors of a subset of vertices, etc. In this paper, we study a class of problems which arise in the study of Internet data traffic models. Several graph-theoretic problems are formulated that relate to the inference of network topology given the distances (as represented by end-to-end delay) between pairs of special nodes designated as network monitors. Some properties of these problems (such as NP-completeness) are derived and illustrated. A number of heuristic algorithms are described and some initial results from experimental implementations of these heuristics are provided. These problems are of interest for monitoring large-scale networks, or supplementing network management techniques that may fail due to the interaction, or lack of standard cooperation, among the heterogeneous technologies comprising the network.
• Discrete Green's functions, J. Combinatorial Theory (A), to appear, (with S.-T. Yau)
  Abstract: We study discrete Green's functions and their relationship with discrete Laplace equations. Several methods for deriving Green's functions are discussed. Green's functions can be used to deal with diffusion-type problems on graphs, such as chip-firing, load balancing and discrete Markov chains.
• The diameter of random sparse graphs,
  Advances in Applied Math, to appear.
  (with Linyuan Lu)
  Abstract: We consider the diameter of a random graph G(n,p) for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of random graph G(n,p) is close to log n / log (np) if np approaches infinity. Moreover if np / log n = c > 8, then the diameter of G(n,p) is concentrated on two values. In general, if np / log n = c > c_0, the diameter is concentrated on at most 2\lfloor 1 / c_0 \rfloor + 4 values. We also proved that the diameter of G(n,p) is almost surely equal to the diameter of its giant component if np > 3.6.
• A random graph model for massive graphs,
  Proceedings of the Thirtysecond Annual ACM Symposium on Theory of Computing (2000), 171-180. (with Bill Aiello and Linyuan Lu)
  The complete paper version has a different title A random graph model for power law graphs,
  Abstract: We propose a random graph model which is a special case of sparse random graphs with given degree sequences which satisfy a power law. This model involves only a small number of parameters, called logsize and log-log growth rate. These parameters capture some universal characteristics of massive graphs. Furthermore, from these parameters, various properties of the graph can be derived. For example, for certain ranges of the parameters, we will compute the expected distribution of the sizes of the connected components which almost surely occur with high probability. We will illustrate the consistency of our model with the behavior of some massive graphs derived from data in telecommunications. We will also discuss the threshold function, the giant component, and the evolution of random graphs in this model.
• On polynomials of spanning trees,
  Annals of Combinatorics, 4 (2000), 13-26.
  (with C. Yang)
  Abstract: The Kirchhoff polynomial of a graph G is the sum of weights of all spanning trees where the weight of a tree is the product of all its edge weights, considered as formal variables. Kontsevich conjectured that when edge weights are assigned values in a finite field F_q, for a prime power q, the number of zeros of the Kirchhoff polynomial of a graph G is just a polynomial function of q. Stanley verified this conjecture for some families of graphs and further proposed several conjectures. In this paper, we derive and prove explicit formulas for certain graphs, thus confirming Stanley's conjectures. We also consider several extensions and generalizations of the conjecture of Kontsevich.
• Dynamic location problems with limited look-ahead,
  Theoretical Computer Science, to appear.
  (with Ron Graham)
  Abstract:
• Spanning trees in subgraphs of lattices,
  Comtempory Math, to appear.
  Abstract: We examine the relations between the heat kernel, the zeta function and the number of spanning trees of a graph. In particular, we show that for an induced subgraph S in the 2-dimensional lattice graph, the number of spanning trees of S is bounded above by a function in |S| and the size of the boundary of S.
• An upper bound for the Turan number t_3(n,4),
  Journal of Combinatorial Theory (A), 87 (1999), 381-389.
  (with Linyuan Lu)
  Abstract: Let t_r(n,r+1) denote the smallest integer m such that every r-uniform hypergraph on n vertices with m+1 edges must contain a complete graph on r+1 vertices. In this paper, we improve the previous lower bound for t_3(n,4).
• Coverings, heat kernels and spanning trees
  Electronic Journal of Combinatorics, 6, (1999), #R12. (with S.-T. Yau).
  Abstract: We consider a graph G and a covering \tilde{G} of G and we study the relations of their eigenvalues and heat kernels. We evaluate the heat kernel for an infinite $k$-regular tree and we examine the heat kernels for general k-regular graphs. In particular, we show that a k-regular graph on n vertices has at most
  (1+o(1)) \frac {2\log n}{kn \log k} \left( \frac{(k-1)^{k-1}} {(k^2-2k)^{k/2-1}} \right)^n
  spanning trees, which is best possible within a constant factor.
• Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs,
  Communications on Analysis and Geometry, to appear
  (with A. Grigor'yan and S.-T. Yau).
• Augumented ring networks,
  (with Bill Aiello, Sandeep Bhatt and Arny Rosenberg, Ramesh Sitaraman)
• Open problems of Paul Erdos in graph theory,
  Journal of Graph Theory, 25 (1997), 3-36.
• Multidiameters and multiplicities,
  European Journal of Combinatorics, 20 (1999), 629-640.
  (with C. Delorme and P. Sol'e ).
• Forced convex n-gons in the plane,
  Discrete and Computational Geometry, 19 (1998), 367-371.
  (with R.L. Graham)
• Spectral Graph Theory, AMS Publications, 1997.
  The first chapter is here .
• Stratified random walks on an $n$-cube,
  Random Structures and Algorithms, 11 (1997), 199-224.
  (with R.L. Graham)
• Random walks on generating sets of groups,
  Electronic Journal of Combinatorics, 4, no. 2, (1997) #R7
  (with R. L. Graham).
• Logarithmic Sobolev techniques for random walks on graphs .
  Emerging Applications of Number Theory, IMA Volumes in Math. and its Applications, 109 (eds. D. A. Hejhal et. al.), 175-186, Springer, 1999.
• Logarithmic Harnack inequalities,
  Mathematical Research Letters, 3 (1996), 793-812.
  (with S.-T. Yau)
• Isoperimetric inequalities for cartesian products of graphs ,
  Probability, Combinatorics and Computing, 7 (1998), 141-148.
  (with Prasad Tetali).
• Weighted graph Laplacians and isoperimetric inequalities,
  Pacific Journal of Mathematics, 192 (2000), 257-274.
  (with Kevin Oden)
• On optimal strategies for stealing cycles,
  IEEE Trans. on Computers, 46 (1997), 545-557
  (with S. Bhatt, F. T. Leighton, and A. L. Rosenberg)
• Maximum subsets of $(0,1]$ with no solutions to $x+y=kz$,
  Electronic Journal of Combinatorics, 3 (1996) #1
  (with John L. Goldwasser)
• A Harnack inequality for Dirichlet eigenvalues,
  Journal of Graph Theory, 34 (2000), 247-257.
  (with S.-T. Yau).
• A combinatorial trace formula,
  Tsing Hua Lectures on Geometry and Analysis, International Press, Cambridge, Massachusetts, 1997, 107-116. (with S.-T. Yau)
• A combinatorial Laplacian with vertex weights,
  Journal of Combinatorial Theory, (A), 75 (1996) 316-327.
  (with R. P. Langlands)
• Eigenvalues and diameters for manifolds and graphs,
  Tsing Hua Lectures on Geometry and Analysis, . International Press, Cambridge, Massachusetts, 1997, 79-106.
  (with A. Grigor'yan and S. T. Yau)
• Optimal emulations by butterfly networks ,
  JACM, 43 (1996), 316-327.
  (with S. Bhatt, Jia-Wei Hong, F. T. Leighton, Bojana Obrenic, A. L. Rosenberg and E.J. schwabe)
• Upper bounds for eigenvalues of the discrete and continuous Laplace operators,
  Advances in Mathematics, 117 (1996) 165-178.
  (with A. Grigor'yan and S. T. Yau)
• On sampling with Markov chains,
  Random Structures and Algorithms, 9 (1996) 55-78.
  (with R. L. Graham and S. -T. Yau)
• Eigenvalue inequalities for graphs and convex subgraphs,
  Communications on Analysis and Geometry, 5 (1998), 575-624.
  (with S.-T. Yau)
• A Harnack inequality for homogeneous graphs and subgraphs,
  Communications on Analysis and Geometry, 2 (1994), 628-639
  (with S.-T. Yau)
• Eigenvalues of graphs,
  Proceedings of the International Congress of Mathematicians, Zurich, (1994),
  Birkh"auser Verlag, Berlin, 1333-1342.
• Scheduling tree-dags using FIFO queues: A control-memory tradeoff,
  (with Sandeep N. Bhatt, Tom Leighton and Arny Rosenberg)
• Eigenvalues of graphs and Sobolev inequalities,
  Combinatorics, Probability and Computing, . 4 (1995) 11-26.
  (with S. T. Yau)
• Salvage embeddings of complete trees,
  SIAM J. Discrete Math., 8 (1995), 617-637
  (with S. Bhatt, F. T. Leighton, and A. L. Rosenberg)
• Groups and the Buckyball, in Lie Theory and Geometry: In honor of Bertram Kostant (Eds. J.-L. Brylinski, R. Brylinski, V. Guillemin and V. Kac)
  PM 123, Birkh"auser, Boston, 1994
  (with Bertram Kostant and Shlomo Sternberg)
• On the cover polynomial of a digraph,
  J. Combinatorial Theory, (B) 65 (1995), 273-290
  (with R. L. Graham)
• Routing permutations on graphs via matchings,
  SIAM J. Discrete Math. 7 (1994) 513-530
  (with Noga Alon and R. L. Graham)
• Mathematics and the Buckyball,
  (This is a somewhat different version from the one that appeared in American Scientist, v. 81, No. 1., (1993) 56-71)
  (with Shlomo Sternberg)
• Chordal completions of planar graphs,
  J. of Comb. Th. (B) 62 (1994) 96-106.
  (with David Mumford)
• A report on reliable software and communication,
  Bellcore Internal Memorandom 1992. Paper version titled `` Reliable software and communication: An overview", IEEE J. Selected Areas Comm. v. 12, no. 1 (1994), 23-32.
• Laplacian and vibrational spectra for homogeneous graphs,
  J. Graph Theory , 16 (1992), 605-627
  (with Shlomo Sternberg)
• Communication complexity and quasi-randomness,
  SIAM J. Discrete Math. 6 (1993), 110-123.
  (with Prasad Tetali)
• Several generalizations of Weil's sums, J. of Number Theory, 49, (1994) 95-106.
• Subgraphs of a hypercube containing no small cycles, J. Graph Theory, 16 (1992), 273-286
• Even cycles in directed graphs,
  SIAM J. Discrete Math. 7 (1994) 474-483
  (with Wayne Goddard and D. J. Kleitman)