Hoffman's Ratio Bound

Willem H. Haemers

Hoffman's Ratio Bound

Willem H. Haemers

Econometrics and OR

Research output: Working paper › Other research output

101 Downloads (Pure)

Abstract

Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.

Original language	English
Place of Publication	Ithaca
Publisher	Cornell University Library
Publication status	Published - 10 Feb 2021

Publication series

Name	arXiv
Publisher	Cornell University
Volume	2102.05529

Keywords

math.CO

Access to Document

2102.05529(1)Submitted manuscript, 85.5 KB

https://arxiv.org/abs/2102.05529

Cite this

@techreport{2569d82ca90b424b879b08145c9a77ee,

title = "Hoffman's Ratio Bound",

abstract = "Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations. ",

keywords = "math.CO",

author = "Haemers, {Willem H.}",

year = "2021",

month = feb,

day = "10",

language = "English",

series = "arXiv",

publisher = "Cornell University Library",

type = "WorkingPaper",

institution = "Cornell University Library",

}

TY - UNPB

T1 - Hoffman's Ratio Bound

AU - Haemers, Willem H.

PY - 2021/2/10

Y1 - 2021/2/10

N2 - Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.

AB - Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.

KW - math.CO

M3 - Working paper

T3 - arXiv

BT - Hoffman's Ratio Bound

PB - Cornell University Library

CY - Ithaca

ER -

Hoffman's Ratio Bound

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this