Institution: | Université Paris-Sud, Laboratoire de Recherche en Informatique, Bát. 490, 91405, Orsay, France C.M.S., 54 Bd Raspail, 75006, Paris, France Université de Lille, France |
Abstract: | Soit H = (X,F) un hypergraphe h-uniforme avec ∥X∥ = n et soit Lh±1(H) le graphe dont les sommets représentent les arêtes de H. deux sommets étant relíes si et seulement si les arétes qu'ils représentent intersectent en h ± 1 sommets. Nous montrons que si Lh±1(H) ne contient pas de cycle, alors . la borne étant exacte pour h = 2 et pour des valeurs de H pour h = 3. Ce probl`eme mène á une conjecture sur les “presque systèmes de Steine.”Let H = (X, F) be a h-uniform hypergraph, with ∥X∥ = n and let Lh±1(H) be the graph whose vertices are the edges of H, two vertices being joined if and only if the edges they represent intersect in h ±1 vertices. We prove that, if Lh±1H contains no cycle, then ; moreover the bound is exact for h = 2 and with some values of n for h = 3. This problem leads to a conjecture on “almost Steiner systems”. |