A Continuous Analogue of the Girth Problem

✍ Scribed by Alon Amit; Shlomo Hoory; Nathan Linial

• Book ID: 102585385
• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 183 KB
• Volume: 84
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2001.2088

✦ Synopsis

Well! I've often seen a cat without a grin,'' thought Alice; ''but a grin without a cat! It's the most curious thing I ever saw in all my life!'' -Lewis Carroll, Alice in Wonderland

Let A be the adjacency matrix of a d-regular graph of order n and girth g and d=l 1 \ • • • \ l n its eigenvalues. Then ; n j=2 l i j =nt i -d i , for i=0, 1, ..., g -1, where t i is the number of closed walks of length i on the d-regular infinite tree. Here we consider distributions on the real line, whose ith moment is also nt i -d i for all i=0, 1, ..., g -1. We investigate distributional analogues of several extremal graph problems involving the parameters n, d, g, and L=max |l 2 |, |l n |. Surprisingly, perhaps, many similarities hold between the graphical and the distributional situations. Specifically, we show in the case of distributions that the least possible n, given d, g is exactly the (trivial graph-theoretic) Moore bound. We also ask how small L can be, given d, g, and n, and improve the best known bound for graphs whose girth exceeds their diameter.