Search

Let f r (n , v , e) denote the maximum number of edges in an r -uniform hypergraph on n vertices, in which the union of any e distinct edges contains at least v + 1 vertices. The study of f r (n , v , e) was initiated by Brown, Erdős and Sós more than forty years ago. In the literature, the following conjecture is well known. Conjecture: n k − o (1) < f r (n , e r − (e − 1) k + 1 , e) = o (n k) holds for all fixed integers r > k ≥ 2 and e ≥ 3 as n → ∞. For r = 3 , e = 3 , k = 2 , the bound n 2 − o (1) < f 3 (n , 6 , 3) = o (n 2) was proved by the celebrated (6,3)-theorem of Ruzsa and Szemerédi. In this paper, we add more evidence for the validity of the conjecture. On one hand, using the hypergraph removal lemma we show that the upper bound part of the conjecture is true for all fixed integers r ≥ k + 1 ≥ e ≥ 3. On the other hand, using tools from additive number theory we present several constructions showing that the lower bound part of the conjecture is true for r ≥ 3 , k = 2 and e = 4 , 5 , 7 , 8. Prior to our results, all known constructions that match the conjectured lower bound satisfy either r = 3 or e = 3. Our constructions are the first ones in the literature that break this barrier. [ABSTRACT FROM AUTHOR]

In 1968, Golomb and Welch conjectured that there is no perfect Lee codes with radius r ≥ 2 and dimension n ≥ 3. A diameter perfect code is a natural generalization of the perfect code. In 2011, Etzion (2011) [5] proposed the following problem: Are there diameter perfect Lee (DPL, for short) codes with distance greater than four besides the D P L (3 , 6) code? Later, Horak and AlBdaiwi (2012) [12] conjectured that there are no D P L (n , d) codes for dimension n ≥ 3 and distance d > 4 except for (n , d) = (3 , 6). In this paper, we give a counterexample to this conjecture. Moreover, we prove that for n ≥ 3 , there is a linear D P L (n , 6) code if and only if n = 3 , 11. [ABSTRACT FROM AUTHOR]

In this paper, we study problems about the similar configurations in F q d. Let G = (V , E) be a graph, where V = { 1 , 2 , ... , n } and E ⊆ ( V 2 ). For a set E in F q d , we say that E contains a pair of G with dilation ratio r if there exist distinct x 1 , x 2 , ... , x n ∈ E and distinct y 1 , y 2 , ... , y n ∈ E such that ‖ y i − y j ‖ = r ‖ x i − x j ‖ ≠ 0 whenever { i , j } ∈ E , where ‖ x ‖ : = x 1 2 + x 2 2 + ⋯ + x d 2 for x = (x 1 , x 2 , ... , x d) ∈ F q d. We show that if E has size at least C k q d / 2 , then E contains a pair of k -stars with dilation ratio r , and that if E has size at least C ⋅ min ⁡ { q (2 d + 1) / 3 , max ⁡ { q 3 , q d / 2 } } , then E contains a pair of 4-paths with dilation ratio r. Our method is based on enumerative combinatorics and graph theory. [ABSTRACT FROM AUTHOR]

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict avoiding codes. In this paper, we prove some nonexistence results for nonsingular perfect splitter sets. We also give some necessary conditions for the existence of purely singular perfect splitter sets. Finally, we apply these results to purely singular perfect $B[-1,k](m)$ and $B[-2,k](m)$ sets for small $k$. In particular, we solve completely the problems left by Schwartz (European J. Combin., vol. 36, pp.130–142, Feb. 2014). [ABSTRACT FROM AUTHOR]

Let H be an r -uniform hypergraph. The Turán number ex (n , H) is the maximum number of edges in an n -vertex H -free r -uniform hypergraph. The Turán density of H is defined by π (H) = lim n → ∞ ⁡ ex (n , H) ( n r ). In this paper, we consider the Turán density of projective geometries. We give two new constructions of P G m (q) -free hypergraphs which improve some results given by Keevash (2005) [14]. Based on an upper bound of blocking sets of P G m (q) , we give a new general lower bound for the Turán density of P G m (q). By a detailed analysis of the structures of complete arcs in P G 2 (q) , we also get better lower bounds for the Turán density of P G 2 (q) with q = 3 , 4 , 5. [ABSTRACT FROM AUTHOR]

