2-cancellative hypergraphs and codes
From MaRDI portal
Abstract: A family of sets F (and the corresponding family of 0-1 vectors) is called t-cancellative if for all distict t+2 members A_1,... A_t and B,C from F the union of A_1,..., A_t and B differs from the union of A_1, ..., A_t and C. Let c(n,t) be the size of the largest t-cancellative family on n elements, and let c_k(n,t) denote the largest k-uniform family. We significantly improve the previous upper bounds, e.g., we show c(n,2)< 2^0.322n (for n> n_0). Using an algebraic construction we show that the order of magnitude of c_{2k}(n,2) is n^k for each k (when n goes to infinity).
Recommendations
Cites work
- scientific article; zbMATH DE number 607286 (Why is no real title available?)
- A better bound for locally thin set families
- An exact Turán result for the generalized triangle
- An extension of the Ruzsa-Szemerédi theorem
- Asymptotic solution of a Turán-type problem
- Asymptotic solution of the Turán problem for some hypergraphs
- Combinatorial properties of systems of sets
- Delta-systems and qualitative (in)dependence
- Extremal problems whose solutions are the blowups of the small Witt- designs
- 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
- Locally thin set families
- New rate pairs in the zero-error capacity region of the binary multiplying channel without feedback
- Nonrandom binary superimposed codes
- On Cancellative Set Families
- On r-cover-free families
- On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
- On a hypergraph Turán problem of Frankl
- On an extremal hypergraph problem of Brown, Erdős and Sós
- On coloring graphs to maximize the proportion of multicolored k-edges
- On the existence of triangulated spheres in 3-graphs, and related problems
- On the extremal combinatorics of the Hamming space
- On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs
- 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
- Stability theorems for cancellative hypergraphs
- String quartets in binary
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- Three-graphs without two triples whose symmetric difference is contained in a third
- Tracing a single user
- Union-free hypergraphs and probability theory
Cited in
(7)- Cancellative hypergraphs and Steiner triple systems
- Spectral Turán-type problems on cancellative hypergraphs
- On Cancellative Set Families
- Cancellative pairs of families of sets
- Probabilistic methods for deriving new lower bounds on the rates of locally thin families and weak superimposed codes
- Degenerate Turán densities of sparse hypergraphs
- New Turán Exponents for Two Extremal Hypergraph Problems
This page was built for publication: 2-cancellative hypergraphs and codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2883859)
