Search

We investigate linear network coding in the context of robust function computation, where a sink node is tasked with computing a target function of messages generated at multiple source nodes. In a previous work, a new distance measure was introduced to evaluate the error tolerance of a linear network code for function computation, along with a Singleton-like bound for this distance. In this paper, we first present a minimum distance decoder for these linear network codes. We then focus on the sum function and the identity function, showing that in any directed acyclic network there are two classes of linear network codes for these target functions, respectively, that attain the Singleton-like bound. Additionally, we explore the application of these codes in distributed computing and design a distributed gradient coding scheme in a heterogeneous setting, optimizing the trade-off between straggler tolerance, computation cost, and communication cost. This scheme can also defend against Byzantine attacks.

In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactly $b$, where $b>1$. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most $7\log n+O\left(\log n/\log\log n\right)$ bits. In contrast, our work introduces a novel approach for constructing $q$-ary codes that attain a redundancy of at most $5\log n+O(\log\log n)$ bits for all $b>1$ and $q\ge2$. Additionally, for the case where $b=1$, we present a new construction of $q$-ary two-deletion correcting codes with a redundancy of $5\log n+O(\log\log n)$ bits, for all $q>2$., Comment: Redundancy is improved to $5\log n+O(\log\log n)$

Motivated by applications in DNA-based data storage, constrained codes have attracted a considerable amount of attention from both academia and industry. We study the maximum cardinality of constrained codes for which the constraints can be characterized by a set of forbidden substrings, where by a substring we mean some consecutive coordinates in a string. For finite-type constrained codes (for which the set of forbidden substrings is finite), one can compute their capacity (code rate) by the ``spectral method'', i.e., by applying the Perron-Frobenious theorem to the de Brujin graph defined by the code. However, there was no systematic method to compute the exact cardinality of these codes. We show that there is a surprisingly powerful method arising from enumerative combinatorics, which is based on the Goulden-Jackson cluster theorem (previously not known to the coding community), that can be used to compute not only the capacity, but also the exact formula for the cardinality of these codes, for each fixed code length. Moreover, this can be done by solving a system of linear equations of size equal to the number of constraints. We also show that the spectral method and the cluster method are inherently related by establishing a direct connection between the spectral radius of the de Brujin graph used in the first method and the convergence radius of the generating function used in the second method. Lastly, to demonstrate the flexibility of the new method, we use it to give an explicit upper bound on the maximum cardinality of variable-length non-overlapping codes, which are a class of constrained codes defined by an infinite number of forbidden substrings., Comment: 21 pages

Set systems with strongly restricted intersections, called $\alpha$-intersecting families for a vector $\alpha$, were introduced recently as a generalization of several well-studied intersecting families including the classical oddtown and eventown. Given a binary vector $\alpha=(a_1, \ldots, a_k)$, a collection $\mathcal F$ of subsets over an $n$ element set is an $\alpha$-intersecting family modulo $2$ if for each $i=1,2,\ldots,k$, all $i$-wise intersections of distinct members in $\mathcal F$ have sizes with the same parity as $a_i$. Let $f_\alpha(n)$ denote the maximum size of such a family. In this paper, we study the asymptotic behavior of $f_\alpha(n)$ when $n$ goes to infinity. We show that if $t$ is the maximum integer such that $a_t=1$ and $2t\leq k$, then $f_{\alpha(n)} \sim {(t! n)}^{\frac 1 t}$. More importantly, we show that for any constant $c$, as the length $k$ goes larger, $f_\alpha(n)$ is upper bounded by $O (n^c)$ for almost all $\alpha$. Equivalently, no matter what $k$ is, there are only finitely many $\alpha$ satisfying $f_\alpha(n)=\Omega (n^c)$. This answers an open problem raised by Johnston and O'Neill in 2023. All of our results can be generalized to modulo $p$ setting for any prime $p$ smoothly., Comment: 12 pages, 0 figure

