User:More than one half/sandbox

</nowiki> Fan Chung

• Fan Chung's biography

      Biography

Since Fan Chung was a high school student in Kaoshiung, Taiwan, she was inspired by her father who was an engineer to take up mathematics. In the National Taiwan University, because her major was mathematics, she had more chances to meet more excellent mathematicians. Through her learning, she was attracted by combinatorics and soon started to research it.

After Fan Chung graduated with a B.S in mathematics from the National Taiwan University, she went to the University of Pennsylvania for her graduate studies. Because Fan Chung's qualifying exam was the highest score and there was a huge gap between her and the next best student, she was noticed by Herbert Wilf who is the Professor of Mathematics at the University of Pennsylvania. Prof. Wilf pulled out Ramsey Theory and let Fan Chung to learn it. In fact, the Ramsey Theory became a major part of her doctoral dissertation.

In 1974, Fan Chung graduated with Ph.D from the university of Pennsylvania and started to work for the Mathematical Foundations of Computing Department at Bell Laboratories in Murray Hill, New Jersey. There were many other leading mathematicians who work with Fan Chung. At that time, she published many impressive mathematical papers with these mathematicians.

In 1983, Fan Chung was asked by Henry Pollak to become Research Manager. At the same year, Fan Chung got married with her second husband, Ron Graham who is the mathematician.

In 1990, Fan Chung decided to college to become a visiting professor at Harvard University.

In 1997, Fan Chung published Spectral graph theory. It studies how the spectrum of the Laplacian of a grah is related to its combinatorial properties. one year later, "Erdos on graphs" jointly written by Chung and her husband.

Since 1998, She is the distinguished professor of mathematics and computer science at the university of California, San diego.During these years, Fan Chung Published over 200 publications. There are many contributions to the area of Graph Theory.

• Fan Chung's research on spectral graph theory?

       * What is the spectral graph theory?
       * How does Fan Chung prove this Theory?
       * How does Fan Chung relate this Theory to certain graph theory problems?

Mentioning about the matrix, it always reminds people about the whole bunch of theories of matrix in linear algebra. However, Spectral graph theory as one of the most important theory in graph theory combines the algebra and graph perfectly. Algebraic methods treat many types of graphs efficiently. Fan Chung’s study in the spectral graph theory brings this “algebraic connectivity” of graphs into a new and higher level. Since the eigenvalue of the matrix plays a central role in the Spectral graph theory, we recall that a vector $\psi \,\!$ is an eigenvector of a matrix M with eigenvalue $\lambda \,\!$ if MFailed to parse (unknown function "\math"): {\displaystyle \psi\,\!<\math>=<math>\lambda\,\!} $\psi \,\!$

• Fan Chung's point of view about the graph theory.

       * How does Fan Chung use her knowledge of graph theory relate to problems in reality?
       * Fan Chung's research about the Network Games. (This is an example)

Spectral theorem and Rayleigh quotient

Optimization problems may be the most useful examples about the combinatorial significance of the eigenvalues and eigenvectors in symmetric matrices, especially for the Rayleigh quotient with respect to a matrix M.

Theorem Let M be a symmetric matrix and let x be the non-zero vector that maximize the Rayleigh quotient with respect to M. Then, x is an eigenvector of M with eigenvalue equal to the Rayleigh quotient. Moreover, this eigenvalue is the largest eigenvalue of M.

Proof Assume the spectral theorem. let the eigenvalues of M are $\lambda _{1}\leq \lambda _{2}\leq \cdots \leq \lambda _{n}$. Since {$v_{i}$}i is an orthonormal basis, any vector x in this basis is $x=\sum _{i}\ x\ v_{i}^{T}\ v_{i}$ The way to prove this formula is pretty easy. $v_{j}^{T}\sum _{i}v_{i}^{T}xv_{i}=\sum _{i}v_{i}^{T}xv_{j}^{T}v_{i}=(v_{j}^{T}x)v_{j}^{T}v_{j}=v_{j}^{T}x$ evaluate the Rayleigh quotient with respect to x:

${\frac {x^{T}Mx}{x^{T}x}}$

$=(\sum _{i}(v_{i}^{T}x)v_{i})^{T}M(\sum _{j}(v_{j}^{T}x)v_{j})$