Abstract: Group divisible covering designs (GDCDs) were introduced by Heinrich and Yin as a natural generalization of both covering designs and group divisible designs. They have applications in software testing and universal data compression. The minimum number of blocks in a k‐GDCD of type g u is a covering number denoted by C ( k , g u ). When k = 3, the values of C ( 3 , g u ) have been determined completely for all possible pairs ( g , u ). When k = 4, Francetić et al. constructed many families of optimal GDCDs, but the determination remained far from complete. In this paper, two specific 4‐IGDDs are constructed, thereby completing the existence problem for 4‐IGDDs of type ( g , h ) u. Then, additional families of optimal 4‐GDCDs are constructed. Consequently the cases for ( g , u ) whose status remains undetermined arise when g ≡ 7 mod 12 and u ≡ 3 mod 6, when g ≡ 11 , 14 , 17 , 23 mod 24 and u ≡ 5 mod 6, and in several small families for which one of g and u is fixed. [ABSTRACT FROM AUTHOR]

The research on directed PBDs is motivated by the construction of t-deletion/insertion-correcting codes. Fuji-Hara, Miao, Wang, and Yin have determined the existence of directed PBDs with block sizes from the set [ABSTRACT FROM AUTHOR]

Permutation polynomials over finite fields constitute an active research area and have applications in many areas of science and engineering. In this paper, two conjectures on permutation polynomials proposed recently by Wu and Li [19] are settled. Moreover, a new class of permutation trinomials of the form x + γ Tr q n / q ( x k ) is also presented, which generalizes two examples of [10] . [ABSTRACT FROM AUTHOR]

A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k . Such a class is denoted k -pc and for a given k the number of k -pcs is denoted r k . The number of points of the URD is denoted by v . In the literature, the existence of URDs of block sizes k 1 and k 2 with { k 1 , k 2 } ∈ { { 2 , 3 } , { 2 , 4 } , { 3 , 4 } } has been studied with much efforts. For { k 1 , k 2 } = { 2 , 3 } or { 3 , 4 } , the existence spectra have been determined completely, while for { k 1 , k 2 } = { 2 , 4 } there are still 1338 undetermined pairs of ( v , r 2 ) . In this paper we continue the study on the existence of URDs of block sizes 2 and 4. We improve the known results by reducing the number of open cases from 1338 to 16 . In addition, we prove that there exist 4 -RGDDs of types 2 178 , 2 250 and 2 334 . [ABSTRACT FROM AUTHOR]

A long-standing conjecture of Golomb and Welch, raised in 1970, states that there is no perfect r error correcting Lee code of length n for n\geq 3 and r>1 under the l_{p} metric, where 1\leq p<\infty . We show some nonexistence results of linear perfect lp codes for p=1 and 2\leq p<\infty , r=2^{1/p},3^{1/p} . We also give an algebraic construction of quasi-perfect l_{p}$ codes for p=1, r=2$ , and 2\leq p<\infty , r=2^{1/p} . [ABSTRACT FROM PUBLISHER]

Given n items with at most d of which being positive, instead of testing these items individually, the theory of combinatorial group testing aims to identify all positive items using as few tests as possible. This paper is devoted to a fundamental and thirty-year-old problem in the nonadaptive group testing theory. A binary matrix is called d -disjunct if the Boolean sum of arbitrary d columns does not contain another column not in this collection. Let T(d) denote the minimal t , such that there exists a t\times n\,\,d -disjunct matrix with n>t and was conjectured that T(d)\ge (d+1)^{2} . In this paper, we narrow the gap by proving T(d)/d^{2}\ge (15+\sqrt {33})/24$ , a quantity in [6/7,7/8]. [ABSTRACT FROM PUBLISHER]

One central theme in quantum error-correction is to construct quantum codes that have a relatively large minimum distance. In this paper, we first present a construction of classical linear codes based on certain classes of polynomials. Through these classical linear codes, we are able to obtain some new quantum codes. It turns out that some of the quantum codes exhibited here have better parameters than the ones available in the literature. [ABSTRACT FROM PUBLISHER]

Snake-in-the-box codes under Kendall’s \tau -metric are studied in the rank modulation scheme for flash memories, where codewords are a subset of permutations in S_{n} with minimal Kendall’s \tau -distance two, and two cyclically consecutive codewords are connected via a push-to-the-top operation. Studies so far restrict the push-to-the-top operations only on odd indices, resulting in a snake consisting of permutations with the same parity, and thus, the minimal distance constraint is easily satisfied. Asymptotically optimal snake codes have been constructed this way in S2n+1 . As for S2n+2 , this framework keeps the last element fixed, and thus, a snake in S2n+2 is equivalent to a snake in S2n+1 , which is rather trivial. If one wants to do better, then it is inevitable to have some push-to-the-top operations on even indices, resulting in a combination of odd and even permutations in the snake, which increases the difficulty to guarantee the minimal Kendall’s $\tau $ -distance constraint. Thus, Horovitz and Etzion pose the open problem to prove or disprove that the size of the largest snake in ({1}/{4})|S_{2n+2}| . [ABSTRACT FROM PUBLISHER]

