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 family L of sample graphs is fixed and we consider various conditions on a graph on n vertices that does not contain any graph in L as a subgraph (not necessarily induced). The most famous such problem asks for the maximum possible number of edges ext(n,L) in a graph G on n vertices which does not have any subgraph in L. Alternatively, we may ask for the maximum possible value dex(n,L) of the minimum degree of a graph G on n vertices which has no graph in the family L as a subgraph. It is easy to see that dex(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 of G is 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 function f has property P or is epsilon-far from any function with property P. A property testing algorithm is given a sample of the value of f on instances drawn according to some distribution, and, in some cases, it is also allowed to query f on instances of its choice. The concept was defined by Goldreich, Goldwasser and Ron. The function f, 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