***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 7th April, 3:00 in Fine Hall 224.
 
Speaker: Hehui Wu (U. Mississippi)

Title: Bipartition with degree constraint

A well-known result of Stiebitz states that given a graph G and two  
functions a, b: V(G)-> N such that d_G(v)> a(v)+b(v) for each v,  
there is a nontrivial vertex partition (A, B), such that  
d_A(v) >= a(v)  for all v in A and d_B(v) >= b(v) for all v in B. 
In this talk, we will report some results on two analogous  
open problems.

Norin conjectured that if G is a graph with e(G) >= (s+t+1)v(G)  
for non-negative real number s and t, then there exists a  
nontrivial vertex partition (A,B),  such that e(G[A]) >= s|A| and  
e(G[B]) >= t|B|. With Csoka, Lo, Norin and Yepremyan, we prove  
this when s=t. In general, if e(G) >= (s+t+1)(v(G)-1), then there  
is a vertex partition (A,B), such that e(G[A]) >= s(|A|-1) and  
e(G[B]) >= t(|B|-1).  By using this, we answer a question asked by  
Reed and Scott.

A ``bisection'' is a vertex partition (A,B) with ||A|-|B||\le 1.  
Bollobas and Scott proposed a conjecture that there exists a  
bisection (A,B) such that |N_B(v)| >= (d_G(v)-1)/2 for every
v in A and |N_A(v)| >= (d_G(v)-1)/2 for every v in B. 
Recently, with Jie Ma, we proved an approximate result of  
this conjecture, that |N_B(v)| >= (1/4-f(d_G(v),n))d_G(v)  
for every v in A and |N_A(v)| >= (1/4-f(d_G(v),n))d_G(v) for 
every v in B, where f(k,n)->0 as k and n go to infinity. 
We also strengthen a result of Kuhn and Osthus.



                       -----------

Next week: Maya Stein

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)