Turán numbers and batch codes

DOI10.1016/J.DAM.2015.01.006MaRDI QIDQ2345596zbMATH OpenOpenAlexWikidataFDO

Authors Zsolt Tuza, Csilla Bujtás

Publication date 22 May 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.6506

zbMATH Keywords

hypergraphcombinatorial batch codeTurán number

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Hypergraphs (05C65)

Abstract: Combinatorial batch codes provide a tool for distributed data storage, with the feature of keeping privacy during information retrieval. Recently, Balachandran and Bhattacharya observed that the problem of constructing such uniform codes in an economic way can be formulated as a Tur'an-type question on hypergraphs. Here we establish general lower and upper bounds for this extremal problem, and also for its generalization where the forbidden family consists of those $r$-uniform hypergraphs $H$ which satisfy the condition $kge|E(H)|>|V(H)|+q$ (for $k>q+r$ and $q>-r$ fixed). We also prove that, in the given range of parameters, the considered Tur'an function is asymptotically equal to the one restricted to $|E(H)|=k$, studied by Brown, ErdH{o}s and T. S'os. Both families contain some $r$-partite members --- often called the `degenerate case', characterized by the equality $li{m}_{noinfty}ex(n,cF)/n^r=0$ --- and therefore their exact order of growth is not known.

Recommendations

• On an extremal hypergraph problem related to combinatorial batch codes
• Combinatorial batch codes
• Relaxations of Hall's condition: optimal batch codes with multiple queries
• Combinatorial batch codes: extremal problems under Hall-type conditions
• On erasure combinatorial batch codes

Cites work

• scientific article; zbMATH DE number 5942358 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 736306 (Why is no real title available?)
• scientific article; zbMATH DE number 878901 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• An extension of the Ruzsa-Szemerédi theorem
• An extremal problem for two families of sets
• Batch codes and their applications
• Combinatorial batch codes
• Combinatorial batch codes and transversal matroids
• Combinatorial batch codes: a lower bound and optimal constructions
• Combinatorial batch codes: extremal problems under Hall-type conditions
• Extensions of Turán's theorem on graphs
• Extremal graphs with bounded densities of small subgraphs
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• On a class of degenerate extremal graph problems
• On an extremal hypergraph problem of Brown, Erdős and Sós
• On an extremal hypergraph problem related to combinatorial batch codes
• On the existence of triangulated spheres in 3-graphs, and related problems
• Optimal batch codes: many items or low retrieval requirement
• Optimal combinatorial batch codes derived from dual systems
• Relaxations of Hall's condition: optimal batch codes with multiple queries
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The history of degenerate (bipartite) extremal graph problems

Cited in

(8)

• Sparse hypergraphs with applications to coding theory
• Batch codes and their applications
• Multicolor Turán numbers
• Derandomized construction of combinatorial batch codes
• Optimal combinatorial batch codes based on block designs
• Multiset combinatorial batch codes
• Erasure list-decodable codes and Turán hypercube problems
• Erasure combinatorial batch codes based on nonadaptive group testing

This page was built for publication: Turán numbers and batch codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345596)