Optimal Codes in the Enomoto-Katona Space
- 9 October 2014
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 24 (2) , 382-406
Abstract
Coding in a new metric space, called the Enomoto-Katona space, has recently been considered in connection with the study of implication structures of functional dependencies and their generalizations in relational databases. The central problem is the determination ofC(n,k,d), the size of an optimal code of lengthn, weightk, and distancedin the Enomoto-Katona space. The value ofC(n,k,d) was known only for some congruence classes ofnwhen (k,d) ∈ {(2,3),(3,5)}. In this paper, we obtain new infinite families of optimal codes in the Enomoto-Katona space and verify a conjecture of Brightwell and Katona in certain instances. In particular,C(n,k, 2k− 1) is determined for all sufficiently largensatisfying eithern≡ 1 modkandn(n− 1) ≡ 0 mod 2k2, orn≡ 0 modk. We also give complete solutions fork= 2 and determineC(n,3,5) for certain congruence classes ofnwith finite exceptions.Keywords
This publication has 10 references indexed in Scilit:
- Optimal codes in the Enomoto-Katona space2013
- Coding Theory Motivated by Relational Databases2011
- New type of coding problem motivated by database theoryDiscrete Applied Mathematics, 2004
- Decompositions of Edge-Colored Complete GraphsJournal of Combinatorial Theory, Series A, 2000
- Design type problems motivated by database theoryJournal of Statistical Planning and Inference, 1998
- The characterization of branching dependenciesDiscrete Applied Mathematics, 1992
- Independent components of relationsACM Transactions on Database Systems, 1977
- Synthesizing third normal form relations from functional dependenciesACM Transactions on Database Systems, 1976
- An existence theory for pairwise balanced designs I. Composition theorems and morphismsJournal of Combinatorial Theory, Series A, 1972
- Truncated finite planes1971