An edit refers to a single insertion, deletion, or substitution. This paper aims to construct binary codes that can correct two edits. To do this, a necessary and sufficient condition for a code to be two-edit correctable is provided, showing that a code is a two-edit correcting code if and only if it can correct two deletions, up to two substitutions, and one deletion and up to one substitution, separately. This criterion allows for the construction of two-edit correcting codes leveraging these three types of error correcting codes. In the field of constructing codes for correcting two deletions, we present a construction with $4\log n+O(\log\log n)$ redundant bits that can be viewed as a subcode proposed by Guruswami and H{\aa}stad, and provide an alternative proof. Moreover, our two-deletion correcting codes can also correct up to two substitutions after making a slight modification. In the field of constructing codes for correcting one deletion and up to one substitution, we present a construction with $4 \log n+O(\log\log n)$ redundant bits, which outperforms the best previously known results $6 \log n+O(1)$. Leveraging these codes, we obtain a construction of two-edit correcting codes with $6 \log n+O(\log\log n)$ redundant bits. This outperforms the best previously known result, which requires at least $8\log n$ redundant bits. Moreover, we also consider the list-decoding problem under the two-edit channel and construct a two-edit list-decodable code with a list size of two employing $4 \log n+O(\log\log n)$ redundant bits., Comment: Submitted to IEEE Trans. Inf. Theory on Sep. 2023

Nanopore sequencing is a promising technology for DNA sequencing. In this paper, we investigate a specific model of the nanopore sequencer, which takes a $q$-ary sequence of length $n$ as input and outputs a vector of length $n+\ell-1$ referred to as an $\ell$-read vector where the $i$-th entry is a multi-set composed of the $\ell$ elements located between the $(i-\ell+1)$-th and $i$-th positions of the input sequence. Considering the presence of substitution errors in the output vector, we study $\ell$-read codes under the Hamming metric. An $\ell$-read $(n,d)_q$-code is a set of $q$-ary sequences of length $n$ in which the Hamming distance between $\ell$-read vectors of any two distinct sequences is at least $d$. We first improve the result of Banerjee \emph{et al.}, who studied $\ell$-read $(n,d)_q$-codes with the constraint $\ell\geq 3$ and $d=3$. Then, we investigate the bounds and constructions of $2$-read codes with a minimum distance of $3$, $4$, and $5$, respectively. Our results indicate that when $d \in \{3,4\}$, the optimal redundancy of $2$-read $(n,d)_q$-codes is $o(\log_q n)$, while for $d=5$ it is $\log_q n+o(\log_q n)$. Additionally, we establish an equivalence between $2$-read $(n,3)_q$-codes and classical $q$-ary single-insertion reconstruction codes using two noisy reads. We improve the lower bound on the redundancy of classical $q$-ary single-insertion reconstruction codes as well as the upper bound on the redundancy of classical $q$-ary single-deletion reconstruction codes when using two noisy reads. Finally, we study $\ell$-read codes under the reconstruction model.

Recently, codes for correcting a burst of errors have attracted significant attention. One of the most important reasons is that bursts of errors occur in certain emerging techniques, such as DNA storage. In this paper, we investigate a type of error, called a $(t,s)$-burst, which deletes $t$ consecutive symbols and inserts $s$ arbitrary symbols at the same coordinate. Note that a $(t,s)$-burst error can be seen as a generalization of a burst of insertions ($t=0$), a burst of deletions ($s=0$), and a burst of substitutions ($t=s$). Our main contribution is to give explicit constructions of $q$-ary $(t,s)$-burst correcting codes with $\log n + O(1)$ bits of redundancy for any given non-negative integers $t$, $s$, and $q \geq 2$. These codes have optimal redundancy up to an additive constant. Furthermore, we apply our $(t,s)$-burst correcting codes to combat other various types of errors and improve the corresponding results. In particular, one of our byproducts is a permutation code capable of correcting a burst of $t$ stable deletions with $\log n + O(1)$ bits of redundancy, which is optimal up to an additive constant., Comment: Submitted to IEEE Trans. Inf. Theory on Jul. 2023

The problem of sparse representation has significant applications in signal processing. The spark of a dictionary plays a crucial role in the study of sparse representation. Donoho and Elad initially explored the spark, and they provided a general lower bound. When the dictionary is a union of several orthonormal bases, Gribonval and Nielsen presented an improved lower bound for spark. In this paper, we introduce a new construction of dictionary, achieving the spark bound given by Gribonval and Nielsen. Our result extends Shen et al.' s findings [IEEE Trans. Inform. Theory, vol. 68, pp. 4230--4243, 2022].

This paper studies the problem of encoding messages into sequences which can be uniquely recovered from some noisy observations about their substrings. The observed reads comprise consecutive substrings with some given minimum overlap. This coded reconstruction problem has applications to DNA storage. We consider both single-strand reconstruction codes and multi-strand reconstruction codes, where the message is encoded into a single strand or a set of multiple strands, respectively. Various parameter regimes are studied. New codes are constructed, some of whose rates asymptotically attain the upper bounds., Comment: 35 pages

Separating hash families are useful combinatorial structures which generalize several well-studied objects in cryptography and coding theory. Let $p_t(N, q)$ denote the maximum size of universe for a $t$-perfect hash family of length $N$ over an alphabet of size $q$. In this paper, we show that $q^{2-o(1)}

