Uniform hypergraphs containing no grids
From MaRDI portal
Publication:390731
DOI10.1016/J.AIM.2013.03.009zbMATH Open1278.05161arXiv1103.1691OpenAlexW2086208008MaRDI QIDQ390731FDOQ390731
Authors: Miklós Ruszinkó, Zoltán Füredi 
Publication date: 8 January 2014
Published in: Advances in Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1103.1691
Recommendations
Density (toughness, etc.) (05C42) Hypergraphs (05C65) Extremal set theory (05D05) Arithmetic progressions (11B25)
Cites Work
- On extremal problems of graphs and generalized graphs
- Families of finite sets in which no set is covered by the union of two others
- Title not available (Why is that?)
- Nonrandom binary superimposed codes
- Packing graphs: The packing problem solved
- On sets of integers containing k elements in arithmetic progression
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Graphs that do not Contain a Thomsen Graph
- Title not available (Why is that?)
- Exact solution of some Turán-type problems
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Solving a linear equation in a set of integers I
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- Compactness results in extremal graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the upper bound of the size of the \(r\)-cover-free families
- Title not available (Why is that?)
- On an extremal hypergraph problem of Brown, Erdős and Sós
- On the existence of triangulated spheres in 3-graphs, and related problems
- Construction Techniques for Anti-Pasch Steiner Triple Systems
- The resolution of the anti‐mitre Steiner triple system conjecture
- Infinite classes of anti‐mitre and 5‐sparse Steiner triple systems
- An extension of the Ruzsa-Szemerédi theorem
- On 6-sparse Steiner triple systems
- Families of finite sets in which no set is covered by the union of \(r\) others
- Integer sets containing no arithmetic progressions
- Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes
- Integer Sets Containing No Arithmetic Progressions
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Method for Detecting All Defective Members in a Population by Group Testing
- On optimal superimposed codes
- A simple construction of \(d\)-disjunct matrices with certain constant weights
- Tracing Many Users With Almost No Rate Penalty
- Optimal superimposed codes and designs for Renyi's search model
- Title not available (Why is that?)
- Further 6-sparse Steiner triple systems
- Sidon sets in groups and induced subgraphs of Cayley graphs
- Union-free families of sets and equations over fields
- Anti-mitre Steiner triple systems
- On \(r\)-cover-free families
- An existence theory for pairwise balanced designs. I: Composition theorems and morphisms
- On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
- 5-sparse Steiner triple systems of order \(n\) exist for almost all admissible \(n\)
- Superimposed codes in R/sup n/
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A direct product construction for 5-sparse triple systems
- Title not available (Why is that?)
- Title not available (Why is that?)
- An improved upper bound of the rate of Euclidean superimposed codes
- Improved asymptotic bounds for error-correcting codes
- Some new results on superimposed codes
- Behrend-type constructions for sets of linear equations
- On upper bounds for unrestricted binary-error-correcting codes
- Primes in short intervals
- A new extremal property of Steiner triple-systems
- Tracing a single user
- The existence of 5-sparse Steiner triple systems of order \(n \equiv 3 \mod 6\), \(n \notin \{9,15 \}\)
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?
- A Ramsey variant of the Brown-Erdős-Sós conjecture
- Sparse hypergraphs: new bounds and constructions
- New Turán Exponents for Two Extremal Hypergraph Problems
- Degenerate Turán densities of sparse hypergraphs
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)
