==============================
                   Bar-Ilan Combinatorics Seminar
                   ==============================

The next meeting of the seminar will take place, IYH, on

(when)  Tuesday, 6 Nisan (March 31)
       12:00-13:30

(where) Room 201 (Math Dept Seminar Room),
       Math and CS Building (216), Bar-Ilan University

(who)   Chaya Keller (Hebrew University)

       will talk about

(what)  "Blocking perfect matchings in a geometric graph"

Abstract:

A perfect matching in a graph is a set of disjoint edges such
that every vertex belongs to one of them. A blocker in a graph
is a set of edges whose intersection with any perfect matching
in the graph is non-empty. In the setting of geometric graphs
(i.e., graphs whose vertices are points in the plane, and whose
edges are the segments connecting the vertices), the considered
perfect matchings are required also to be simple (i.e., the
edges do not intersect), and the blocker is defined similarly.

In this talk we discuss the minimal blockers for several classes
of graphs. For general graphs, it is easy to see that the minimal
possible blocker of the graph K_{2m} (the complete graph on 2m
vertices) has  2m-1  edges, and the minimal possible blocker of
K_{m,m} (the complete bipartite graph with sets of m vertices) has
m  edges.

It appears that for a general geometric graph on  2m  vertices, the
minimal size of a blocker is at least  m, and there exist geometric
graphs for which the size is  2m-1. If the geometric graph is also
convex (i.e., the vertices are in a convex position in the plane)
then the minimal size is exactly  m.

The main result we present is a full characterization of the minimal
blockers in a convex geometric graph. It appears that all these
blockers admit a very special structure, known as a "caterpillar graph".

Joint work with Micha A. Perles.
The talk will be given in Hebrew.

*************************************************************************
You are all invited ! (Graduate students especially welcome)
If you want to give a talk at the seminar, or know a prospective speaker,
please contact  Ron Adin <radin@math.biu.ac.il>.
Seminar's homepage: <http://www.math.biu.ac.il/~radin/comsem/comsem.html>
*************************************************************************