To prevent service time bottlenecks in distributed storage systems, the access balancing problem has been studied by designing almost supermagic edge labelings of certain graphs to balance the access requests to different servers. In this paper, we introduce the concept of robustness of edge labelings under limited-magnitude swaps, which is important for studying the dynamical access balancing problem with respect to changes in data popularity. We provide upper and lower bounds on the robustness ratio for complete graphs with $n$ vertices, and construct $O(n)$-almost supermagic labelings that are asymptotically optimal in terms of the robustness ratio., Comment: 27 pages, no figure

Motivated by an extremal problem on graph-codes that links coding theory and graph theory, Alon recently proposed a question aiming to find the smallest number $t$ such that there is an edge coloring of $K_{n}$ by $t$ colors with no copy of given graph $H$ in which every color appears an even number of times. When $H=K_{4}$, the question of whether $n^{o(1)}$ colors are enough, was initially emphasized by Alon. Through modifications to the coloring functions originally designed by Mubayi, and Conlon, Fox, Lee and Sudakov, the question of $K_{4}$ has already been addressed. Expanding on this line of inquiry, we further study this new variant of the generalized Ramsey problem and provide a conclusively affirmative answer to Alon's question concerning $K_{5}$., Comment: Note added: Heath and Zerbib also proved the result on $K_{5}$ independently. arXiv:2307.01314

Signed difference sets have interesting applications in communications and coding theory. A $(v,k,\lambda)$-difference set in a finite group $G$ of order $v$ is a subset $D$ of $G$ with $k$ distinct elements such that the expressions $xy^{-1}$ for all distinct two elements $x,y\in D$, represent each non-identity element in $G$ exactly $\lambda$ times. A $(v,k,\lambda)$-signed difference set is a generalization of a $(v,k,\lambda)$-difference set $D$, which satisfies all properties of $D$, but has a sign for each element in $D$. We will show some new existence results for signed difference sets by using partial difference sets, product methods, and cyclotomic classes.

Reconstruction codes are generalizations of error-correcting codes that can correct errors by a given number of noisy reads. The study of such codes was initiated by Levenshtein in 2001 and developed recently due to applications in modern storage devices such as racetrack memories and DNA storage. The central problem on this topic is to design codes with redundancy as small as possible for a given number $N$ of noisy reads. In this paper, the minimum redundancy of such codes for binary channels with exactly two insertions is determined asymptotically for all values of $N\ge 5$. Previously, such codes were studied only for channels with single edit errors or two-deletion errors.

We study the supersaturation problems of oddtown and eventown. Given a family $\mathcal A$ of subsets of an $n$ element set, let $op(\mathcal A)$ denote the number of distinct pairs $A,B\in \mathcal A$ for which $|A \cap B|$ is odd. We show that if $\mathcal A$ consists of $n+s$ odd-sized subsets, then $op(\mathcal A)\geq s+2$, which is tight when $s\le n-4$. This disproves a conjecture by O'Neill on the supersaturation problem of oddtown. For the supersaturation problem of eventown, we show that for large enough $n$, if $\mathcal A$ consists of $2^{\lfloor \frac n 2\rfloor}+s$ even-sized subsets, then $op(\mathcal A)\ge s\cdot2^{\lfloor \frac n 2\rfloor-1} $ for any positive integer $s\le \frac{2^{\lfloor\frac n 8\rfloor}} n$. This partially proves a conjecture by O'Neill on the supersaturation problem of eventown. Previously, the correctness of this conjecture was only verified for $s=1$ and $2$. We further provide a twice weaker lower bound in this conjecture for eventown, that is $op(\mathcal{A})\ge s\cdot 2^{\lfloor n/2\rfloor-2}$ for general $n$ and $s$ by using discrete Fourier analysis. Finally, some asymptotic results for the lower bounds of $op(\mathcal A)$ are given when $s$ is large for both problems., Comment: 16 pages, no figure