Some physical effects that limit the reliability and performance of multilevel flash memories induce errors that have low magnitudes and are dominantly asymmetric. This motivated the application of the asymmetric limited magnitude error model in flash memory. In this paper, we present a new construction of quasi-perfect codes for such errors, and we also study the perfect codes with symmetric errors. Moreover, we show some nonexistence results on perfect codes for correcting single error of limited magnitude. [ABSTRACT FROM PUBLISHER]

The construction of group divisible designs (GDDs) is a basic problem in design theory. While there have been some methods concerning the constructions of uniform GDDs, the construction of nonuniform GDDs remains a challenging problem. In this paper, we present a new approach to the construction of nonuniform GDDs with group type [ABSTRACT FROM AUTHOR]

A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k . Such a class is denoted k -pc and for a given k the number of k -pcs is denoted r k . Let v denote the number of points of the URD. For the case of block sizes 3 and 4 (both existing), the necessary conditions imply that v ≡ 0 ( mod 12 ) . It has been shown that almost all URDs with permissible r 3 and r 4 exist for v ≡ 0 ( mod 24 ) , v ≡ 0 ( mod 60 ) , v ≡ 36 ( mod 144 ) or v ≡ 36 ( mod 108 ) . In this paper, we prove that the necessary conditions for the existence of a URD with block sizes 3 and 4 are also sufficient, except when v = 12 , r 3 = 1 and r 4 = 3 . [ABSTRACT FROM AUTHOR]

A triple system is a collection of b blocks, each of size three, on a set of v points. It is j-balanced when every two j -sets of points appear in numbers of blocks that are as nearly equal as possible, and well balanced when it is j-balanced for each j ∈ {1, 2, 3}.Well-balanced systems arise in the minimization of variance in file availability in distributed file systems. It is shown that when a triple system that is 2-balanced and 3-balanced exists, so does one that is well balanced. Using known and new results on variants of group divisible designs, constructions for well-balanced triple systems are developed. Using these, the spectrum of pairs (v, b) for which such a well-balanced triple system exists is determined completely. [ABSTRACT FROM AUTHOR]

For a Gray code in the scheme of rank modulation for flash memories, the codewords are permutations, and two consecutive codewords are obtained using a push-to-the-top operation. We consider the snake-in-the-box code under Kendall’s \tau -metric, which is a Gray code capable of detecting one Kendall’s \tau -error. We answer two open problems posed by Horovitz and Etzion. First, we prove the validity of a construction given by them, resulting in a snake of size M2n+1=({(2n+1)!}/{2})-2n+1 . Second, we come up with a different construction aiming at a larger snake of size M2n+1=({(2n+1)!}/{2})-2n+3 . The construction is applied successfully to S7 . [ABSTRACT FROM PUBLISHER]

Quantum maximum-distance-separable (MDS) codes form an important family of quantum codes. In this paper, using Hermitian construction and classical constacyclic codes, we construct six classes of quantum MDS codes. Two of these six classes of quantum MDS codes have larger minimum distance than the ones available in the literature. Most of these quantum MDS codes are new in the sense that their parameters are not covered by the codes available in the literature. [ABSTRACT FROM AUTHOR]

Grooming uniform all-to-all traffic in optical (SONET) rings with grooming ratio C requires the determination of a decomposition of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The determination of optimal C-groomings has been considered for [ABSTRACT FROM AUTHOR]

Quadratic residue codes are a well-known class of codes. In this paper, we consider the constructions of self-dual codes by higher power residues, especially fourth power residues. New infinite families of self-dual codes over GF(2), GF(3), GF(4), GF(8), and GF(9) are introduced. Some of them have better minimum weight than previously known codes. We also give general results related to the automorphism group of some of these codes. [ABSTRACT FROM PUBLISHER]

