06/01/2004 - Maximal Independent sets in graphs and Segre's problem; Van Vu, University of California, San Diego, Visiting MSR

From: Kelli McGee \(Kelly Services Inc\) (a-kellim@microsoft.com)
Date: Thu May 27 2004 - 14:12:33 PDT

  • Next message: Kelli McGee \(Kelly Services Inc\): "6/16/2004 Anomalous Diffusion and Polya Recurrence; Domokos Szász, Budapest University of Technology"

    You are invited to attend...

    ************************************************************************
    *****************************

    WHO: Van Vu

    AFFILIATION: University of California, San Diego, Visiting MSR

    TITLE: Maximal Independent sets in graphs and Segre's
    problem

    WHEN: Tue 6/01/2004

    WHERE: 113/1159 Research Lecture Room, Microsoft Research

    TIME: 3:30PM-5:00PM

    HOST: Jeong Han Kim

    ************************************************************************
    ******************************

    ABSTRACT:

    Consider the finite plane F(q)^2 over the field of q elements. An arc a
    set with no three elements on a line. An arc is maximal if it cannot be
    extended. B. Segre, in the fifties,

    Posed the following question:

     

    What are the possible cardinalities of a maximal arc?

     

    Segre's question is one of the main sources for research in finite
    geometry. In this talk, we will give a brief survey on the main
    developments concerning this question. Next, we discuss our recent
    result which shows that the possible cardinalities of a maximal arc form
    a dense set between the trivial upper and lower bounds.

     

    The proof blends tools from several areas of mathematics: algebra, graph
    theory and probability. Central to it is the following graph theoretical
    statement, which might be of independent interest:

     

    Let G be a d-regular graph on n points with girth at least 5. Then G
    contains a maximal independent set of size approximately (n log d)/d.

     

    (joint work with J.H. Kim).

     

    BIO:

    Van Vu is an associate professor at the department of mathematics at
    UCSD. Currently he is a long term visitor at the Theory group at
    Microsoft Research. He received his Ph.D. in 1998 under L. Lovasz at
    Yale and spent his postdoc years at IAS and Microsoft. He has received
    a Sloan fellowship and an NSF Career Award.

     


    _______________________________________________
    Theory-group mailing list
    Theory-group@cs.washington.edu
    http://mailman.cs.washington.edu/mailman/listinfo/theory-group

  • Next message: Kelli McGee \(Kelly Services Inc\): "6/16/2004 Anomalous Diffusion and Polya Recurrence; Domokos Szász, Budapest University of Technology"

    This archive was generated by hypermail 2.1.6 : Thu May 27 2004 - 14:13:26 PDT