Füredi, Zoltán and Ruszinkó, Miklós (2013) Uniform hypergraphs containing no grids. ADVANCES IN MATHEMATICS, 240. pp. 302-324. ISSN 0001-8708
|
Text
Uniform hypergraphs containing no grids.pdf Download (271kB) | Preview |
Abstract
A hypergraph is called an r×r grid if it is isomorphic to a pattern of r horizontal and r vertical lines, i.e.,a family of sets {A1, ..., Ar, B1, ..., Br} such that Ai∩Aj=Bi∩Bj=φ for 1≤i<j≤r and {pipe}Ai∩Bj{pipe}=1 for 1≤i, j≤r. Three sets C1, C2, C3 form a triangle if they pairwise intersect in three distinct singletons, {pipe}C1∩C2{pipe}={pipe}C2∩C3{pipe}={pipe}C3∩C1{pipe}=1, C1∩C2≠C1∩C3. A hypergraph is linear, if {pipe}E∩F{pipe}≤1 holds for every pair of edges E≠F.In this paper we construct large linear r-hypergraphs which contain no grids. Moreover, a similar construction gives large linear r-hypergraphs which contain neither grids nor triangles. For r≥. 4 our constructions are almost optimal. These investigations are motivated by coding theory: we get new bounds for optimal superimposed codes and designs. © 2013 Elsevier Ltd.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Union free hypergraphs; Turán hypergraph problem; Superimposed codes; Density problems |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 11 Dec 2013 10:23 |
Last Modified: | 11 Dec 2013 10:27 |
URI: | http://real.mtak.hu/id/eprint/7997 |
Actions (login required)
![]() |
Edit Item |