Let R k (H ; K m) be the smallest number N such that every coloring of the edges of K N with k + 1 colors has either a monochromatic H in color i for some 1 ⩽ i ⩽ k , or a monochromatic K m in color k + 1. In this short note, we study the lower bound for R k (H ; K m) when H is C 5 or C 7 , respectively. We show that R k (C 5 ; K m) = Ω (m 3 k 8 + 1 / (log ⁡ m) 3 k 8 + 1) , and R k (C 7 ; K m) = Ω (m 2 k 9 + 1 / (log ⁡ m) 2 k 9 + 1) , for fixed positive integer k and m → ∞. The proof is based on random block constructions of Mubayi and Verstraëte, who obtained comparable bounds when k = 1 , and random blowups argument. Our results slightly improve the previously known lower bound R k (C 2 ℓ + 1 ; K m) = Ω (m k 2 ℓ − 1 + 1 / (log ⁡ m) k + 2 k 2 ℓ − 1 ) obtained by Alon and Rödl. [ABSTRACT FROM AUTHOR]

Given a graph H and an integer k ⩾ 2 , let f k (n , H) be the smallest number of colors C such that there exists a proper edge-coloring of the complete graph K n with C colors containing no k vertex-disjoint color isomorphic copies of H. In this paper, we prove that f 2 (n , H t) = Ω (n 1 + 1 2 t − 3 ) where H t is the 1-subdivision of the complete graph K t. This answers a question of Conlon and Tyomkyn (2021) [4]. [ABSTRACT FROM AUTHOR]

A G-design of order n is a decomposition of the complete graph on n vertices into edge-disjoint subgraphs isomorphic to G. Grooming uniform all-to-all traffic in optical ring networks with grooming ratio C requires the determination of graph decompositions of the complete graph on n vertices into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The existence spectrum problem of G-designs for five-vertex graphs is a long standing problem posed by Bermond, Huang, Rosa and Sotteau in 1980, which is closely related to traffic groomings in optical networks. Although considerable progress has been made over the past 30 years, the existence problems for such G-designs and their related traffic groomings in optical networks are far from complete. In this paper, we first give a complete solution to this spectrum problem for five-vertex graphs by eliminating all the undetermined possible exceptions. Then, we determine almost completely the minimum drop cost of 8-groomings for all orders n by reducing the 37 possible exceptions to 8. Finally, we show the minimum possible drop cost of 9-groomings for all orders n is realizable with 14 exceptions and 12 possible exceptions. [ABSTRACT FROM AUTHOR]

In this paper, we continue to investigate the existence of 5 -GDDs, 4-frames and 4-RGDDs, which have been studied by numerous researchers in the past two decades due to their vital applications in the constructions for other types of designs. Much progress has been made for the existence problems of these designs, while the problems are still open. Our new results mainly lie in the cases with relatively large group size. We also construct some smaller designs, including 4 -RGDDs of types 2 184 , 9 44 , 14 10 , 18 18 , 22 10 and 36 11 . [ABSTRACT FROM AUTHOR]

Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia contents. Separable codes were introduced to detect colluders taking part in the averaging attack, which is the most feasible approach to perform a collusion attack. In this paper, we provide some improved bounds for the size of separable codes. Using a combinatorial technique named grouping coordinates, we have greatly reduced the upper bound. On the other hand, we also provide some lower bounds for the size of separable codes by both probabilistic and deterministic construction methods. In particular, \( \overline {2}\) -separable codes with asymptotically optimal rate are obtained by the deletion method. [ABSTRACT FROM AUTHOR]

Abstract: Non-uniform group divisible designs (GDDs) and non-uniform Kirkman frames are useful in the constructions for other types of designs. In this paper, we consider the existence problems for -GDDs of type with and Kirkman frames of type . First, we determine completely the spectrum for uniform -GDDs of type . Then, we consider the entire existence problem for non-uniform -GDDs of type with . We show that, for each given , up to a small number of undetermined cases of , the necessary conditions on for the existence of a -GDD of type are also sufficient, except possibly when for and when for . Finally, a similar result for Kirkman frames of type is obtained. We show that, for each given , up to a small number of undetermined cases of , the necessary conditions on for the existence of a Kirkman frame of type are also sufficient, except possibly when for and when for . [Copyright &y& Elsevier]

