[Colloquium] REMINDER: Raghav Kulkarni Talk Today

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, March 30, 2009
Time: 3:45 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Raghav Kulkarni

From:		University of Chicago

Website: 	 http://www.cs.uchicago.edu/people/raghav

Title:    Any Monotone Property of Sparse Graphs is Evasive

Abstract:    We call an n-vertex graph "sparse" if its number of edges
is O(n). A graph property is said to be ''evasive'' if, in order to
decide its membership, one needs to query all {n \choose 2} possible
edges in wosrt case. Karp conjectures that any non-trivial monotone
graph property must be evasive. It is a longstanding open question. We
prove Karp's conjecture when restricted to 'sparse' graphs, i.e., we
show that any non-trivial monotone decreasing property of n-vertex
'sparse' graphs is 'evasive' for all large enough n. We use the
topological approach proposed by Kahn, Saks and Sturtevant [1984] as a
black box. The extra component of our method is a further connection
to analytic number theory. In particular, we construct new group
actions which rely crucially on some deep and interesting properties
of the numbers. Under the Generalized Reimann Hypothesis, we can
further stregthen our result to show that any monotone property of
''weakly sparse'' graphs is evasive, where 'weakly sparse' means that
the number of edges are bounded by O(n^{5/4 - \epsilon}). We give an
evidence that this can be further improved to O(n^3/2) but these
bounds are far from the desired {n \choose 2} bound. This is a joint
work with Anandam Banerjee, Department of Mathematics, Northeastern
University and Vipul Naik, Department of Mathematics, University of
Chicago.


Refreshments will be served prior to the talk in RY 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090330/43d30ca4/attachment.htm