$=(\sum _{i}(v_{i}^{T}x)v_{i})^{T})(\sum _{j}(v_{j}^{T}x)v_{j}\lambda _{j})$

$=\sum _{i,j}(v_{i}^{T}x)v_{i})^{T})(v_{j}^{T}x)v_{j}\lambda _{j})$

$=\sum _{j}(v_{j}^{T}x)(v_{j}^{T}x)\lambda _{j}$

$=\sum _{j}(v_{j}^{T}x)^{2}\lambda _{j}\leq \lambda _{n}\sum _{j}(v_{j}^{T}x)^{2}$

$=\lambda _{n}$

so the Rayleigh quotient is always less than $\lambda _{n}$.

Basic facts about the spectrum of a graph

Mostly, half of the main problems of spectral theory lie in deriving bounds on the distributions of eigenvalues. Here are some basic facts about eigenvalues of a graph. LEMMA For a graph G on n vertices, we have

(i): :$\sum _{i}\lambda _{i}\leq n$

with equality holding if and only if G has no isolated vertices.

(ii): For n≥ 2,

$\lambda _{1}\leq {\frac {n}{n-1}}$

with equality holding if and only if G is the complete graph on n vertices. Also, for a graph G without isolated vertices, we have

$\lambda _{n-1}\geq {\frac {n}{n-1}}$

(iii): For a graph which is not a complete graph, we have $\lambda _{1}\leq 1$.

(iv): If G is connected, then $\lambda _{1}$ >0. If $\lambda _{i}=0$ and $\lambda _{i+1}\neq 0$, then G has exactly i+1 connected components.

(v): For all i≤ n-1, we have

$\lambda _{i}\leq 2$,

with $\lambda _{n-1}$ = 2 if and only if a connected component of G is bipartite and nontrivial.

(vi): The spectrum of a graph is the union of the spectra of its connected components.

==Fan Chung and Bell Laboratories＝＝ In 1974, Fan Chung graduated from the University of Pennsylvania and became a member of Technical Staff working for the Mathematical Foundations of Computing Department at Bell Laboratories in Murray Hill, New Jersey. She worked under Henry Pollak. During this time, Fan Chung collaborate with many leading mathematicians who work for Bell Laboratories such as Ron Graham. In 1975, Fan Chung published her first joint paper with Ron Graham on Multicolor Ramsey Numbers for Complete Bipartite Graphs which was published in the Journal of Combinatorial Theory. In 1983 the Bell Telephone Company was split up. Since Henry Pollak joined and became head of a research unit within a new company, he asked Fan Chung to become Research Manager. Until 1990, Fan Chung was one of the first to receive the fellowship to spend a sabbatical at a university, she supervised many a lot of mathematicians in the unit. According to Fan Chung's words, although people respect her because of the power to make decisions with positions in management, she prefers to be respected because of her achievement of mathematics. Since then, she returns to the academic world. In 1995, Fan Chung took up the professorship at the University of Pennsylvania. After 3 years, she became the professor of Mathematics and Professor of Computer Science and Engineering at the University of California, San Diego.

Fan Chung and Ron Graham

In 1974, Fan Chung met with Ron Graham in Bell Laboratories. In 1975, They published their first joint paper On Multicolor Ramsey Numbers for Complete Bipartite Graphs. When Fan Chung works in the Bell Laboratories, her second child was born in 1977. However, her marriage was ended in divorce in 1982.

In 1983, She married to Ron Graham. In P Hoffman's book The man who loved only numbers, Graham talked about his marriage with Fan Chung. He said:

Many mathematicians would hate to marry someone in the profession. They fear their relationship would be too competitive. In our case, not only are we both mathematicians, we both do work in the same areas. So we can understand and appreciate what the other is working on, and we can work on things together and sometimes make good progress.

Fan Chung and Graham's marriage as Graham said becomes one of the most important factors to help Fan Chung achieves higher level in the academic world and challenges more and more problems in the graph theory. In 1998, one of the most important book appears. Erdos on graphs was jointly written by Fan Chung and her husband Graham. Many problems in graph theory made by Paul Erdos are listed in this book. Even though many of the Erdos problems presented in the book would remains open for years, this book provides many challenges to the mathematicians who are interested in the field of graph theory.

Fan Chung and Spectral Graph Theorem

