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

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

(when)  Tuesday, 30 Marcheshvan 5767 (Nov. 21)
         refreshments at 11:45 am, talk at 12 noon

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

(who)   Adam Marcus (Georgia Tech)

         will talk about

(what)  "The Furedi-Hajnal conjecture and hypergraph extensions"

Abstract:
---------
Almost 15 years ago, Furedi and Hajnal began a systematic investigation of 
extremal problems on {0,1}-matrices.  In particular, they asked, if one 
was to fix their favorite {0,1}-matrix K, how many 1-entries could they 
then cram into an n x n {0,1}-matrix A while avoiding the matrix K (by 
"avoiding" we mean that there is no order preserving mapping f from K into 
A s.t. f(K(i,j)) = 1 whenever K(i,j) = 1).  In particular, how does 
ex(K,n), the maximum number of 1-entries that are crammable, grow as a 
function of n?

Apart from a number of interesting results (including growth rates that 
include logs, a phenomenon unseen in the analogous unordered graph 
problem), a number of interesting conjectures arose.  The most well-known 
of these, which has since been named the Furedi-Hajnal Conjecture, 
predicted that ex(K,n) = O(n) whenever the chosen K is a permutation 
matrix (all rows and columns each have a single 1-entry).  In this talk, I 
will show that the conjectured growth is correct, and then show how it 
implies the solution to the (much more well-known) Stanley-Wilf 
Conjecture, which asks how many permutations of length n avoid a fixed 
smaller permutation.  If time permits, I will show an extension of the 
Furedi-Hajnal result that considers avoidance in {0,1}-grids of higher 
dimension (which correspond to ordered d-uniform, d-partite hypergraphs in 
the way that the original matrix formulation corresponds to ordered 
bipartite graphs).

As a side note, the proofs are surprisingly (or perhaps "refreshingly", 
depending on who you ask) simple - they use nothing more than basic 
counting, pigeonhole, and induction.  The talk will be accessible to 
anyone (including undergraduates and even advanced high-schoolers) with 
even a basic knowledge of combinatorics.  For this reason, I would like to 
extend a special invitation to anyone who is interested in the field of 
combinatorics (or mathematics in general) but who wouldn't normally attend 
a research seminar for fear that the material would be too advanced.  On 
the other hand, I hope to see advanced students and researchers there as 
well, as this will serve as a gentle reminder that hard problems don't 
necessarily require hard solutions.


Forthcoming Events
==================
* 7 Kislev (Nov. 28)
   Eli Berger (University of Haifa):
   "On the duality between independence and domination"
* 14 Kislev (Dec. 5)
   Ori Gurel-Gurevich (Weizmann Institute):
   TBA
*************************************************************************
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>
*************************************************************************