In this paper, we study problems about the similar configurations in $\mathbb{F}_q^d$. Let $G=(V, E)$ be a graph, where $V=\{1, 2, \ldots, n\}$ and $E\subseteq{V\choose2}$. For a set $\mathcal{E}$ in $\mathbb{F}_q^d$, we say that $\mathcal{E}$ contains a pair of $G$ with dilation ratio $r$ if there exist distinct $\boldsymbol{x}_1, \boldsymbol{x}_2, \ldots, \boldsymbol{x}_n\in\mathcal{E}$ and distinct $\boldsymbol{y}_1, \boldsymbol{y}_2, \ldots, \boldsymbol{y}_n\in\mathcal{E}$ such that $\|\boldsymbol{y}_i-\boldsymbol{y}_{j}\|=r\|\boldsymbol{x}_i-\boldsymbol{x}_j\|\neq0$ whenever $\{i, j\}\in E$, where $\|\boldsymbol{x}\|:=x_1^2+x_2^2+\cdots+x_d^2$ for $\boldsymbol{x}=(x_1, x_2, \ldots, x_d)\in\mathbb{F}_q^d$. We show that if $\mathcal{E}$ has size at least $C_kq^{d/2}$, then $\mathcal{E}$ contains a pair of $k$-stars with dilation ratio $r$, and that if $\mathcal{E}$ has size at least $C\cdot\min\left\{q^{(2d+1)/3}, \max\left\{q^3, q^{d/2}\right\}\right\}$, then $\mathcal{E}$ contains a pair of $4$-paths with dilation ratio $r$. Our method is based on enumerative combinatorics and graph theory., Comment: 19 pages; any comments are welcome

Limited magnitude error model has applications in flash memory. In this model, a perfect code is equivalent to a tiling of $\mathbb{Z}^n$ by limited magnitude error balls. In this paper, we give a complete classification of lattice tilings of $\mathbb{Z}^n$ by limited magnitude error balls $\mathcal{B}(n,2,1,1)$., Comment: 15 pages

Hopping cyclic codes (HCCs) are (non-linear) cyclic codes with the additional property that the $n$ cyclic shifts of every given codeword are all distinct, where $n$ is the code length. Constant weight binary hopping cyclic codes are also known as optical orthogonal codes (OOCs). HCCs and OOCs have various practical applications and have been studied extensively over the years. The main concern of this paper is to present improved Gilbert-Varshamov type lower bounds for these codes, when the minimum distance is bounded below by a linear factor of the code length. For HCCs, we improve the previously best known lower bound of Niu, Xing, and Yuan by a linear factor of the code length. For OOCs, we improve the previously best known lower bound of Chung, Salehi, and Wei, and Yang and Fuja by a quadratic factor of the code length. As by-products, we also provide improved lower bounds for frequency hopping sequences sets and error-correcting weakly mutually uncorrelated codes. Our proofs are based on tools from probability theory and graph theory, in particular the McDiarmid's inequality on the concentration of Lipschitz functions and the independence number of locally sparse graphs., Comment: 14 pages, submitted

In 1968, Golomb and Welch conjectured that there is no perfect Lee codes with radius $r\ge2$ and dimension $n\ge3$. A diameter perfect code is a natural generalization of the perfect code. In 2011, Etzion (IEEE Trans. Inform. Theory, 57(11): 7473--7481, 2011) proposed the following problem: Are there diameter perfect Lee (DPL, for short) codes with diameter greater than four besides the $DPL(3,6)$ code? Later, Horak and AlBdaiwi (IEEE Trans. Inform. Theory, 58(8): 5490--5499, 2012) conjectured that there are no $DPL(n,d)$ codes for dimension $n\ge3$ and diameter $d>4$ except for $(n,d)=(3,6)$. In this paper, we give a counterexample to this conjecture. Moreover, we prove that for $n\ge3$, there is a linear $DPL(n,6)$ code if and only if $n=3,11$., Comment: 26 pages

Several network communication problems are highly related such as coded caching and distributed computation. The centralized coded caching focuses on reducing the network burden in peak times in a wireless network system and the coded distributed computation studies the tradeoff between computation and communication in distributed system. In this paper, motivated by the study of the only rainbow $3$-term arithmetic progressions set, we propose a unified framework for constructing coded caching schemes. This framework builds bridges between coded caching schemes and lots of combinatorial objects due to the freedom of the choices of families and operations. We prove that any scheme based on a placement delivery array (PDA) can be represented by a rainbow scheme under this framework and lots of other known schemes can also be included in this framework. Moreover, we also present a new coded caching scheme with linear subpacketization and near constant rate using the only rainbow $3$-term arithmetic progressions set. Next, we modify the framework to be applicable to the distributed computing problem. We present a new transmission scheme in the shuffle phase and show that in certain cases it could have a lower communication load than the schemes based on PDAs or resolvable designs with the same number of files., Comment: 13 pages

