首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On the maximum number of edges in a hypergraph whose linegraph contains no cycle
Authors:J -C Bermond
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 ∥F∥<(nh±1)/h±1. 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 ∥F∥(nh±1)/h±1; 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”.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号