Turán numbers and batch codes

DOI10.1016/J.DAM.2015.01.006zbMATH Open1311.05137arXiv1309.6506OpenAlexW2067650130WikidataQ59072513 ScholiaQ59072513MaRDI QIDQ2345596FDOQ2345596

Csilla Bujtás, Zsolt Tuza

Publication date: 22 May 2015

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The History of Degenerate (Bipartite) Extremal Graph Problems
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• On an extremal hypergraph problem of Brown, Erdős and Sós
• An extremal problem for two families of sets
• On the existence of triangulated spheres in 3-graphs, and related problems
• An extension of the Ruzsa-Szemerédi theorem
• On a Turán-type hypergraph problem of Brown, Erdős and T. Sós
• Combinatorial batch codes: a lower bound and optimal constructions
• Combinatorial batch codes and transversal matroids
• Extremal graphs with bounded densities of small subgraphs
• Extensions of Turán's theorem on graphs
• Optimal batch codes: many items or low retrieval requirement
• On a class of degenerate extremal graph problems
• Combinatorial batch codes
• Combinatorial batch codes: extremal problems under Hall-type conditions
• Batch codes and their applications
• Relaxations of Hall’s Condition: Optimal batch codes with multiple queries
• On an extremal hypergraph problem related to combinatorial batch codes

Cited In (7)

• Batch codes and their applications
• Multicolor Turán numbers
• Optimal combinatorial batch codes based on block designs
• Multiset combinatorial batch codes
• Derandomized Construction of Combinatorial Batch Codes
• Sparse Hypergraphs with Applications to Coding Theory
• 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)