Permutation codes and multi-permutation codes have been widely considered due to their various applications, especially in flash memory. In this paper, we consider permutation codes and multi-permutation codes against a burst of stable deletions. In particular, we propose a construction of permutation codes correcting a burst stable deletion of length $s$, with redundancy $\log n+ 2\log \log n+O(1)$. Compared to the previous known results, our improvement relies on a different strategy to retrieve the missing symbol on the first row of the array representation of a permutation. We also generalize our constructions for multi-permutations and the variable length burst model. Furthermore, we propose a linear-time encoder with optimal redundancy for single stable deletion correcting permutation codes., Comment: Accepted for publication in IEEE Trans. Inf. Theory

Grassmannian $\mathcal{G}_q(n,k)$ is the set of all $k$-dimensional subspaces of the vector space $\mathbb{F}_q^n.$ Recently, Etzion and Zhang introduced a new notion called covering Grassmannian code which can be used in network coding solutions for generalized combination networks. An $\alpha$-$(n,k,\delta)_q^c$ covering Grassmannian code $\mathcal{C}$ is a subset of $\mathcal{G}_q(n,k)$ such that every set of $\alpha$ codewords of $\mathcal{C}$ spans a subspace of dimension at least $\delta +k$ in $\mathbb{F}_q^n.$ In this paper, we derive new upper and lower bounds on the size of covering Grassmannian codes. These bounds improve and extend the parameter range of known bounds., Comment: 17 pages

In this paper, we give some new lower bounds for the kissing number of $\ell_p$-spheres. These results improve the previous work due to Xu (2007). Our method is based on coding theory., Comment: 15 pages, 4 figures; any comments are welcome

Let $\mathcal{H}$ be an $r$-uniform hypergraph and $F$ be a graph. We say $\mathcal{H}$ contains $F$ as a trace if there exists some set $S\subseteq V(\mathcal{H})$ such that $\mathcal{H}|_{S}:=\{E\cap S: E\in E(\mathcal{H})\}$ contains a subgraph isomorphic to $F.$ Let $ex_r(n,Tr(F))$ denote the maximum number of edges of an $n$-vertex $r$-uniform hypergraph $\mathcal{H}$ which does not contain $F$ as a trace. In this paper, we improve the lower bounds of $ex_r(n,Tr(F))$ when $F$ is a star, and give some optimal cases. We also improve the upper bound for the case when $\mathcal{H}$ is $3$-uniform and $F$ is $K_{2,t}$ when $t$ is small., Comment: 6 pages

Recent years, several new types of codes were introduced to provide fault-tolerance and guarantee system reliability in distributed storage systems, among which locally repairable codes (LRCs for short) have played an important role. A linear code is said to have locality $r$ if each of its code symbols can be repaired by accessing at most $r$ other code symbols. For an LRC with length $n$, dimension $k$ and locality $r$, its minimum distance $d$ was proved to satisfy the Singleton-like bound $d\leq n-k-\lceil k/r\rceil+2$. Since then, many works have been done for constructing LRCs meeting the Singleton-like bound over small fields. In this paper, we study quaternary LRCs meeting Singleton-like bound through a parity-check matrix approach. Using tools from finite geometry, we provide some new necessary conditions for LRCs being optimal. From this, we prove that there are $27$ different classes of parameters for optimal quaternary LRCs. Moreover, for each class, explicit constructions of corresponding optimal quaternary LRCs are presented., Comment: 23 pages, the Chinese version of this paper will appear in SCIENTIA SINICA Mathematica (DOI: 10.1360/SSM-2022-0041)

Define the superball with radius $r$ and center ${\boldsymbol 0}$ in $\mathbb{R}^n$ to be the set $$ \left\{{\boldsymbol x}\in\mathbb{R}^n:\sum_{j=1}^{m}\left(x_{k_j+1}^2+x_{k_j+2}^2+\cdots+x_{k_{j+1}}^2\right)^{p/2}\leq r^p\right\},0=k_1

In this paper, we investigate function computation problems under different secure conditions over a network with multiple source nodes and a single sink node which desires a function of all source messages without error. A wiretapper has access to some edges of the network. Based on different practical requirements, we consider two secure conditions named as secure and user secure respectively. The main parameter concerned here is the computing rate, which is the average times of the target function that can be computed securely or user securely without error for one use of the network. In the secure case, a new upper bound which is tighter than the previous one is provided for arithmetic sum functions and arbitrary networks. Moreover, we show that the improved upper bound is strictly tight for tree-like networks. In the user secure case, we give a sufficient and necessary condition for the existence of user secure network codes and obtain an upper bound for the computation capacity., Comment: 10 pages, 3 figures