We study some sum-product problems over matrix rings. Firstly, for A , B , C ⊆ M n (F q) , we have | A + B C | ≳ q n 2 , whenever | A | | B | | C | ≳ q 3 n 2 − n + 1 2 . Secondly, if a set A in M n (F q) satisfies | A | ≥ C (n) q n 2 − 1 for some sufficiently large C (n) , then we have max ⁡ { | A + A | , | A A | } ≳ min ⁡ { | A | 2 q n 2 − n + 1 4 , q n 2 / 3 | A | 2 / 3 }. These improve the results due to The and Vinh (2020), and generalize the results due to Mohammadi, Pham, and Wang (2021). We also give a new proof for a recent result due to The and Vinh (2020). Our method is based on spectral graph theory and linear algebra. [ABSTRACT FROM AUTHOR]

In this note, we present a corrected proof of Lemma 5.8 which was wrong due to the incorrectness of Construction 2.3, from our paper. [ABSTRACT FROM AUTHOR]

This paper focuses on constructions of MDS self-dual codes from (extended) generalized Reed-Solomon (GRS) codes. Let $q = r^{2}$ be an odd prime power. We show that, there exists a $q$ -ary self-dual (extended) GRS code for each even length in the range $[{2r,3r-3}]$ , and for each singly even length in the range $[3r-1,4r]$. This extends the only known consecutive range $[2,2r]$ to $[{2,3r-3}]$ for this case. Furthermore, our general constructions provide many MDS self-dual codes with new parameters which, to the best of our knowledge, were not reported before. [ABSTRACT FROM AUTHOR]

As an important coding scheme in modern distributed storage systems, locally repairable codes (LRCs) have attracted a lot of attentions from perspectives of both practical applications and theoretical research. As a major topic in the research of LRCs, bounds and constructions of the corresponding optimal codes are of particular concerns. In this work, codes with $(r,\delta)$ -locality which have optimal minimal distance w.r.t. the bound given by Prakash et al. are considered. Through parity-check matrix approach, constructions of both optimal $(r,\delta)$ -LRCs with all symbol locality ($(r,\delta)_{a}$ -LRCs) and optimal $(r,\delta)$ -LRCs with information locality ($(r,\delta)_{i}$ -LRCs) are provided. As a generalization of a work of Xing and Yuan, these constructions are built on a connection between sparse hypergraphs and optimal $(r,\delta)$ -LRCs. With the help of constructions of large sparse hypergraphs, the lengths of codes obtained from our construction can be super-linear in the alphabet size. This improves upon previous constructions when the minimal distance of the code is at least $3\delta +1$. As two applications, optimal H-LRCs with super-linear lengths and GSD codes with unbounded lengths are also constructed. [ABSTRACT FROM AUTHOR]

As a crucial technique for integrated circuits (IC) test response compaction, X-compact employs a special kind of codes called X-codes for reliable compressions of the test response in the presence of unknown logic values (Xs). From a combinatorial view point, Fujiwara and Colbourn introduced an equivalent definition of X-codes and studied X-codes of small weights that have good detectability and X-tolerance. An $({\it\text { m, n, d, x}})~\text {X}$ -code is an $\text {m}\times \text {n}$ binary matrix with column vectors as its codewords. The parameters ${\it\text { d, x}}$ correspond to the test quality of the code. In this paper, bounds and constructions for constant weighted X-codes are investigated. First, we obtain a general result on the maximum number of codewords n for an $({\it\text { m, n, d, x}})~\text {X}$ -code of weight w, and we further improve this lower bound for the case with $\text {x}=2$ and $\text {w}=3$ through the probabilistic method. Then, using tools from additive combinatorics and finite fields, we present some explicit constructions for constant weighted X-codes with $\text {d}=3,7$ and $\text {x}=2$ , which are optimal for the case when $\text {d}=3, \text {w}=4$ and nearly optimal for the case when $\text {d}=3,\text {w}=3$. We also consider a special class of X-codes introduced by Fujiwara and Colbourn and improve the best known lower bound on the maximum number of codewords for this kind of X-codes. [ABSTRACT FROM AUTHOR]

To solve the access-balancing problem in distributed storage systems, we introduce a new combinatorial model, called MinVar model for fractional repetition (FR) codes. Since FR codes are based on graphs or set systems, our MinVar model is characterized by the property that the variance among the sums of block-labels incident to a fixed vertex is minimized. This characterization is different from Dau and Milenkovic’s MaxMinSum model, while the minimum sum of labels is maximized. We show that our MinVar model is meaningful by distinguishing labelings with different variances but with the same MaxMin value for some FR codes. By reformulating the MinVar model to an equivalent vertex-labeling problem of graphs, we find several families of optimal FR codes with balanced access frequency, and provide fundamental results for both problems. It is interesting that MinVar model is closely related to the concept of magic-labeling in graph theory. [ABSTRACT FROM AUTHOR]

