**Papers of Fan Chung**

**Papers of Fan Chung**## Preprints

Regularity lemmas for clustering graphs,

*Advances in Applied Math.*, to appear.Permanental generating functions and sequential importance sampling , preprint, (with Persi Diaconis and Ron Graham)

Slow Fibonacci walks,

*Journal of Number Theory*, to appear, (with Ron Graham and Sam Spiro)Efficient packings of unit squares in a large square,

*Discrete and Computational Geometry*, to appear, (with R. Graham)

## 2020

## 2019

## 2018

The maximum relaxation time of a random walk,

*Advances in Applied Math.*,**101**, (2018), 1-14, (with S. G. Aksoy, M. Tait and J. Tobin).Well dispersed sequences in [0,1]^d ,

*J. Number Theory,***189**, (2018), 1-24, (with Ron Graham).The digraph drop polynomial, in

*Connections in Discrete Mathematics*, (S. Butler, J. Cooper, G. Hurlbert, eds.) Cambridge University Press, 2018, 86-103, (with Ron Graham).Sum sequences modulo n, JCT(A),

**158**, (2018), 290-314, (with Jon Folkman and Ron Graham).A semi-supervised heat kernel pagerank MBO algorithm for data classification,

*Comm. Math. Sci.*,**16**(2018), 1241-1264, (with Ekaterina Merkurjev and Andrea L. Bertozzi).Computing heat kernel pagerank and a local clustering algorithms,

*European Journal of Combinatorics*,**68**(2018), 96-119, (with O. Simpson).

## 2017

The drop polynomial of a weighted digraph, JCT(B),

**126**, (2017), 62-82, (with Ron Graham).Juggling card sequences,

*Journal of Combinatorics***8**(2017), 507-539, (with Steve Butler, Jay Cummings, and Ron Graham).The spectral gap of graphs arising from substring reversals,

*The Electronic J. of Combinatorics*,**24**, no. 3 (2017), #P.3.4, (with J. Tobin).A strong Harnack inequality for graphs,

*Comm. Analysis and Geometry*,**25**, no. 3, (2017), 557-588, (with S.-T. Yau).Curvature aspects of graphs,

*Proc. of AMS*,**145**(2017), 2033-2042, (with F. Bauer, Y. Lin and Y. Liu).

## 2016

Extreme values of the stationary distribution of random walks on directed graphs,

*Advance in Applied Math.*,**81**, (2016), 128-155, (with Sinan Aksoy and Xing Peng).A generalized Alon-Boppana bound and weak Ramanujan graphs,

*Electronic Journal of Combinatorics*,**23**, (2016), Paper #3.4, (20 pages). The version in E-JC.On the discrepancy of circular sequences of reals,

*J. Number Theory*,**164**(2016), 52-65, (with R. L. Graham).Decomposition of random graphs into complete bipartite graphs,

*SIAM J. Discrete Math.*,**30**, no. 1, (2016), 296-310, (with X. Peng).Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions,

*OR Spectrum*,**38**(2), (2016), 531-540, (with O. Braun and R. L. Graham).The matrix cover polynomial,

*J. Combinatorics*,**7**(2016), 375-412, (with R. L. Graham).

## 2015

Distributed algorithms for finding local clusters using heat kernel pagerank, WAW, 2015, LNCS 9479, Springer, 177-189, (with O. Simpson).

A brief survey of PageRank algorithms,

*IEEE Transactions on Network Science and Engineering*,**1**, No. 1, (2015), 38-42.Edge flipping in the complete graphs,

*Advances in Appl. Math.***69**(2015), 46-64, (with S. Butler, J. Cummings and R. L. Graham).Computing heat kernel pagerank and a local clustering algorithms,

*Combinatorial Algorithms, Lecture Notes in Comput. Sci.*, 8986, Springer, Cham, 2015, 110-121.Solving linear systems with boundary conditions using heat kernel pagerank,

*Internet Mathematics*,**11**(2015), 449-471, (with Olivia Simpson).A local clustering algorithm for connection graphs,

*Internet Math.*,**11**(2015), 333-351, (with Mark Kempton).

## 2014

Discrepancy inequalities for directed graphs,

*Discrete Applied Mathematics*,**176**(2014) 30-42, (with F. Kenter).Complex Networks, a chapter in Handbook of Graph Theory, (eds. J. L. Gross et. al), 1456-1476, CRC Press, 2014, (with A. Bonato).

Harnack inequalities for graphs with non-negative Ricci curvature,

*J. Math. Anal. Appl.***415**(2014), 25-32, (with Yong Lin and S.-T. Yau).A chapter titled ``Spectral Graph Theory", to appear in

*Handbook of Linear Algebra*, CCR Press, (with Steve Butler).A note on an alternating upper bound for random walks on semigroups,

*Discrete Applied Mathematics*,**176**(2014), 24-29, (with J. Hughes).Single processor scheduling with time restrictions,

*J. of Scheduling*,**17**(2014), 399-403, (with O. Braun and R. Graham).From quasirandom graphs to graph limits and graphlets,

*Advances in Applied Math.***56**(2014), 135-174.Hypergraph coloring games and voter models,

*Internet Mathematics*,**10**(2014), 66-86, (with Alex Tsiatas).Multi-commodity allocation for dynamic demands using PageRank vectors,

*Internet Mathematics*,**10**(2014), 49-65, (with P. Horn and J. Hughes).Ranking and sparsifying a connection graph,

*Internet Mathematics*,**10**(2014), 87-115, (with M. Kempton and W. Zhao).

## 2013

Inversion-descent polynomials for restricted permutations,

*J. of Combinatorial Theory*, A,**120**, (2013), 366-378, (with Ron Graham).Solving linear systems with boundary conditions using heat kernel pagerank, WAW 2013, LNCS 8305, 203-219, (with Olivia Simpson).

Dirichlet PageRank and ranking algorithms based on trust and distrust,

*Internet Mathematics*,**9**, (2013), 113-134, (with A. Tsiatas and Wensong Xu).A local clustering algorithm for connection graphs, WAW 2013, LNCS 8305, 203-219, (with Mark Kempton).