Motivated by applications in DNA-based storage, we study explicit encoding and decoding schemes of binary strings satisfying locally balanced constraints, where the $(\ell,\delta)$-locally balanced constraint requires that the weight of any consecutive substring of length $\ell$ is between $\frac{\ell}{2}-\delta$ and $\frac{\ell}{2}+\delta$. In this paper we present coding schemes for the strongly locally balanced constraints and the locally balanced constraints, respectively. Moreover, we introduce an additional result on the linear recurrence formula of the number of binary strings which are $(6,1)$-locally balanced, as a further attempt to both capacity characterization and new coding strategies for locally balanced constraints., Comment: Submitted to ISIT2022

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\leqslant i\leqslant 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 \begin{equation*} R_{k}(C_5;K_m)=\Omega(m^{\frac{3k}{8}+1}/(\log{m})^{\frac{3k}{8}+1}), \end{equation*} and \begin{equation*} R_{k}(C_7;K_m)=\Omega(m^{\frac{2k}{9}+1}/(\log{m})^{\frac{2k}{9}+1}), \end{equation*} for fixed positive integer $k$ and $m\rightarrow\infty$. These slightly improve the previously known lower bound $R_{k}(C_{2\ell+1};K_m)=\Omega(m^{\frac{k}{2\ell-1}+1}/(\log m)^{k+\frac{2k}{2\ell-1}})$ obtained by Alon and R\"{o}dl. The proof is based on random block constructions and random blowups argument.

In nonadaptive group testing, the main research objective is to design an efficient algorithm to identify a set of up to $t$ positive elements among $n$ samples with as few tests as possible. Disjunct matrices and separable matrices are two classical combinatorial structures while one provides a more efficient decoding algorithm and the other needs fewer tests, i.e., larger rate. Recently, a notion of strongly separable matrix has been introduced, which has the same identifying ability as a disjunct matrix, but has larger rate. In this paper, we use a modified probabilistic method to improve the lower bounds for the rate of strongly separable matrices. Using this method, we also improve the lower bounds for some well-known combinatorial structures, including locally thin set families and cancellative set families., Comment: 8 pages. arXiv admin note: substantial text overlap with arXiv:2108.07987

The Tur\'{a}n problem asks for the largest number of edges ex$(n,H)$ in an $n$-vertex graph not containing a fixed forbidden subgraph $H$, which is one of the most important problems in extremal graph theory. However the order of magnitude of ex$(n,H)$ for bipartite graphs is known only in a handful of cases. In particular, giving explicit constructions of extremal graphs is very challenging in this field. In this paper, we develop a polynomail resultant approach to algebraic construction of explicit extremal graphs, which can efficiently decide whether a specified structure exists. A key insight in our approach is the multipolynomial resultant, which is a fundamental tool of computational algebraic geometry. Our main results include the matched lowers bounds for Tur\'{a}n number of $1$-subdivision of $K_{3,t_{1}}$ and linear Tur\'{a}n number of Berge theta hyerpgraph $\Theta_{3,t_{2}}^{B}$ with $t_{1}=25$ and $t_{2}=217$. Moreover, the constant $t_{1}$ improves the random algebraic construction of Bukh and Conlon~[Rational exponents in extremal graph theory, J. Eur. Math. Soc. 20 (2018), 1747-1757] and makes progress on the known estimation for the smallest value of $t_{1}$ concerning a problem posed by Conlon, Janzer and Lee ~[More on the extremal number of subdivisions, Combinatorica, to appear], while the constant $t_{2}$ improves a result of He and Tait~[Hypergraphs with few berge paths of fixed length between vertices, SIAM J. Discrete Math., 33(3), 1472-1481]., Comment: 46 pages. arXiv admin note: substantial text overlap with arXiv:2002.06795, arXiv:1908.01459

Secure codes are widely-studied combinatorial structures which were introduced for traitor tracing in broadcast encryption. To determine the maximum size of such structures is the main research objective. In this paper, we investigate the lower bounds for secure codes and their related structures. First, we give some improved lower bounds for the rates of $2$-frameproof codes and $\overline{2}$-separable codes for slightly large alphabet size. Then we improve the lower bounds for the rate of some related structures, i.e., strongly $2$-separable matrices and $2$-cancellative set families. Finally, we give a general method to derive new lower bounds for strongly $t$-separable matrices and $t$-cancellative set families for $t\ge 3.$, Comment: There are errors in Sections II and III. The proofs of Theorems II.6 and III.3 are wrong

