Browse Prior Art Database

APPLICATIONS OF RAMSEY STYLE STHEOREMS TO EIGENVALUE OF GRAPHS

IP.com Disclosure Number: IPCOM000148476D
Original Publication Date: 1974-Jun-13
Included in the Prior Art Database: 2007-Mar-30

Publishing Venue

Software Patent Institute

Related People

Hoffman, A.J.: AUTHOR [+2]

Abstract

APPLICATIONS OF RAMSEY STYLE THEOREMS TO EIGENVALUE OF GRAPHS::: Mathematical Sciences Department IBM Watson Research CenterY orktown Heights, New York Notes of a lecture to be given at NATO Advanced Study Institute on Combinatorics in the Netherlands, July 1974 t The preparation of this manuscript was supported (in part) by U,S. Army contract #DAHC04-72-C-0023. RC 4882 (#21746) June 1 3 , 1 9 7 4 Mathematics Copies may be requested from:IBM Thomas J. Watson Research Center Post Office Box 218Yorktown Heights, New York 10598 1, INTRODUCTION Let G be a graph, A(G) its ad.jacency matrix, i. e., A=(a. .) 1J is given by 1J 0 otherwise . Thus, A A(G) is a symmetric matrix whose entries are 0 and 1,with every a..= 0. For any real symmetric A, we denote its eigenvalues 1J as is convenient. For A A(G), we sometimes write A .(G) or xi(^) 1 There have been many investigations in graph theory, experimental designs, group theory, etc. in which knowledge of properties of h .

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 26

APPLICATIONS OF RAMSEY STYLE THEOREMS TO EIGENVALUE OF GRAPHS:::

Mathematical Sciences Department IBM Watson Research Center
Y orktown Heights, New York

* Notes of a lecture to be given at NATO Advanced Study Institute on

Combinatorics in the Netherlands, July 1974

t The preparation of this manuscript was supported (in part) by

U,S. Army contract #DAHC04-72-C-0023.

RC 4882 (#21746) June 1 3 , 1 9 7 4 Mathematics

[This page contains 1 picture or other non-text object]

Page 2 of 26

Copies may be requested from:
IBM Thomas J. Watson Research Center Post Office Box 218
Yorktown Heights, New York 10598

[This page contains 1 picture or other non-text object]

Page 3 of 26

1, INTRODUCTION
Let G be a graph, A(G) its ad.jacency matrix, i. e., A=(a. .)

1J

is given by

1J 0 otherwise > .

Thus, A = A(G) is a symmetric matrix whose entries are 0 and 1,
with every a..= 0. For any real symmetric A, we denote its eigenvalues

1J

as is convenient. For A = A(G), we sometimes write A .(G) or xi(^)

1

      There have been many investigations in graph theory, experimental designs, group theory, etc. in which knowledge of properties of ( h . ( ~ ) )

1

- which we shall henceforth call the spectrum of G - has been very useful even where the eigenvalues are not mentioned in either the hypotheses
or conclusions of the theorems proved. These investigations furnish part of (the rest is natural curiosity) the motivation for study of questions where the eigenvalues play an explicit role. More specifically, we can ask (and sometimes answer) questions of the following type:
i

      (1) what properties of a graph control the magnitude of X (G) or X .(G)? We can answer this in a limited way for 1
h1,X2 and h

1

1 if i and j are adjacent vertices


a.. =

for X .(A(G)) or x~(A(G)) respectively.

1

[This page contains 1 picture or other non-text object]

Page 4 of 26

(2) If G is an induced subgraph of H,written GCH then (as we i

know from matrix theory), Xi(G) =< 1 .(H), X'(G) 2 A (H). Suppose we specify

1

that every vertex of H must have large valence. Then by how much i

must XI(H) exceed X.(G) or X (G) exceed A~(H)?

We can answer

thisfor X and X . 2
(3) Define a relationship - on V(G) to mean i - j if for every k i , aik=a jk' and let e(G) be the number of equivalence classes so defined. The examples

and

show that e(G) is not uniquely determined by the spectrum of G (which is (2,0,0,0, -2) in both cases). But is the magnitude e(G) roughly de- termined by the spectrum? The answer is yes in a sense to be made precise later (and this result will be completely proven in these notes, whereas other results will be sketched).
(4) What real numbers can be limit points of the {A 1(~)), as G 1

ranges over all graphs, or { X 2 ( ~ ) ] ,

. . . , or { X (G)] , etc. ? We know

1

the early limit points for { X (G)) and { A (G)).

1

      (5) Suppose (as is sometimes done) we represent G by the...