DIMACS Center, CoRE Building, Rutgers University, Piscataway, NJ

**Organizers:****János Komlós**, Rutgers University, komlos@math.rutgers.edu**Endre Szemerédi**, Rutgers University, szemered@cs.rutgers.edu

DIMACS/DIMATIA/Renyi Working Group on Extremal Combinatorics Main Page

DIMACS/DIMATIA/Renyi Tripartite Partnership

This meeting will continue the work of the working group on two general topics, extremal graph theory and extremal problems arising from combinatorial search and testing.

Extremal graph theory deals with graphs satisfying specified constraints and optimizing some criteria. We will investigate a number of specific questions of current research interest in this field, which has played a fundamental role in the history of graph theory. Typically, we are interested in Turán-type extremal problems. Here, a familyLof sample graphs is fixed and we consider various conditions on a graph onnvertices that does not contain any graph inLas a subgraph (not necessarily induced). The most famous such problem asks for the maximum possible number of edgesext(n,L)in a graphGonnvertices which does not have any subgraph inL. Alternatively, we may ask for the maximum possible valuedex(n,L)of the minimum degree of a graphGonnvertices which has no graph in the familyLas a subgraph. It is easy to see thatdex(n,L)<(2/n)ext(n,L). The upper bound is almost achieved in many interesting cases, and we will try to identify conditions under which this occurs. A variant of Turán-type problems is the generalized matching problem: to find many vertex-disjoint copies of a fixed graph in a large graph. Here too, the minimal degree ofGis the natural quantity to work with. In approaching some problems in extremal graph theory, two standard tools are the Regularity Lemma and the Blow-up Lemma. In the last few years, various promising analogues of these tools were developed for hypergraphs.

The working group also investigates the theory and algorithms of combinatorial group testing, with emphasis on connections to coding theory and combinatorial design. These topics are also of interest to the Working Group on Algebraic and Geometric Methods in Combinatorics. To identify all positive cases in a large population of items, group testing proceeds by grouping the items into subsets, testing if a subset contains at least one positive item, and then identifying all positive items through iteration of group tests. We investigate problems involving testing properties of evolving objects. These problems can be formulated as determining whether a functionfhas propertyPor isepsilon-farfrom any function with propertyP. A property testing algorithm is given a sample of the value offon instances drawn according to some distribution, and, in some cases, it is also allowed to queryfon instances of its choice. The concept was defined by Goldreich, Goldwasser and Ron. The functionf, viewed as an object itself, can be of combinatorial, geometric, or algebraic nature. Thus far all property tests are designed to work with static objects even though in reality the studied object (e.g., the hyper-link graph of the Internet) can be constantly changing. We will investigate efficient methods for testing changing objects and seek to determine the frequency with which we have to draw samples if we want to keep the computed information up to date.

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on May 13, 2004.