We study some sum-product problems over matrix rings. Firstly, for $A, B, C\subseteq M_n(\mathbb{F}_q)$, we have $$ |A+BC|\gtrsim q^{n^2}, $$ whenever $|A||B||C|\gtrsim q^{3n^2-\frac{n+1}{2}}$. Secondly, if a set $A$ in $M_n(\mathbb{F}_q)$ satisfies $|A|\geq C(n)q^{n^2-1}$ for some sufficiently large $C(n)$, then we have $$ \max\{|A+A|, |AA|\}\gtrsim \min\left\{\frac{|A|^2}{q^{n^2-\frac{n+1}{4}}}, q^{n^2/3}|A|^{2/3}\right\}. $$ 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., Comment: 18 pages

Erd\H{o}s posed the problem of finding conditions on a graph $G$ that imply the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We generalize this problem to general cases. Let $\delta_r$ be the least number so that any graph $G$ on $n$ vertices with minimum degree $\delta_rn$ has the property $P_{r-1}(G)=K_rf(G),$ where $P_{r-1}(G)$ is the largest number of edges in an $(r-1)$-partite subgraph and $K_rf(G)$ is the largest number of edges in a $K_r$-free subgraph. We show that $\frac{3r-4}{3r-1}<\delta_r\le\frac{4(3r-7)(r-1)+1}{4(r-2)(3r-4)}$ when $r\ge4.$ In particular, $\delta_4\le 0.9415.$, Comment: 16 pages

For a graph $H$ and a $k$-chromatic graph $F,$ if the Tur\'an 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\'an-good, or $k$-Tur\'an-good for short if $F$ is $K_k.$ In this paper, we construct some new classes of $k$-Tur\'an-good graphs and prove that $P_4$ and $P_5$ are $k$-Tur\'an-good for $k\ge4.$, Comment: 16 pages

A Nikodym set $\mathcal{N}\subseteq(\mathbb{Z}/(N\mathbb{Z}))^n$ is a set containing $L\setminus\{x\}$ for every $x\in(\mathbb{Z}/(N\mathbb{Z}))^n$, where $L$ is a line passing through $x$. We prove that if $N$ is square-free, then the size of every Nikodym set is at least $c_nN^{n-o(1)}$, where $c_n$ only depends on $n$. This result is an extension of the result in the finite field case., Comment: There is a much simpler proof

Ever since the famous Erd\H{o}s-Ko-Rado theorem initiated the study of intersecting families of subsets, extremal problems regarding intersecting properties of families of various combinatorial objects have been extensively investigated. Among them, studies about families of subsets, vector spaces and permutations are of particular concerns. Recently, the authors proposed a new quantitative intersection problem for families of subsets: For $\mathcal{F}\subseteq {[n]\choose k}$, define its \emph{total intersection number} as $\mathcal{I}(\mathcal{F})=\sum_{F_1,F_2\in \mathcal{F}}|F_1\cap F_2|$. Then, what is the structure of $\mathcal{F}$ when it has the maximal total intersection number among all families in ${[n]\choose k}$ with the same family size? In \cite{KG2020}, the authors studied this problem and characterized extremal structures of families maximizing the total intersection number of given sizes. In this paper, we consider the analogues of this problem for families of vector spaces and permutations. For certain ranges of family size, we provide structural characterizations for both families of subspaces and families of permutations having maximal total intersection numbers. To some extent, these results determine the unique structure of the optimal family for some certain values of $|\mathcal{F}|$ and characterize the relation between having maximal total intersection number and being intersecting. Besides, we also show several upper bounds on the total intersection numbers for both families of subspaces and families of permutations of given sizes., Comment: 33 pages, to appear in SCIENCE CHINA Mathematics

Given a graph $H$ and an integer $k\geqslant 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})=\Omega(n^{1+\frac{1}{2t-3}})$ where $H_{t}$ is the $1$-subdivision of the complete graph $K_{t}$. This answers a question of Conlon and Tyomkyn (arXiv: 2002.00921)., Comment: 9 pages

Let $\mathcal{H}$ be an $r$-uniform hypergraph. The Tur\'{a}n number $\text{ex}(n,\mathcal{H})$ is the maximum number of edges in an $n$-vertex $\mathcal{H}$-free $r$-uniform hypergraph. The Tur\'{a}n density of $\mathcal{H}$ is defined by \[\pi(\mathcal{H})=\lim_{n\rightarrow\infty}\frac{\text{ex}(n,\mathcal{H})}{\binom{n}{r}}.\] In this paper, we consider the Tur\'{a}n density of projective geometries. We give two new constructions of $PG_{m}(q)$-free hypergraphs which improve some results given by Keevash (J. Combin. Theory Ser. A, 111: 289--309, 2005). Based on an upper bound of blocking sets of $PG_m(q)$, we give a new general lower bound for the Tur\'{a}n density of $PG_{m}(q)$. By a detailed analysis of the structures of complete arcs in $PG_2(q)$, we also get better lower bounds for the Tur\'{a}n density of $PG_2(q)$ with $q=3,\ 4,\ 5,\ 7,\ 8$., Comment: 15 pages