Among Fan Chung's publications, her contributions to Spectral graph theory are important to this area of graph theory. From the first publications about undirected graphs to recent publications about the directed graphs, Fan Chung creates the solid base in the Spectral graph theory to the future graph theorist.

Spectral graph theory as one of the most important theory in graph theory combines the algebra and graph perfectly. Algebraic methods treat many types of graphs efficiently. According to the biography Fan Rong K Chung Graham, "Spectral graph theory studies how the spectrum of the Laplacian of a graph is related to its combinatorial properties."'.

In 1997, the American Mathematical Society published Fan Chung's book Spectral graph theory. This book becomes textbook in many universities and is the key to study Spectral graph theory for many mathematics students who are interested in this area. Fan Chung’s study in the spectral graph theory brings this “algebraic connectivity” of graphs into a new and higher level.

Eigenvalues and the Laplacian of a graph

Eigenvalues as one of the most important terms in the linear algebra plays a central role in the Spectral graph theory. In another word, certain eigenvalues are referred as "algebraic connectivity" of a graph. The study of graph eigenvalues connected more and more different areas in the mathematics. In this case, graph is not only graph, but also it has algebraic flavor because of the graph eigenvalues.

In a graph G, let $d_{v}$ denote the degree of the vertex v. Fist define the Laplacian for graphs without loops and multiple edges. Consider the matrix L,defined as follows:

$L(u,v)={\begin{cases}d_{v}&{\text{if u=v}},\\-1&{\text{if u and v are adjacent}},\\0&{\text{otherwise}}.\end{cases}}$

Let T denoted the diagonal matrix with the (v,v)-th entry having value $d_{v}$. The Laplacian of F is defined to be the matrix

$\ell _{u,v}={\begin{cases}1&{\mbox{if}}\ u=v\ {\mbox{and}}d_{v}\neq 0\\-{\frac {1}{\sqrt {d_{v}d_{u}}}}&{\text{if u and v are adjacent}},\\0&{\text{otherwise}}.\end{cases}}$

we can write

$\ell =T^{1/2}LT^{1/2}$

with the convention $T_{v,v}^{-1}=0$ for $d_{v}=0$. A graph is said to be nontrivial if it contains at least one edge.

The Laplacian is an operator on the function of g. When G is k-regular,

$\ell =I-{\frac {1}{k}}A$

Where A is the adjacency matrix of G and I is an identity matrix. All matrices are n × n where n is the number of vertices in G.

For a general graph without isolated vertices,

$\ell =T^{-1/2}LT^{1/2}=I-T^{-1/2}AT^{-1/2}$

$\ell =SS^{*}$.

Where S is the matrix whose rows are indexed by the vertices and whose columns are indexed by the edges of G such that each column corresponding to an edge e = {u, v} has an entry ${\frac {1}{{\sqrt {d}}_{u}}}$ in the row corresponding to u, an entry $-{\frac {1}{{\sqrt {d}}_{v}}}$ in the row corresponding to v, and has 0 entries elsewhere. (Note:$S^{*}$ denotes the transpose of S).

Since $\ell$ is symmetric, its eigenvalues are real and non-negative. We can use its characterization in terms of Rayleigh quotient of $\ell$.

Let g is an arbitrary function which assigns to each vertex v of G a real value g(v). We can treat g as a column vector.

${\frac {g,\ell _{g}}{g,g}}$

$={\frac {g,T^{-1/2}LT^{-1/2}g}{g,g}}$

$={\frac {f,Lf}{T^{1/2}f,T^{1/2}f}}$

$={\frac {\sum _{u~v}(f(u)-f(v))^{2}}{\sum _{v}f(v)^{2}d_{v}}}$

where $g=T^{1/2}f$ and $\sum _{u~v}$ denotes the sum over all unordered pairs {u,v} for which u and v are adjacent. $\sum _{u~v}(f(u)-f(v))^{2}$ is called the Dirichlet sum of G. The left hand side of the equation is Rayleigh quotient.

The eigenvalues of $\ell$ by $0=\lambda _{0}\leq \lambda _{1}\leq \cdots \lambda _{(}n-1)$. the set of $\lambda _{i}$ is usually called the spectrum of $\ell$ Let 1 be the function which assumes the value 1 on each vertex. Then $T^{1/2}1$ is an eigenfunction of $\ell$ with eigenvalue 0.