## 2012

Spectral clustering of graphs with general degrees in the extended planted partition model, COLT 2012, Journal of Machine Learning Research, (2012), 1-23, (with K. Chaudhuri and A. Tsiatas).

Ranking and sparsifying a connection graph, WAW 2012, LNCS 7323 (2012), 66-77, (with M. Kempton and W. Zhao).

Generalized Euler sums,

*Journal of Combinatorics*,**3**, (2012), 299-316, (with Ron Graham).Multi-commodity allocation for dynamic demands using PageRank vectors, WAW2012, LNCS 7323 (2012), 138-152, (with P. Horn and J. Hughes).

Braess's paradox in expanders,

*Random Structures and Algorithms*,**41**(2012), 451-468, (with S. J. Young and W. Zhao).Hypergraph coloring games and voter models, WAW2012, LNCS 7323 (2012), 1-16, (with Alex Tsiatas).

Edge flipping in graphs,

*Advances in Applied Mathematics*,**48**(2012) 37-63, (with Ron Graham).Diameter of random spanning trees in a given graph,

*Journal of Graph Theory*,**69**, (2012), 223-240, (with P. Horn and L. Lu).Finding and visualizing graph clusters using PageRank optimization,

*Internet Mathematics*,**8**(2012), 46-72, (with A. Tsiatas).

## 2011

Dirichlet PageRank and trust-based ranking algorithms, WAW 2011, LNCS 6732, (2011), 103-114, (with A. Tsiatas and Wensong Xu).

On the spectra of general random graphs,

*Electronic Journal of Combinatorics*,**18(1)**, (2011), P215, 14 pages, (with M. Radcliffe).

## 2010

Graph Theory in the information age,

*Notices of AMS*,**57**, no. 6, July 2010, 726-732. This article was translated into Chinese and appeared in*Mathematical Advances in Translation*,**3**, 2010, 207-213.A symmetric Eulerian identity,

*Journal of Combinatorics*,**1**(2010), 29-38, (with Ron Graham and Don Knuth).PageRank and random walks on graphs, Fete of Combinatorics and Computer Science, (G. O. H. Katona, A. Schrijver and T. Szonyi, Eds.), Springer, Berlin, (2010), 43-62, (with Wenbo Zhao).

Small spectral gap in the combinatorial Laplacian implies Hamiltonian,

*Annals of Combinatorics*,**13**, (2010), 403-412, (with S. Butler).Tiling polygons with lattice triangles, Discrete and Computational Geometry,