In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn~(arXiv: 2002.00921). Given a graph $H$ and an integer $k\geqslant 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$. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge-coloring of $K_{n}$ and show that $f_{k}(n, C_{4})=\Theta(n)$ when $k\geqslant 3$ and $n\rightarrow\infty$. The methods we used in the edge-coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs $G$ and $H,$ let $r(G,H,q)$ be the minimum number of edge-colors (not necessarily proper) of $G$, such that the edges of every copy of $H\subseteq G$ together receive at least $q$ distinct colors. Establishing the relation to the Tur\'{a}n number of specified bipartite graphs, we obtain some general lower bounds for $r(K_{n,n},K_{s,t},q)$ with a broad range of $q$., Comment: 13 pages, accepted by SIAM Journal on Discrete Mathematics

A family of subsets $\mathcal{F}\subseteq {[n]\choose k}$ is called intersecting if any two of its members share a common element. Consider an intersecting family, a direct problem is to determine its maximal size and the inverse problem is to characterize its extremal structure and its corresponding stability. The famous Erd\H{o}s-Ko-Rado theorem answered both direct and inverse problems and led the era of studying intersection problems for finite sets. In this paper, we consider the following quantitative intersection problem which can be viewed an inverse problem for Erd\H{o}s-Ko-Rado type theorems: For $\mathcal{F}\subseteq {[n]\choose k}$, define its \emph{total intersection} as $\mathcal{I}(\mathcal{F})=\sum_{F_1,F_2\in \mathcal{F}}|F_1\cap F_2|$. Then, what is the structure of $\mathcal{F}$ when it has the maximal total intersection among all families in ${[n]\choose k}$ with the same family size? Using a pure combinatorial approach, we provide two structural characterizations of the optimal family of given size that maximizes the total intersection. As a consequence, for $n$ large enough and $\mathcal{F}$ of proper size, these characterizations show that the optimal family $\mathcal{F}$ is indeed $t$-intersecting ($t\geq 1$). To a certain extent, this reveals the relationship between properties of being intersecting and maximizing the total intersection. Also, we provide an upper bound on $\mathcal{I}(\mathcal{F})$ for several ranges of $|\mathcal{F}|$ and determine the unique optimal structure for families with sizes of certain values., Comment: 36 pages

For a graph $H$, the 1-subdivision of $H$, denoted by $H'$, is the graph obtained by replacing the edges of $H$ by internally disjoint paths of length 2. Recently, Conlon, Janzer and Lee (arXiv: 1903.10631) asked the following question: For any integer $s\ge2$, estimate the smallest $t$ such that $\textup{ex}(n,K_{s,t}')=\Omega(n^{\frac{3}{2}-\frac{1}{2s}})$. In this paper, we consider the case $s=3$. More precisely, we provide an explicit construction giving \begin{align*} \text{ex}(n,K_{3,30}')=\Omega(n^{\frac{4}{3}}), \end{align*} which reduces the estimation for the smallest value of $t$ from a magnitude of $10^{56}$ to the number $30$. The construction is algebraic, which is based on some equations over finite fields., Comment: 15 pages

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., Comment: accepted to IEEE Transaction on Information Theory

Let $\{(A_i,B_i)\}_{i=1}^{m}$ be a collection of pairs of sets with $|A_i|=a$ and $|B_i|=b$ for $1\leq i\leq m$. Suppose that $A_i\cap B_j=\emptyset$ if and only if $i=j$, then by the famous Bollob\'{a}s theorem, we have the size of this collection $m\leq {a+b\choose a}$. In this paper, we consider a variant of this problem by setting $\{A_i\}_{i=1}^{m}$ to be intersecting additionally. Using exterior algebra method, we prove a weighted Bollob\'{a}s type theorem for finite dimensional real vector spaces under these constraints. As a consequence, we have a similar theorem for finite sets, which settles a recent conjecture of Gerbner et. al \cite{GKMNPTX2019}. Moreover, we also determine the unique extremal structure of $\{(A_i,B_i)\}_{i=1}^{m}$ for the primary case of the theorem for finite sets.

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., Comment: 15 pages; accepted to IEEE Transaction on Information Theory