Research on Internet Mathematics by Fan Chung Graham

• Guessing secrets ,
  A problem that arose in connection with Internet traffic routing has led to many interesting new directions in solving equations with uncertainty.
  
  • The first paper contains the formulation, variations, upper and lower bounds, algorithms and relations to hypergraph theory.
    Abstract| paper | SODA paper .
    Authors: Fan Chung, Tom Leighton, Ronald Graham
  • In a second paper, efficient inverse strategies are presented with special emphasis on inner product methods.
    Abstract| paper
    Authors: Fan Chung, Ronald Graham and Lincoln Lu
  • A third paper, in preparation.
• Massive graphs
  We are still far from taming the beast but here we have first developed quantatitive rigorous methods for dealing with massive graphs by using random graph theory. In turn, the study of power law model for massive graphs has deepened our understanding for sparse random graphs with general degree distributions.
  • The first paper includes the basic model for power law graphs, the expected distribution of the giant component and the second largest components.
    Abstract| some descriptions | paper | STOC paper| other related papers
    Coauthors -- Bill Aiello, Fan Chung, Lincoln Lu.
    The STOC talk in ppt (Math type notation required).
  • A second paper is on the evolution of massive graphs that are changing dynamically. We deal with scale-invariant graphs with different in-degrees and out-degrees.
    Abstract| paper| FOCS paper
    Coauthors -- Bill Aiello, Fan Chung, Lincoln Lu.
  • A paper on (classical) random sparse graphs extends the ranges of expected values for diameters .
    Abstract| paper
    Coauthors -- Fan Chung, Lincoln Lu.
  • For random graphs with given degree sequence the distribution of the sizes of connected components depends primarily on the average degree.
    Abstract| paper
    Coauthors -- Fan Chung, Lincoln Lu.
  • A simulation project for massive graphs.
• Internet tomography
  • Abstract| some descriptions
  • A talk on this topic.
  • A paper
    Distance realization problems with applications to Internet tomography
    coauthored with Ronald Graham, Mark Garrett and David Shallcross.
• Dynamic location problems with finite look-ahead
  • Abstract| some descriptions
  • A paper
• Chip-firing and load balancing in distributed networks.
  Various methods are based on an interesting question:
  Can you hear the shape of a graph? An implementation can be found in a neat webpage designed by Robert Ellis.
  A simulation of several chip-firing games is under construction.
  Abstract| papers on this topic.
• Selected research topics in spectral graph theory :
  • Isoperimetric inequalities
    Abstract| descriptions | paper | other related papers
  • Green's functions
    Abstract| descriptions | paper | other related papers
  • Heat kernels and spanning trees
    Abstract| descriptions | two papers | other related papers
  • Harnack inequalities
  • Discrete Sobolev inequalities
  • Logarithmic Sobolev inequalities
  • Random walks
• Selected topics in extremal graph theory and random graph theory
  • Tur'an problems
    Abstract| descriptions | paper | other related papers
  • Diameter of random sparse graphs
    Abstract| descriptions | paper | other related papers
  • Papers in
    • universal graphs,
    • unavoidable graphs,
    • graph labelings,
    • graph embeddings.
    • graph decomposition.