TY - JOUR

T1 - Lines in hypergraphs

AU - Beaudou, Laurent

AU - Bondy, Adrian

AU - Chen, Xiaomin

AU - Chiniforooshan, Ehsan

AU - Chudnovsky, Maria

AU - Chvátal, Vašek

AU - Fraiman, Nicolas

AU - Zwols, Yori

N1 - Funding Information: ∗Partially supported by NSF grants DMS-1001091 and IIS-1117631 †Canada Research Chair in Discrete Mathematics

PY - 2013/12

Y1 - 2013/12

N2 - One of the De Bruijn-Erdo{double acute}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-Erdo{double acute}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.

AB - One of the De Bruijn-Erdo{double acute}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-Erdo{double acute}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.

UR - http://www.scopus.com/inward/record.url?scp=84892548537&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84892548537&partnerID=8YFLogxK

U2 - 10.1007/s00493-013-2910-5

DO - 10.1007/s00493-013-2910-5

M3 - Article

SN - 0209-9683

VL - 33

SP - 633

EP - 654

JO - Combinatorica

JF - Combinatorica

IS - 6

ER -