ARTICLE
TITLE

A Linear Hypergraph Extension of Turán's Theorem

SUMMARY

An rr-uniform hypergraph is linear if every two edges intersect in at most one vertex. Given a family of rr-uniform hypergraphs F\mathcal{F}, the linear Turán number exlinr(n,F)_r^{lin}(n,\mathcal{F}) is the maximum number of edges of a linear rr-uniform hypergraph on nn vertices that does not contain any member of F\mathcal{F} as a subgraph.Let KlK_l be a complete graph with ll vertices and r=2r\geq 2. The rr-expansion of KlK_l is the rr-graph K+lK_l^+ obtained from KlK_l by enlarging each edge of KlK_l with r-2r-2 new vertices disjoint from V(Kl)V(K_l) such that distinct edges of KlK_l are enlarged by distinct vertices. When l=r=3l\geq r \geq 3 and nn is sufficiently large, we prove the following extension of Turán's Theorem exlinr(n,K+l+1)=|TDr(n,l)|,ex_{r}^{lin}\left(n, K_{l+1}^{+}\right)\leq |TD_r(n,l)|, with equality achieved only by the Turán design TDr(n,l)TD_r(n,l), where the Turán design TDr(n,l)TD_r(n,l) is an almost balanced ll-partite rr-graph such that each pair of vertices from distinct parts are contained in one edge exactly. Moreover, some results on linear Turán number of general configurations are also presented.

 Articles related

Tiru S Arthanari    

The traveling salesperson problem (TSP) is a very well-known NP-hard combinatorial optimization problem. Many different integer programming formulations are known for the TSP. Some of them are “compact”, in the sense of having a polynomially-bounded numb... see more


Anda Olteanu,Oana Olteanu    

For path ideals of the square of the line graph we compute the Krull dimension, we characterize the linear resolution property in combinatorial terms. We bound the Castelnuovo-Mumford regularity and the projective dimension in terms of the corresponding... see more