Abstract: A hypergraph is called an r by r grid if it is isomorphic to a pattern of r horizontal and r vertical lines. Three sets form a triangle if they pairwise intersect in three distinct singletons. A hypergraph is linear if every pair of edges meet in at most one vertex. 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 at least 4 our constructions are almost optimal. These investigations are also motivated by coding theory: we get new bounds for optimal superimposed codes and designs.
Recommendations
Cites work
- scientific article; zbMATH DE number 3167429 (Why is no real title available?)
- scientific article; zbMATH DE number 4043100 (Why is no real title available?)
- scientific article; zbMATH DE number 4064918 (Why is no real title available?)
- scientific article; zbMATH DE number 19213 (Why is no real title available?)
- scientific article; zbMATH DE number 26314 (Why is no real title available?)
- scientific article; zbMATH DE number 3478938 (Why is no real title available?)
- scientific article; zbMATH DE number 3561377 (Why is no real title available?)
- scientific article; zbMATH DE number 3572172 (Why is no real title available?)
- scientific article; zbMATH DE number 1314686 (Why is no real title available?)
- scientific article; zbMATH DE number 1496588 (Why is no real title available?)
- scientific article; zbMATH DE number 205343 (Why is no real title available?)
- scientific article; zbMATH DE number 3801449 (Why is no real title available?)
- scientific article; zbMATH DE number 3430675 (Why is no real title available?)
- scientific article; zbMATH DE number 3232670 (Why is no real title available?)
- scientific article; zbMATH DE number 3258067 (Why is no real title available?)
- scientific article; zbMATH DE number 3407723 (Why is no real title available?)
- 5-sparse Steiner triple systems of order \(n\) exist for almost all admissible \(n\)
- A Method for Detecting All Defective Members in a Population by Group Testing
- A direct product construction for 5-sparse triple systems
- A new extremal property of Steiner triple-systems
- A simple construction of \(d\)-disjunct matrices with certain constant weights
- An existence theory for pairwise balanced designs. I: Composition theorems and morphisms
- An extension of the Ruzsa-Szemerédi theorem
- An improved upper bound of the rate of Euclidean superimposed codes
- Anti-mitre Steiner triple systems
- Behrend-type constructions for sets of linear equations
- Compactness results in extremal graph theory
- Construction Techniques for Anti-Pasch Steiner Triple Systems
- Exact solution of some Turán-type problems
- Families of finite sets in which no set is covered by the union of \(r\) others
- Families of finite sets in which no set is covered by the union of two others
- Further 6-sparse Steiner triple systems
- Improved asymptotic bounds for error-correcting codes
- Infinite classes of anti‐mitre and 5‐sparse Steiner triple systems
- Integer Sets Containing No Arithmetic Progressions
- Integer sets containing no arithmetic progressions
- Nonrandom binary superimposed codes
- On 6-sparse Steiner triple systems
- On Graphs that do not Contain a Thomsen Graph
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- On r-cover-free families
- On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
- On an extremal hypergraph problem of Brown, Erdős and Sós
- On extremal problems of graphs and generalized graphs
- On optimal superimposed codes
- On sets of integers containing k elements in arithmetic progression
- On the existence of triangulated spheres in 3-graphs, and related problems
- On the upper bound of the size of the \(r\)-cover-free families
- On upper bounds for unrestricted binary-error-correcting codes
- Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes
- Optimal superimposed codes and designs for Renyi's search model
- Packing graphs: The packing problem solved
- Primes in short intervals
- Sidon sets in groups and induced subgraphs of Cayley graphs
- Solving a linear equation in a set of integers I
- Some new results on superimposed codes
- Superimposed codes in R/sup n/
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- The existence of 5-sparse Steiner triple systems of order \(n \equiv 3 \mod 6\), \(n \notin \{9,15 \}\)
- The resolution of the anti‐mitre Steiner triple system conjecture
- Tracing Many Users With Almost No Rate Penalty
- Tracing a single user
- Union-free families of sets and equations over fields
Cited in
(19)- Constructing dense grid-free linear 3-graphs
- Sparse hypergraphs with applications to coding theory
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- On positive hypergraphs
- On vertex independence number of uniform hypergraphs
- On a conjecture of Erdős on locally sparse Steiner triple systems
- Degenerate Turán Densities of Sparse Hypergraphs II: A Solution to the Brown-Erdős-Sós Problem for Every Uniformity
- Superimposed codes and hypergraphs containing no grids.
- On the structure of pointsets with many collinear triples
- Separating hash families: a Johnson-type bound and new constructions
- Local-vs-global combinatorics
- The Turán number of the grid
- Turán and Ramsey numbers in linear triple systems
- Identifying defective sets using queries of small size
- The linear Turán number of small triple systems or why is the wicket interesting?
- Sparse hypergraphs: new bounds and constructions
- A Ramsey variant of the Brown-Erdős-Sós conjecture
- Degenerate Turán densities of sparse hypergraphs
- New Turán Exponents for Two Extremal Hypergraph Problems
This page was built for publication: Uniform hypergraphs containing no grids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q390731)
