From rendl@fmatbds01.tu-graz.ac.at Tue Oct 24 10:46:54 1995
Received: from fmatbds01.tu-graz.ac.at (fmatbds01.tu-graz.ac.at [129.27.149.10]) by orion.math.uwaterloo.ca (8.6.12/8.6.12UW) with SMTP id KAA03192 for <hwolkowi@orion.math.uwaterloo.ca>; Tue, 24 Oct 1995 10:46:49 -0400
Received: by fmatbds01.tu-graz.ac.at (5.57/Ultrix3.0-C)
	id AA06416; Tue, 24 Oct 95 15:56:00 +0100
Date: Tue, 24 Oct 95 15:56:00 +0100
From: rendl@fmatbds01.tu-graz.ac.at (Franz Rendl)
Message-Id: <9510241456.AA06416@fmatbds01.tu-graz.ac.at>
To: hwolkowi@orion.math.uwaterloo.ca
Subject: gp, qap
Cc: karisch@fmatbds02.tu-graz.ac.at
Status: R

Hi, it would be nice if you advertise our results in New Orleans..
Stefan will send you the latex files, you wanted...

we are just finishing the graph partition paper. this is going to
be very interesting..
for instance: we show that our eigenvalue bound with julie deteriorates
rather quickly as k increases:
the approximation error for k = 2 is at least 13.9 % 
for k = 3 it is at least 33 %
for k = 4 it is at least 50 %
for k = 5 it is at least 66 %
(to be precise, we show that there are (simple) graphs where the
ratio of the eigenvalue bound and the best (here maximal k-partition,
differ by these quantities), so the true worst case ratio may (and
probably will) be much worse.

more later, franz

