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


Lines in hypergraphs
Authors:Laurent Beaudou  Adrian Bondy  Xiaomin Chen  Ehsan Chiniforooshan  Maria Chudnovsky  Va?ek Chvátal  Nicolas Fraiman  Yori Zwols
Institution:1. Université Blaise Pascal, Clermont-Ferrand, France
2. Université Paris 6, Paris, France
3. Shanghai Jianshi LTD, Shanghai, China
4. Google, Waterloo, Canada
5. Columbia University, New York, USA
6. Concordia University, Montreal, Canada
7. McGill University, Montreal, Canada
Abstract:One of the De Bruijn-Erd?s theorems deals with finite hypergraphs where every two vertices belong to precisely one hyperedge. It asserts that, except in the perverse case where a single hyperedge equals the whole vertex set, the number of hyperedges is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of simply described families, near-pencils and finite projective planes. Chen and Chvátal proposed to define the line uv in a 3-uniform hypergraph as the set of vertices that consists of u, v, and all w such that {u;v;w} is a hyperedge. With this definition, the De Bruijn-Erd?s theorem is easily seen to be equivalent to the following statement: If no four vertices in a 3-uniform hypergraph carry two or three hyperedges, then, except in the perverse case where one of the lines equals the whole vertex set, the number of lines is at least the number of vertices and the two numbers are equal if and only if the hypergraph belongs to one of two simply described families. Our main result generalizes this statement by allowing any four vertices to carry three hyperedges (but keeping two forbidden): the conclusion remains the same except that a third simply described family, complements of Steiner triple systems, appears in the extremal case.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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