The famous Erdős-Falconer distance problems aim to quantify the extent to which large sets must determine many distinct distances. The problems in both the Euclidean setting and the discrete setting have received much attention. An interesting generalization of Erdős-Falconer problems is to find locating point configurations with prescribed metric structure within large subsets. In this paper, we consider such problem in the discrete setting. We say a distance graph H in F q n under Hamming metric means a graph H = (V , E) with vertices as the points in V ⊆ F q n and edges being assigned by Hamming distance between the pairs of vertices. We call a subset A ⊆ F q n contains an isometric copy of distance graph H , if there exists an embedding ϕ : V (H) → A such that for every edge u v ∈ E (H) , the Hamming distance between ϕ (u) and ϕ (v) is equal to the Hamming distance between u and v. When q is a fixed prime power and n goes to infinity, we show that for any given bipartite graph H with ex (n , H) = O (n) , any subset A ⊆ F q n contains a positive proportion of all possible isometric copies of distance graphs H whose edges are assigned by the same Hamming distance, if | A | > q (1 − c) n for some c = c (q , H) > 0. Our methods also work for general bipartite graphs. Moreover, we will give the quantitative bounds for the above constant c = c (q , H). Unlike using analytical method as before, our ideas are more combinatorial, which mainly include two techniques. The first one is the celebrated dependent random choice, which is like glue, sticking several small structures together. The second one is a new extension of the modular version of the classical Delsarte's inequality. In particular, this extension itself is of independent interest, which also helps us build a surprising connection between our main results and the extremal number of the bipartite graphs. [ABSTRACT FROM AUTHOR]

The centralized coded caching scheme is a technique proposed by Maddah-Ali and Niesen as a method to reduce the network burden in peak times in a wireless network system. Yan et al. reformulate the problem as designing a corresponding placement delivery array and propose two new schemes from this perspective. These schemes significantly reduce the rate compared with the uncoded caching schemes. However, to implement these schemes, each file should be cut into $F$ pieces, where $F$ grows exponentially with the number of users $K$. Such a constraint is obviously infeasible in the practical setting, especially when $K$ is large. Thus, it is desirable to design caching schemes with constant rate $R$ (independent of $K$ ) as well as smaller $F$. In this paper, we view the centralized coded caching problem in a hypergraph perspective and show that designing a feasible placement delivery array is equivalent to constructing a linear and (6,3)-free 3-uniform 3-partite hypergraph. Several new results and constructions arise from our novel point of view. First, by using the famous (6,3)-theorem in extremal graph theory, we show that constant rate placement delivery arrays with $F$ growing linearly with $K$ do not exist. Second, we present two infinite classes of placement delivery arrays to show that constant rate caching schemes with $F$ growing sub-exponentially with $K$ do exist. [ABSTRACT FROM AUTHOR]

Let K = { k 1 , k 2 , … , k r } and L = { l 1 , l 2 , … , l s } be disjoint subsets of { 0 , 1 , … , p − 1 } , where p is a prime and A = { A 1 , A 2 , … , A m } is a family of subsets of [ n ] = { 1 , 2 , … , n } such that | A i | ( mod p ) ∈ K for all A i ∈ A and | A i ∩ A j | ( mod p ) ∈ L for i ≠ j . In 1991, Alon, Babai and Suzuki conjectured that if n ≥ s + max 1 ≤ i ≤ r k i , then | A | ≤ n s + n s − 1 + ⋯ + n s − r + 1 . In 2000, Qian and Ray-Chaudhuri proved the conjecture under the condition n ≥ 2 s − r . In 2015, Hwang and Kim verified this conjecture. In this paper, we will prove that if n ≥ 2 s − 2 r + 1 or n ≥ s + max 1 ≤ i ≤ r k i , then | A | ≤ n − 1 s + n − 1 s − 1 + ⋯ + n − 1 s − 2 r + 1 . This result strengthens both the upper bound of Alon–Babai–Suzuki’s conjecture and Qian and Ray-Chaudhuri’s result, when n ≥ 2 s − 2 . [ABSTRACT FROM AUTHOR]