**44**, (2010), 898-903, (with Steve Butler, Ron Graham and Mikl'os Laczkovich).Descent polynomials for permutations with bounded drop size, European J. Combinatorics,

**31**, (2010), 1853-1867, (with Anders Claesson, Mark Dukes, and Ronald Graham).Finding and visualizing graph clusters using PageRank optimization, WAW 2010, LNCS 6516, (2010), 86-97, (with A. Tsiatas).

Braess's paradox in large sparse graphs, WINE 2010, LNCS 6484, 194-208, (with Stephen J. Young).

A sharp PageRank algorithm with applications to edge ranking and graph sparsification, WAW 2010, LNCS 6516, 2-14, (with Wenbo Zhao).

PageRank as a discrete Green's function,

*Geometry and Analysis*, I, ALM**17**, (2010), 285-302.

## 2009

A local graph partitioning algorithm using heat kernel pagerank, WAW 2009, LNCS 5427, (2009), 62-75.

Distributing antidote using PageRank vectors,

*Internet Mathematics*,**6**, (2009), 237-254, (with Paul Horn and Alexander Tsiatas).The giant component in a random subgraph of a given graph, Proceedings of WAW2009, Lecture Notes in Computer Science 5427, 38-49, (with P. Horn and L. Lu).

Packing equal squares into a large square,

*JCT(A)*,**116**, (2009), 1167-1175, (with R. L. Graham).

## 2008

A whirlwind tour of random graphs, a survey article in

*Encyclopedia on Complex Systems*, Springer, 2008.A network color game, WINE 2008, Lecture Notes in Computer Science,

**Volume 5385**(2008), 522-530, (with K. Chaudhuri and M. S. Jamall).Quasi-random graphs with given degree sequences,

*Random Structures and Algorithms*,**12**(2008), 1-19, (with R. L. Graham).Primitive juggling sequences,

*Amer. Math. Monthly,***115**, March 2008, 185-194, (with Ron Graham).Local partitioning for directed graphs using PageRank,

*Internet Mathematics*,**5**(2008), 3-22, (with R. Andersen and Kevin Lang).

## 2007

Four Cheeger-type inequalities for graph partitioning algorithms, Proceedings of ICCM, II, (2007), 751-772.

The heat kernel as the pagerank of a graph, PNAS,

**105**(50), (2007), 19735-19740.The spectral gap of a random subgraph of a graph, the extended abstract appeared in Proceedings of WAW2006, LNCS 4937 and the complete version is in

*Internet Math*,**4**(2007), 225-244, (with Paul Horn).Oblivious and adaptive strategies for the majority and plurality problems,

*Algorithmica*,**48**(2007), 147-157, (with R. Graham, Jia Mao and Andrew Yao)Detecting sharp drops in PageRank and a simplified local partitioning algorithm,

*Theory and Applications of Models of Computation*, Proceedings of TAMC 2007, LNCS 4484, Springer, (2007), 1-12, (with R. Andersen).Using pagerank vectors to locally partition a graph,

*Internet Mathematics*,**4**(2007), 35-64, (with R. Andersen and K. Lang).Random walks and local cuts in graphs,

*Linear Algebra and its Applications,***423**Universal juggling cycles,

*Integers, Combinatorial Number Theory*, B. Landman, M.B. Nathanson, J. Nesetril, R.J. Nowakowski, C. Pomerance, eds. (2007), 121-130, (with Ron Graham).Universal juggling cycles,

*INTEGERS***7**(2) (2007), A8 (electronic) 10 pp. (with Ron Graham).Drawing power law graphs using a local/global decomposition, appeared in

*Algorithmica***47**(2007), 379-397, (with Reid Andersen, L. Lu).Oblivious strategies for the majority and plurality problems,

*Algorithmica***48**(2007), 147-157, (with R. Graham, Jia Mao and Andrew Yao).Local partitioning for directed graphs using PageRank, WAW2007, 166-178, (with R. Andersen and Kevin Lang).

## 2006

Parallelism versus memory allocation in pipelined router forwarding engines,

*Theory Comput. Systems***39**(2006), 829-849, (with R. Graham, J. Mao and G. Varghese).Weighted Laplacians and the Sigma function of a graph,

*Quantum Graphs and their Applications*, (B. Berkolaiko et. al. eds), Contemporary Math., AMS, Providence, RI, 93-107, 2006 (with Ross Richardson).Concentration inequalities and martingale inequalities --- a survey,

*Internet Math.*,**3**(2006-2007), 79-127, (with L. Lu).Maximizing data locality in distributed systems,

*Journal of Computer System Sciences*,**72**(December 2006), 1309-1316, (with Ronald Graham, Ranjita Bhagwan, Stefan Savage and Geoffrey M. Voelker).The volume of the giant component of a random graph with given expected degrees,

*SIAM J. Discrete Math.***20**(2006), no. 2, 395-411, (with L. Lu).A brief overview of network algorithms,

*J. of Computer and System Sciences***72**(2006), no. 3, 420-424.The diameter and Laplacian eigenvalues of directed graphs,

*Electronic Journal of Combinatorics***13**(2006), N4, 6 pp.Complex Graphs and Networks,

*CBMS*Number 107, AMS Publications, 2006, vii+264pp., (with L. Lu).Local graph partitioning using pagerank vectors, FOCS 2006, 475-486, (with R. Andersen and K. Lang).

## 2005

Laplacians and the Cheeger inequality for directed graphs,

*Annals of Combinatorics*,**9**(2005), 1-19.Oblivious strategies for the majority and plurality problems,

*Computing and Combinatorics*, Lecture Notes in Computer Science, Springer, Berlin (2005), 329-338, (with R. Graham, Jia Mao and Andrew Yao).A spectral Turán theorem,

*Combinatorics, Probability and Computing***14**(2005), 755-767.

## 2004

Drawing power law graphs,

*Proceedings Graph Drawing*, New York, 2004, 12-17, (with Reid Andersen, L. Lu).Analyzing the small world phenomenon using a hybrid model with local network flow, WAW 2004, Rome, Italy, Lecture Notes in Computer Science, 3234, Springer, 2004, 19-30, a long version appeared as Modeling the small-world phenomenon with local network flow,

*Internet Mathematics***2**(2006), no. 3, 359-385, (with Reid Andersen, L. Lu).Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines, SPAA'04, Barcelona, Spain, (2004), 103-111, (with Ronald Graham and George Varghese).

De Bruijn cycles for covering codes,

*Random Structures and Algorithms*,**25**, (2004), 421-431, (with J. Cooper).Coupling online and offline analyses for random power law graphs,

*Internet Mathematics*,**1**(2004), 409-461, (with Lincoln Lu).Discrete isoperimetric inequalities,

*Surveys in Differential Geometry IX*, International Press, (2004), 53-82.On disjoint path pairs with wavelength continuity constraint in WDM networks, INFOCOM, 2004, (with Reid Andersen, Arunabha Sen and Guoliang Xue).

The small world phenomenon in hybrid power law graphs, Complex Networks, (Eds. E. Ben-Naim et. al.), Springer-Verlag, (2004), 89-104, (with Lincoln Lu).

Spectral grouping using the Nyström method,

*IEEE Transactions on Pattern Analysis and Machine Intelligence***26**, No. 2, (2004), 214-225, (with Charless Fowlkes, Serge Belongie, and Jitendra Malik).Guessing secrets with inner product questions,

*Internet Math*.,**1**(2004), no. 2, 177-192, (with R.L. Graham and Linyuan Lu).The spectra of random graphs with given expected degrees,

*Internet Mathematics***1**(2004), 257-275, (with Lincoln Lu and Van Vu).

## 2003

Generalizations of Polya's urn problem,

*Annals of Combinatorics***7**(2003), 141-153, (with Shirin Handjani and Doug Jungreis).Finding Favorites,

*Electronic Colloquium on Computational Complexity*, Report No. 78 (2003), (with Ron Graham, Jia Mao and Andrew Yao).Eigenvalues of random power law graphs,

*Annals of Combinatorics***7**(2003), 21-33, (with Lincoln Lu and Van Vu).The spectra of random graphs with given expected degrees,

*Proceedings of National Academy of Sciences***100**, no. 11, (2003), 6313-6318, (with Lincoln Lu and Van Vu).Duplication models for biological networks,

*Journal of Computational Biology***10**, no. 5, (2003), 677-688, (with Lincoln Lu, Gregory Dewey, David J. Galas).The average distances in random graphs with given expected degrees, abstract,

*Internet Mathematics***1**(2003), 91-113, (with L. Lu).

## 2002

Guessing secrets with inner product questions,

*Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms*, (2002), 247-253, (with R.L. Graham and Linyuan Lu).Spectral Partitioning with Indefinite Kernels using the Nyström Extension, European Conference on Computer Vision, 2002, III, 531-542, (with Charless Fowlkes, Serge Belongie, and Jitendra Malik).

Sparse quasi-random graphs, abstract,

*Combinatorica***22**(2002), 217-244, (with Ronald Graham).Connected components in random graphs with given expected degree sequences, abstract,

*Annals of Combinatorics***6**(2002), 125-145, (with L. Lu).Random evolution of massive graphs, abstract, Handbook of Massive Data Sets, (Eds. James Abello et al.), Kluwer Academic Publishers, (2002), 97-122, extended abstract appeared in FOCS 2001, 510-519, (with W. Aiello and L. Lu).

On sparse sets hitting linear forms, abstract, Number Theory for the Millennium I, (Eds. M. A. Bennett et al.), AK Peters, Natick, Massachusetts, (2002), 257-272. (with Paul Erdős and Ronald Graham)

A chip-firing game and Dirichlet eigenvalues, abstract,

*Discrete Math***257**(2002), 341-355, (with Robert Ellis).The average distances in random graphs with given expected degrees, abstract,

*Proc. National Academy of Sciences***99**, no. 25, (December, 2002), 15879-15882, (with L. Lu).

## 2001

Guessing secrets, abstract,

*Electronic Journal of Combinatorics***8**(2001), R13, 25 pp, extended abstract appeared in*Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms*(Washington, DC, 2001), SIAM, Philadelphia, 723-726, (with Ron Graham and Tom Leighton). also, SODA'01, 723-726, (with Ronald Graham and F. Tom Leighton).Combinatorics for the East model, abstract,

*Advances in Applied Math.***27**(2001), 192-206, (with Persi Diaconis and Ronald Graham).Distance realization problems with applications to Internet tomography,

*J. Computer and System Sciences***63**No. 3, (November 2001), 432-448, (with Mark Garrett, Ronald Graham and David Shallcross).The diameter of sparse random graphs, abstract,

*Advances in Applied Math*.**26**(2001), 257-279, (with Linyuan Lu).Dynamic location problems with limited look-ahead,

*Theoretical Computer Science***261**(2001), 213-226, (with Ron Graham).Augmented ring networks,

*IEEE Transactions on Parallel and Distributed Systems***12**(2001), 598-609, (with W. Aiello, S. N. Bhatt, A. L. Rosenberg and R. K. Sitaraman).A random graph model for power law graphs,

*Experimental Math.***10**(2001), 53-66, (with Bill Aiello and Linyuan Lu).

## 2000

Discrete Green's functions, abstract,

*J. Combinatorial Theory*(A)**91**(2000), 191-214, (with S.-T. Yau).Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs,

*Communications on Analysis and Geometry***8**, (2000), 969-1026, (with A. Grigor'yan and S.-T. Yau).A random graph model for massive graphs, abstract,

*Proceedings of the Thirtysecond Annual ACM Symposium on Theory of Computing*(2000), 171-180, (with Bill Aiello and Linyuan Lu).On polynomials of spanning trees, abstract,

*Annals of Combinatorics***4**(2000), 13-26, (with C. Yang).Weighted graph Laplacians and isoperimetric inequalities,

*Pacific Journal of Mathematics***192**(2000), 257-273, (with Kevin Oden).A Harnack inequality for Dirichlet eigenvalues,

*Journal of Graph Theory,***34**(2000), 247-257, (with S.-T. Yau).

## 1999

Spanning trees in subgraphs of lattices,

*Comtempory Math.***245**, Amer. Math. Soc., Providence, R. I., 1999, 201-219.The maximum upper density of a set of positive real numbers with no solution s to x+y=kz, in

*Paul Erdős and his mathematics*(Budapest, 1999), Janos Bolyai Math. Soc., Budapest, 1999, 54-56, (with John L. Goldwasser).An upper bound for the Turan number t

_{3}(n,4),*Journal of Combinatorial Theory*(A)**87**(1999), 381-389, (with Linyuan Lu).Coverings, heat kernels and spanning trees,

*Electronic Journal of Combinatorics***6**(1999), R12, 21 pp, (with S.-T. Yau).Multidiameters and multiplicities,

*European Journal of Combinatorics***20**(1999), 629-640, (with C. Delorme and P. Sol'e).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.

## 1998

Forced convex n-gons in the plane,

*Discrete and Computational Geometry***19**(1998), 367-371, (with R.L. Graham).Isoperimetric inequalities for Cartesian products of graphs,

*Combinatorics, Probability and Computing***7**(1998), 141-148, (with Prasad Tetali).Erdős on Graphs.

*His Legacy of Unsolved Problems*, A. K. Peters, Wellesley, MA, 1998, xiv+142 pp., (with Ron Graham).

## 1997

Open problems of Paul Erdős in graph theory,

*Journal of Graph Theory***25**(1997), 3-36. MoreSpectral Graph Theory, (first four chapter) CBMS Number 92, AMS Publications, 1997, xii+207 pp.

Stratified random walks on an n-cube,

*Random Structures and Algorithms***11**(1997), 199-222, (with R.L. Graham).Random walks on generating sets of groups,

*Electronic Journal of Combinatorics***4**no. 2, (1997) #R7, 14 pp, (with R. L. Graham).Eigenvalue inequalities for graphs and convex subgraphs,

*Communications on Analysis and Geometry***5**(1997), 575-623, (with S.-T. Yau).On optimal strategies for cycle-stealing in networks of workstations,

*IEEE Trans. on Computers***46**(1997), 545-557, (with S. Bhatt, F. T. Leighton, and A. L. Rosenberg).Integer sets containing no solutions to x+y=3z, in

*The Mathematics of Paul Erdős*, Springer Verlag, Berlin (1997), 218-227, (with John L. Goldwasser).A combinatorial trace formula,

*Tsing Hua Lectures on Geometry and Analysis*, International Press, Cambridge, Massachusetts, 1997, 107-116, (with S.-T. Yau)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).

## 1996

Logarithmic Harnack inequalities,

*Mathematical Research Letters***3**(1996), 793-812, (with S.-T. Yau).Laplacians of graphs and Cheeger's inequalities, in

*Combinatorics, Paul Erdős is eighty,*Vol. 2 (Keszthely, 1993), Bolyai Math. Soc., Budapest, 1996, 157-172.Optical wavelength routing, translation, and packet/cell switched networks,

*Journal of Lightwave Technology***14**, Issue 3, March 1996, 336-343, (with Krishna Bala and Charles A. Brackett).Maximum subsets of $(0,1]$ with no solutions to $x+y=kz$,

*Electronic Journal of Combinatorics***3**(1996) R1, 23 pp, (with John L. Goldwasser).A combinatorial Laplacian with vertex weights,

*Journal of Combinatorial Theory*(A)**75**(1996), 316-327, (with R. P. Langlands).Optimal emulations by butterfly-like networks,

*JACM***43**(1996), 293-330, (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-77. (with R. L. Graham and S. -T. Yau).Scheduling tree-dags using FIFO queues: A control-memory tradeoff,

*Journal of Parallel and Distributed Computing***33**(1996), 55-68, (with Sandeep N. Bhatt, Tom Leighton and Arny Rosenberg).

## 1995

Pebbling a chessboard,

*Amer. Math. Monthly***102**(1995), 113-123, (with Ron Graham, John Morrison and Andrew Odlyzko).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).On the cover polynomial of a digraph,

*J. Combinatorial Theory*(B)**65**(1995), 273-290, (with R. L. Graham).

## 1994

A Harnack inequality for homogeneous graphs and subgraphs,

*Communications on Analysis and Geometry***2**(1994), 627-640, also in Turkish J. Math.**19**(1995), 273-290, (with S.-T. Yau).Eigenvalues of graphs,

*Proceedings of the International Congress of Mathematicians*(Zurich, 1994), Birkhäuser Verlag, Berlin, 1333-1342.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äuser, Boston, 1994, 97-126, (with Bertram Kostant and Shlomo Sternberg).Routing permutations on graphs via matchings,

*SIAM J. Discrete Math.***7**(1994) 513-530, (with Noga Alon and R. L. Graham).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.***12**, no. 1 (1994), 23-32.An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian,

*SIAM J. Discrete Math.***7**(1994), 443-457, (with V. Faber and Thomas A. Manteuffel).Several generalizations of Weil's sums,

*J. of Number Theory***49**(1994) 95-106.Even cycles in directed graphs,

*SIAM J. Discrete Math.***7**(1994) 474-483, (with Wayne Goddard and D. J. Kleitman).

## 1993

Communication complexity and quasi-randomness,

*SIAM J. Discrete Math*.**6**(1993), 110-123, (with Prasad Tetali).The Laplacian of a hypergraph, in

*Expanding graphs*(Princeton, NY, 1992), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 10, Amer. Math. Soc., Providence, RI, 1993, 21-36.Chordal completions of grids and planar graphs, in

*Planar graphs*(New Brunswick, NJ, 1991), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 9, Amer. Math. Soc., Providence, RI, 1993, 37-40, (with D. Mumford).On hypergraphs having evenly distributed subhypergraphs,

*Disc. Math.*111 (1993), 125-129, (with Ron Graham).A note on constructive lower bounds for the Ramsey numbers R(3,t),

*J. Comb. Theory*(B)**57**(1993), 150-155, (with R. Cleve and P. Dagum).Mathematics and the Buckyball, (this is a somewhat different version from the one that appeared in

*American Scientist***81**, No. 1., (1993) 56-71), (with Shlomo Sternberg).

## 1992

The number of different distances determined by a set of points in the Euclidean place,

*Discrete and Computational Geometry***7**(1992), 1-11, (with E. Szemeredi and W.T. Trotter).Tolerating faults in synchronization networks,

*Parallel processing: CONPAR 92---VAPP V*(Lyon, 1992), Lecture Notes in*Comput. Sci.*, 634, Springer, Berlin, 1992, 1-12, (with S. N. Bhatt, F. T. Leighton and A. L. Rosenberg).Quasi-ransom subsets of Z

_{n},*J. Comb. Theory*(A)**61**(1992), 64-86, (with R. L. Graham).Laplacian and vibrational spectra for homogeneous graphs,

*J. Graph Theory***16**(1992), 605-627, (with Shlomo Sternberg).Cohomological aspects of hypergraphs,

*Trans. Amer. Math. Soc.***334**(1992), 365-388, (with R. L. Graham).Universal cycles for combinatorial structures,

*Discrete Math.***110**(1992), 43-59, (with P. Diaconis and R. L. Graham).Efficient embeddings of trees in hypercubes,

*SIAM Journal on Computing***21**(1992), 151-162, (with S. Bhatt, F. T. Leighton and A. Rosenberg).Subgraphs of a hypercube containing no small even cycles,

*J. Graph Theory***16**(1992), 273-286.Graphs with small diameter after edge deletion,

*Discrete Applied Math*.**37/38**(1992), 73-94.Maximum cuts and quasirandom graphs, in

*Random Graphs*, John Wiley and Sons (1992), 23-33, (with R.L. Graham).

## 1991

Quasi-random set systems,

*J. Amer. Math. Soc.***4**(1991), 151-196, (with R. L. Graham).Constructing random-like graphs,

*Probabilistic Combinatorics and Its Applications*, (B. Bollobas ed.), Amer. Math. Soc., Providence, (1991), 21-55.Quasi-random tournaments,

*J. of Graph Theory***15**(1991), 173-198, (with R.L. Graham).A note on finding a strict saddlepoint,

*Amer. Math. Monthly***98**(1991), 418-419, (with Daniel Bienstock, Michael Fredman, Alejandro A. Schaffer, Peter W. Shor and Subhash Suri).Improved separators for planar graphs,

*Graph Theory, Combinatorics, and Applications*, John Wiley and Sons, (1991), 265-270.Regularity lemmas for hypergraphs and quasi-randomness,

*Random Structures and Algorithms***2**(1991), 241-252.

## 1990

Quasi-random classes of hypergraphs,

*Random Structures and Algorithms***1**(1990), 363-382. Corrigendum.On graphs not containing prescribed induced subgraphs, in

*A Tribute to Paul Erdős*, Cambridge University Press (1990), 111-120, (with R.L. Graham).The Maximum number of edges in 2K

_{2}-free graphs of bounded degree,*Discrete Math.***81**(1990), 129-135, (with A. Gyarfas, W. T. Trotter and Z. Tuza).Universal graphs and induced-universal graphs,

*J. Graph Theory***14**(1990) 443-454.Separator theorems and their applications,

*Paths, Flows and VLSI-Layout*, Springer-Verlag, Berlin (1990), 17-34.Quasi-random hypergraphs,

*Random Structures and Algorithms***1**(1990), 105-124, (with R.L. Graham).

## 1989

Quasi-random graphs,

*Combinatorica***9**(1989), 345-362, (with R. L. Graham and R. M. Wilson).Quasi-random hypergraphs,

*Proc. Natl. Acad. Sci. USA***86**(1989), 8175-8177, (with R.L. Graham).Pebbling in hypercubes,

*SIAM J. Disc. Math.***2**(1989), 467-472.Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs,

*Discrete & Computational Geometry***4**(1989), 183-190.Diameters and eigenvalues,

*J. of the Amer. Math. Soc.***2**(1989), 187-196.Graphs with small bandwidth and cutwidth,

*Discrete Math.***75**(1989), 113-119, (with P.D. Seymour).Optical orthogonal codes: design, analysis and applications,

*IEEE Trans. on Information Theory***35**, No. 3, (1989), 595-604, (with J. Salehi and V. Wei). Erratum.A dynamic location problem for graphs,

*Combinatorica***9**(1989), 111-131, (with R. L. Graham and M. Saks).Universal graphs for bounded-degree trees and planar graphs,

*SIAM J. Discrete Math.***2**(1989), 145-155, (with S. Bhatt, F. T. Leighton and A. L. Rosenberg).Steiner trees on a checkerboard,

*Math. Magazine***62**(1989), 83-96, (with Martin Gardner and R. L. Graham).

## 1988

On the fractional covering number of hypergraphs,

*SIAM J. on Discrete Math.***1**(1988), 45-49, (with Z. Furedi, M. R. Garey and R. L. Graham).Optimal simulations by butterfly networks,

*Proc. of the Twentieth Annual ACM Symposium on Theory of Computing,*(1988), 192-204, (with S. N. Bhatt, Jia-Wei Hong, F. T. Leighton and A. L. Rosenberg).On induced subgraphs of the cube,

*J. Comb. Th.*(A)**49**(1988), 180-187, (with Z. Furedi, R.L. Graham and P. Seymour).The average distance and the independence number,

*J. Graph Theory***12**(1988), 229-235.Pursuit-evasion games on graphs,

*J. Graph Theory***12**(1988), no. 2, 159-167, (with J.E. Cohen and R.L. Graham).Labelings of graphs,

*Selected Topics in Graph Theory***3**, Academic Press, San Diego, CA, 1988, 151-168.Explicit construction of linear sized tolerant networks,

*Discrete Math.***72**(1988), 15-19, (with N. Alon).The diameter of a cycle plus a random matching,

*SIAM J. on Discrete Math.***1**(1988), 328-333. (with B. Bollobás)Self-organizing sequential search and Hilbert's inequalities,

*J. Comp. System Sc.***36**(1988), 148-157, (with D. J. Hajela and P. D. Seymour).Quasi-random graphs,

*Proc. Natl. Acad. Sci. USA*,**85**(1988), 969-970, (with R. L. Graham and R. M. Wilson).

## 1987

The maximum number of edges in a 3-graph not containing a given star,

*Graphs and Combinatorics***3**(1987), 111-126, (with P. Frankl).Diameters of graphs: old problems and new results,

*Congressus Numerantium***60**(1987), 295-317.Dynamic search in graphs,

*Discrete Algorithms and Complexity*(1987), 351-387, (with R. L. Graham and M. Saks).Highly irregular graphs,

*J. Graph Theory***11**(1987), 235-249, (with Yousef Alavi, Gary Chartrand, Paul Erdős, R. L. Graham and Ortrud R. Oellermann).Random walks arising in random number generation,

*Ann. Probab.***15**(1987), no. 3, 1148-1165, (with P. Diaconis and R.L. Graham).On unavoidable hypergraphs,

*J. Graph Theory***11**(1987), 251-263, (with P. Erdős).Embedding graphs in books: a layout problem with applications to VLSI design,

*SIAM J. Algebraic Discrete Methods***8**(1987), no. 1, 33-58, (with F.T. Leighton and A.L. Rosenberg).The forwarding index of communication networks,

*IEEE Trans. Inform. Theory***33**(1987), no. 2, 224-232, (with E.G. Coffman, Jr., M.I. Reiman, and B.E. Simon).

## 1986

Monotone subsequences in (0,1)-matrices,

*Graphs Combin.***2**(1986), no. 1, 31-36, (with P.C. Fishburn and V.K. Wei).The relationship between switch capacity and network capacity in packet switched networks,

*Bell Laboratories Internal Memorandum*, 1986, (with R.R.Goldberg).Some intersection theorems for ordered sets and graphs,

*J. Combin. Theory Ser.*(A)**43**(1986), no. 1, 23-37, (with R.L. Graham, P. Frankl, and J.B. Shearer).Optimal simulations of tree machines,

*27th Annual Symposium on Foundations of Computer Science*(1986), 274-282, (with S. N. Bhatt, F. T. Leighton and A. L. Rosenberg).Minced trees, with applications to fault-tolerant VLSI processor arrays,

*Math. Systems Theory***19**(1986), 1-12, (with A. L. Rosenberg).Partitioning circuits for improved testability,

*4th MIT Conf. on Advanced Research in VLSI*, (C. E. Leiserson, ed.), The MIT Press, Cambridge (1986), 91-106, (with S. N. Bhatt, A. L. Rosenberg).

## 1985

Self-organizing sequential search and Hilbert's inequalities,

*Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing***8**(1985), 217-223, (with D. J. Hajela and P. D. Seymour).On the addressing problem for directed graphs,

*Graphs Combin.***1**(1985), no. 1, 41-50, (with R.L. Graham, and P.M. Winkler).Strongly connected orientations of mixed multigraphs,

*Networks***15**(1985), no. 4, 477-484, (with M.R. Garey and R.E. Tarjan).Cross-monotone subsequences,

*Order***1**(1985), no. 4, 351-369, (with P.C. Fishburn and V.K. Wei).Extremal subgraphs for two graphs,

*J. Combin. Theory*(B)**38**(1985), no. 3, 248-260, (with P. Erdős and J. Spencer).Coding strings by pairs of strings,

*SIAM J. Algebraic Discrete Methods***6**(1985), no. 3, 445-461, also in*Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983)*Congr. Numer.**39**(1983), 183-191, (with R.E. Tarjan, W.J. Paul, and R. Reischuk).Quantitative forms of a theorem of Hilbert,

*J. Combin. Theory Ser.*(A)**38**(1985), no. 2, 210-216, (with T.C. Brown, P. Erdős, and R.L. Graham).On the cutwidth and the topological bandwidth of a tree,

*SIAM J. Algebraic Discrete Methods***6**(1985), no. 2, 268-277.

## 1984

On irregularities of distribution,

*Finite and infinite sets*, Vol. I, II (Eger, 1981), 181-222, Colloq. Math. Soc. János Bolyai, 37, North-Holland, Amsterdam, 1984, (with R. L. Graham).The number of different distances determined by n points in the plane,

*J. Combin. Theory Ser.*(A)**36**(1984), no. 3, 342-354.On optimal linear arrangements of trees,

*Computers and Mathematics with Applications***10**(1984), 43-60.Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs,

*Discrete Math.***50**(1984), no. 1, 15-28, (with A. R. Calderbank and D. Sturtevant).Diameter bounds for altered graphs,

*J. Graph Theory***8**(1984), no. 4, 511-534, (with M. R. Garey).Applications of topological electron-counting theory to polyhedral metal clusters,

*Organic Chemistry***23**(1984), 1257-1266, (with B.K. Teo and G. Longoni).Diameters of communication networks,

*Mathematics of information processing*(Louisville, Ky., 1984), 1-18,*Proc. Sympos. Appl. Math*.**34**Amer. Math. Soc., Providence, RI, 1986.Embedding graphs in books: a layout problem with applications to VLSI design,

*Graph theory with applications to algorithms and computer science*(Kalamazoo, Mich., 1984), 175-188, Wiley-Intersci. Publ., Wiley, New York, 1985, (with F.T. Leighton and A.L. Rosenberg).

## 1983

A survey of bounds for classical Ramsey numbers,

*J. Graph Theory***7**(1983), no. 1, 25-37, (with C.M. Grinstead)Perfect storage representations for families of data structures,

*SIAM J. Algebraic Discrete Methods***4**(1983), no. 4, 548-565, (with A.L. Rosenberg and Lawrence Snyder).Diogenes: A methodology for designing fault-tolerant VLSI processor arrays,

*FTCS 13th Annual International Symposium Fault-Tolerant Computing*(1983), 26-32, (with F.T. Leighton and A.L.Rosenberg).On unavoidable graphs,

*Combinatorica***3**(1983), no. 2, 167-176, (with P. Erdős).Unavoidable stars in 3-graphs,

*J. Combin. Theory Ser.*(A)**35**(1983), no. 3, 252-262.On universal graphs for spanning trees,

*Journal of London Math. Soc.***27**(1983), 203-211 (with R. L. Graham).Edge-colored complete graphs with precisely colored subgraphs,

*Combinatorica***3**(1983), no. 3-4, 315-324, (with R.L. Graham).On the decomposition of graphs into complete bipartite subgraphs,

*Studies in Pure Mathematics Akadémiai Kiadó, Budapest,*(1983) 95-101, (with P. Erdős and J. Spencer).On a Ramsey-type problem,

*J. Graph Theory***7**(1983), no. 1, 79-83.On complete bipartite subgraphs contained in spanning tree complements,

*Studies in Pure Mathematics*, (ed.-in-chief P. Erdős)*Akadémiai Kiadó*, Budapest, (1983) 83-90, (with B. Bollobas and R. L. Graham).

## 1982

A new bound for Euclidean Steiner minimal trees,

*Discrete geometry and convexity*(New York, 1982), 328-346,*Ann. New York Acad. Sci*.**440**, New York Acad. Sci., New York, 1985, (with R. L. Graham).Triangle-free graphs with restricted bandwidth,

*Progress in graph theory*(Waterloo, Ont., 1982), 175-190,*Academic Press*, Toronto, ON, 1984, (with W.T. Trotter, Jr.).On the minimum dominating pair number of a class of graphs,

*Caribbean J. Math.***1**(1982), no. 2, 73-76, (with R.L. Graham, E.J. Cockayne, and D.J. Miller).Minimal decompositions of hypergraphs into mutually isomorphic subhypergraphs,

*J. Comb. Th.*(A)**32**(1982), 241-251, (with P. Erdős and R. L. Graham).Tiling rectangles with rectangles,

*Math. Mag.***55**(1982), no. 5, 286-291, (with E. N. Gilbert, and R. L. Graham).On graphs which contain all sparse graphs,

*Annals of Discrete Math*.**12**(1982), 21-26, (with L. Babai, P. Erdős, R. L. Graham, and J. Spencer).On packing two-dimensional bins,

*SIAM J. Algebraic Discrete Methods***3**(1982), no. 1, 66-76, (with M. R. Garey and D. S. Johnson).The number of relation graphs,

*Bell Laboratories Internal Memorandum*, 1982, (with F. K. Hwang and D. H. Krantz).A note on subtrees in tournaments,

*Bell Laboratories Internal Memorandum*, 1982.

## 1981

Efficient realization techniques for network flow patterns,

*Bell System Tech. J.***60**(1981), no. 8, 1771-1786, (with R. L. Graham and F. K. Hwang).On irregularities of distribution of real sequences,

*Proc. Nat. Acad. Sci. U.S.A.***78**(1981), no. 7, part 1, 4001, (with R.L. Graham)Recent results in graph decompositions,

*Combinatorics*(Swansea, 1981), pp. 103-123, London Math. Soc. Lecture Note Ser.**52**, Cambridge Univ. Press, Cambridge-New York, 1981, (with R. L. Graham).Universal caterpillars,

*J. Comb. Th. (B)***31**(1981), 348-355, (with R. L. Graham and J. Shearer).On the permanents of complements of the direct sum of identity matrices,

*Adv. in Applied Math.***2**(1981), 121-137, (with P. Diaconis, R. L. Graham, and C. L. Mallows).Some problems and results on labelings of graphs,

*The Theory and Applications of Graphs*(ed. G. Chartrand), John Wiley and Sons (1981), 255-264.On the bandwidths of a graph and its complement,

*The Theory and Applications of Graphs*(ed. G. Chartrand), John Wiley and Sons (1981), 243-253, (with P. Z. Chinn, P. Erdős and R. L. Graham).On trees containing all small trees,

*The Theory of Applications of Graphs*(ed. by G. Chartrand) John Wiley and Sons, (1981) 265-272, (with R. L. Graham and D. Coppersmith).Minimal decomposition of graphs into mutually isomorphic subgraphs,

*Combinatorica***1**(1981), 13-24, (with P. Erdős and R. L. Graham).A note on constructive methods for Ramsey numbers,

*J. Graph Theory***5**(1981), 109-113.On Steiner trees for bounded point sets,

*Geometriae Dedicata***11**(1981), 353-361, (with R. L. Graham).On the decompositions of graphs,

*SIAM J. Alg. Disc. Methods***2**(1981), 1-12.Rotatable graceful graphs,

*Ars Combinatoria***11**(1981), 239-250, (with F. K. Hwang).

## 1980

On unimodality for linear extensions of partial orders,

*SIAM J. Alg. Disc. Methods***1**(1980), 405-410, (with R. L. Graham and F. C. Fishburn).The connection patterns of two complete binary trees,

*SIAM J. Alg. Disc. Methods***1**(1980), 322-335, (with F. K. Hwang).On unimodal subsequences,

*J. Comb. Th. (A)***29**(1980), 267-279.Optimal spreading in

*n*-dimensional rectilinear grids,*Stud. Appl. Math.***62**(1980), 67-74, (with D. J. Kleitman (PECK)).On switching networks and block designs, II,

*Bell System Tech. J.***59**(1980), 1165-1173.On the coverings of graphs,

*Discrete Math.***30**(1980), 89-93.

## 1979

On universal graphs,

*Annals of the New York Academy of Sciences***319**(1979), 136-140, (with R. L. Graham).Minimal decompositions of two graphs into pairwise isomorphic subgraphs,

*Proceedings of the 10th Southeastern Conf. on Comb., Graph Theory and Computing*(1979), 3-18, (with P. Erdős, R.L. Graham, S.M. Ulam and F.F. Yao).Maximum antichains of rectangular arrays,

*J. Comb. Theory***27**(1979), 397-400, (with R. L. Graham, P. Erdős, D. J. Kleitman, D. West, and G. Purdy (G. W. Peck)).On concentrators, superconcentrators, generalizers, and nonblocking networks,

*Bell System Tech. J.***58**(1979), 1765-1777.On the product of the point and line covering numbers of a graph,

*Annals of the New York Academy of Sciences***319**(1979), 597-602, (with P. Erdős and R. L. Graham).The largest minimal rectilinear Steiner trees for a set of

*n*points enclosed in a rectangle with given perimeter,*Networks***9**(1979), 19-36, (with F. K. Hwang).

## 1978

A conjectured minimum valuation tree, Problems and solutions,

*SIAM Review***20**(1978), 601-604.Zone-balanced networks and block designs,

*Bell System Tech. J.***57**(1978), 2957-2971.The number of Baxter permutations,

*J. Comb. Th. (A)***24**(1978), 382-394, (with R. L. Graham, V. E. Hoggatt, and M. Kleiman).Optimal multistage switching networks,

*IEEE Trans. on Communications*COM-26 (1978), 1282-1287.On blocking probabilities for a class of linear graphs,

*Bell Systems Tech. J.***57**(1978), 2915-2925, (with F. K. Hwang).A generalization of Takagi's Theorem on optimal channel graphs,

*Bell System Tech. J.***57**(1978), 171-178, (with F. K. Hwang).On partitions of graphs into trees,

*Discrete Math.***23**(1978), 23-30.An algebraic approach to switching networks, Bell Laboratories Internal Memorandom, 1978.

Steiner trees for ladders,

*Annals of Discrete Math.***2**(1978), 173-200, (with R. L. Graham).Do stronger players win more knockout tournaments?,

*JASA***73**(1978), 593-596, (with F. K. Hwang).A lower bound for the Steiner tree problem,

*SIAM J. on Applied Math. (B)***34**(1978), 27-36, (with F. K. Hwang).On graphs which contain all small trees,

*J. Comb. Th. (B)***24**(1978), 14-23, (with R. L. Graham).

## 1977

A problem on blocking probabilities in connecting networks,

*Networks***7**(1977), 185-192, (with F. K. Hwang).On blocking probabilities for switching networks,

*Bell System Tech. J.***56**(1977), 1431-1446, (with F. K. Hwang).Some results on hook lengths,

*Discrete Math*.**20**(1977), 33-40, (with J. E. Herman).

## 1976

On switching networks and block designs,

*Conf. Record of the 10th Asilomar conf. on Circuits System and Computers*(1976), 212-218.On the set of distances determined by the union of arithmetic progressions,

*Ars Combinatoria***1**(1976), 57-76, (with R. L. Graham).On graphs which contain all small trees II,

*Colloquia Mathematica Societatis János Bolyai, Keszthely, Hungary*, (1976), 213-223, (with R. L. Graham and N. Pippenger).Steiner trees for the regular simplex,

*Bull. of the Inst. of Math., Academia Sinica*,**4**(1976), 313-325, (with E. N. Gilbert).

## 1975

On multicolor Ramsey numbers for complete bipartite graphs,

*J. Comb. Th. (B)***18**(1975), 164-169, (with R. L. Graham).Optimal Rearrangeable graphs,

*Bell System Tech. J.***54**(1975), 1647-1661.

## 1974

On triangular and cyclic Ramsey numbers with k colors,

*Graphs and Combinatorics, Lecture Notes*, No.**406**, (1974), 236-242, Springer-Verlag, New York.

## 1973

On the Ramsey numbers N(3,3,...,3;2),

*Discrete Math*.**5**(1973), 317-321.