Upper Bounds on Matching Families in <formula formulatype="inline"> <tex Notation="TeX">\BBZ_{pq}^{n}</tex></formula>

DOI10.1109/TIT.2013.2257918MaRDI QIDQ5346437zbMATH OpenOpenAlexFDO

Authors Yeow Meng Chee, San Ling, Huaxiong Wang, Liang Feng Zhang

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Other types of codes (94B60)

Abstract: extit{Matching families} are one of the major ingredients in the construction of {em locally decodable codes} (LDCs) and the best known constructions of LDCs with a constant number of queries are based on matching families. The determination of the largest size of any matching family in $mathbb{Z}_m^n$, where $mathbb{Z}_m$ is the ring of integers modulo $m$, is an interesting problem. In this paper, we show an upper bound of $O((pq{)}^{0.625n+0.125})$ for the size of any matching family in $mathbb{Z}_{pq}^n$, where $p$ and $q$ are two distinct primes. Our bound is valid when $n$ is a constant, $pightarrowinfty$ and $p/qightarrow1$. Our result improves an upper bound of Dvir {it et al.}

Recommendations

• On families with bounded matching number
• On the maximum size of (p,Q)-free families
• Asymptotics of the upper matching conjecture
• Bounds for matchings in nonabelian groups
• An upper bound on the size of separated matchings
• Bounds on pairs of families with restricted intersections
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
• Upper bounds on the paired-domination number
• An Upper Bound on Zarankiewicz' Problem
• On the upper bounds of the numbers of perfect matchings in graphs with given parameters

Cited in

(2)

• On piercing numbers of families satisfying the \((p,q)_{r}\) property
• On families with bounded matching number

This page was built for publication: Upper Bounds on Matching Families in <formula formulatype="inline"> <tex Notation="TeX">$\BBZ_{pq}^{n}$</tex></formula>

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