Recently, Yaakobi et al. introduced codes for b -symbol read channels, where the read operation is performed as a consecutive sequence of b > 2 symbols. In this paper, we establish a Singleton-type bound for b -symbol codes. Codes meeting the Singleton-type bound are called maximum distance separable (MDS) codes, and they are optimal in the sense they attain the maximal minimum b -distance. We introduce a construction method using projective geometry, and then construct several infinite families of linear MDS b -symbol codes over finite fields. The lengths of these codes have a large range. And in some sense, we completely determine the existence of linear MDS b -symbol codes over finite fields for certain parameters. [ABSTRACT FROM AUTHOR]

Splitter sets are closely related to lattice tilings, and have applications in flash memories and conflict-avoiding codes. The study of k -radius sequences was motivated by some problems occurring in large data transfer. It is observed that the existence of splitter sets yields k -radius sequences of short length. In this paper, we obtain several new results contributing to splitter sets and k -radius sequences. We give some new constructions of perfect splitter sets, as well as some nonexistence results on them. As a byproduct, we obtain some new results on optimal conflict-avoiding codes. Furthermore, we provide several explicit constructions of short k -radius sequences for certain values of n , by establishing the existence of k -additive sequences. In particular, we show that for any fixed k , where fk (n) denotes the shortest length of an n -ary $k$ -radius sequence. This result partially affirms a conjecture posed by Bondy, Lonc, and Rzążewski. [ABSTRACT FROM AUTHOR]

Frameproof codes are used to fingerprint digital data. They can prevent copyrighted materials from unauthorized use. In this paper, we study upper and lower bounds for $w$ -frameproof codes of length N$ over an alphabet of size q$ . The upper bound is based on a combinatorial approach and the lower bound is based on a probabilistic construction. Both bounds can improve one of the previous results when q$ is small compared with w$ , say cq\leq w$ for some constant c\leq q$ . Furthermore, we pay special attention to binary frameproof codes. We show a binary w . [ABSTRACT FROM PUBLISHER]

Various kinds of secure codes and their related hash families are broadly studied combinatorial structures for protecting copyrighted materials. The codewords in such a structure can be regarded as a subset of Q^N , the set of all $q$ -ary vectors of given length $N$ , satisfying some constraints. We use a hypergraph model to characterize the combinatorial structure. By applying a result of Duke et al. on the lower bound of the independence number of hypergraphs, we provide a new approach to evaluate the lower bounds for several kinds of secure codes and related hash families. In particular, the general method is illustrated via the examples of existence results on some perfect hash families, frameproof codes, and separable codes. [ABSTRACT FROM PUBLISHER]

In this paper, a new class of circulant matrices built from the deterministic filter and the deterministic subsampling is introduced for convolution-based compressed sensing. The pseudo-random sequences are applied in the construction of compressed sensing matrices. By using Katz's and Bombieri's character sum estimation, we are able to design good deterministic compressed sensing matrices for sparse recovery. In the worst case, the sparsity bound in our construction is similar to that of binary compressed sensing matrices constructed by DeVore and partial Fourier matrices constructed by Xu and Xu. Moreover, in the average case, we show that our construction can reconstruct almost all k -sparse vectors with m ≥ O ( k log ⁡ N ) . [ABSTRACT FROM AUTHOR]

The generalized Hamming weights (GHWs) of linear codes are fundamental parameters, the knowledge of which is of great interest in many applications. However, to determine the GHWs of linear codes is difficult in general. In this paper, we study the GHWs for a family of reducible cyclic codes and obtain the complete weight hierarchy in several cases. This is achieved by extending the idea of Yang et al. into higher dimension and by employing some interesting combinatorial arguments. It shall be noted that these cyclic codes may have arbitrary number of nonzeros. [ABSTRACT FROM PUBLISHER]

Constacyclic codes which generalize the classical cyclic codes have played important roles in recent constructions of many new quantum maximum distance separable (MDS) codes. However, the mathematical mechanism may not have been fully understood. In this paper, we use pseudo-cyclic codes, which is a further generalization of constacyclic codes, to construct the quantum MDS codes. We can not only provide a unified explanation of many previous constructions, but also produce some new quantum MDS codes. [ABSTRACT FROM AUTHOR]

Recently, there has been intensive research on the weight distributions of cyclic codes. In this paper, we compute the weight distributions of three classes of cyclic codes with Niho exponents. More specifically, we obtain two classes of binary three-weight and four-weight cyclic codes and a class of nonbinary four-weight cyclic codes. The weight distributions follow from the determination of value distributions of certain exponential sums. Several examples are presented to show that some of our codes are optimal and some have the best known parameters. [ABSTRACT FROM AUTHOR]

Recently, Bennett, English and Talanda-Fisher introduced the vertex-induced weighted Turán problem. In this paper, we consider their open Turán problem under sum-edge-weight function and characterize the extremal structure of K ℓ -free graphs. Based on these results, we propose a generalized version of the Erdős–Stone theorem for weighted graphs under two types of vertex-induced weight functions. [ABSTRACT FROM AUTHOR]

For a graph H and a k -chromatic graph F , if the Turán graph T k − 1 (n) has the maximum number of copies of H among all n -vertex F -free graphs (for n large enough), then H is called F -Turán-good, or k -Turán-good for short if F is K k. In this paper, we construct some new classes of k -Turán-good graphs and prove that P 4 and P 5 are k -Turán-good for k ≥ 4. [ABSTRACT FROM AUTHOR]

Erdős posed the problem of finding conditions on a graph G which imply that the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We consider a more general problem by defining δ r to be the least number so that any graph G on n vertices with minimum degree δ r n has the property that the largest number of edges in an (r − 1) -partite subgraph equals to the largest number of edges in a K r -free subgraph. We show that 3 r − 4 3 r − 1 < δ r ≤ 4 (3 r − 7) (r − 1) + 1 4 (r − 2) (3 r − 4) when r ≥ 4. We also show δ 4 ≤ 0.9415. [ABSTRACT FROM AUTHOR]

Recently, several hypergraph Turán problems were solved by the powerful random algebraic method. However, the random algebraic method usually requires some parameters to be very large, hence we are concerned about how these Turán numbers depend on such large parameters of the forbidden hypergraphs. In this paper, we determine the dependence on such specified large constant for several hypergraph Turán problems. More specifically, for complete r -partite r -uniform hypergraphs, we show that if s r is sufficiently larger than s 1 , s 2 , ... , s r − 1 , then ex r (n , K s 1 , s 2 , ... , s r (r) ) = Θ (s r 1 s 1 s 2 ⋯ s r − 1 n r − 1 s 1 s 2 ⋯ s r − 1 ). For complete bipartite r -uniform hypergraphs, we prove that if s is sufficiently larger than t , we have ex r (n , K s , t (r) ) = Θ (s 1 t n r − 1 t ). In particular, our results imply that the famous Kővári–Sós–Turán's upper bound ex (n , K s , t) = O (t 1 s n 2 − 1 s ) has the correct dependence on large t. The main approach is to construct random multi-hypergraph via a variant of random algebraic method. [ABSTRACT FROM AUTHOR]

Splitter sets have been widely studied due to their applications in flash memories, and their close relations with lattice tilings and conflict avoiding codes. In this paper, we give necessary and sufficient conditions for the existence of nonsingular perfect splitter sets, ${B}[-{k}_{1},{k}_{2}]({p})$ sets, where $0\le {k}_{1}\leq {k}_{2}=4$. Meanwhile, constructions of nonsingular perfect splitter sets are given. When perfect splitter sets do not exist, we present four new constructions of quasi-perfect splitter sets. Finally, we give a connection between nonsingular splitter sets and Cayley graphs, and as a byproduct, a general lower bound on the maximum size of nonsingular splitter sets is given. [ABSTRACT FROM AUTHOR]

Given a database, the private information retrieval (PIR) protocol allows a user to make queries to several servers and retrieve a certain item of the database via the feedbacks without revealing the identity of the specific item to any single server. Classic $k$ -server PIR protocols work on replicated databases, i.e., each of the $k$ servers stores a whole copy of the database. Recently, new PIR models were proposed with coding techniques arising from the distributed storage system. In these new models, each server only stores a fraction $1/s$ of the whole database, where $s>1$ is the given rational number. The PIR array codes are recently proposed by Fazeli, Vardy, and Yaakobi to characterize the new models. The central problem in designing a PIR array code with $m$ servers and the $k$ -PIR property (which indicates that these $m$ servers may emulate a classic $k$ -server PIR protocol) is to maximize $k/m$ , known as the virtual server rate. Our main contribution to this problem is twofold. First, for the case $1 < s\le 2$ , although the PIR array codes with optimal rate have been constructed recently by Blackburn and Etzion, the number of servers in their construction is rather large. We determine the minimum number of servers admitting the existence of a PIR array code with an optimal rate for a certain range of parameters. Second, for the case $s>2$ , a new upper bound on the rate of a PIR array code is presented. Besides, we also have some discussions on an asymptotically optimal construction by Blackburn and Etzion. [ABSTRACT FROM AUTHOR]