Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe $rho$-Capacity of a Graph
95
0
0.0
(
0
)
Added by
Sihuang Hu
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Motivated by the problem of zero-error broadcasting, we introduce a new notion of graph capacity, termed $rho$-capacity, that generalizes the Shannon capacity of a graph. We derive upper and lower bounds on the $rho$-capacity of arbitrary graphs, and provide a Lovasz-type upper bound for regular graphs. We study the behavior of the $rho$-capacity under two graph operations: the strong product and the disjoint union. Finally, we investigate the connection between the structure of a graph and its $rho$-capacity.
rate research
Read More
We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lovasz theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of Index Coding.
Maximum distance separable (MDS) codes are very important in both theory and practice. There is a classical construction of a family of $[2^m+1, 2u-1, 2^m-2u+3]$ MDS codes for $1 leq u leq 2^{m-1}$, which are cyclic, reversible and BCH codes over $mathrm{GF}(2^m)$. The objective of this paper is to study the quaternary subfield subcodes and quaternary subfield codes of a subfamily of the MDS codes for even $m$. A family of quaternary cyclic codes is obtained. These quaternary codes are distance-optimal in some cases and very good in general. Furthermore, infinite families of $3$-designs from these quaternary codes are presented.
Consider two sequences of $n$ independent and identically distributed fair coin tosses, $X=(X_1,ldots,X_n)$ and $Y=(Y_1,ldots,Y_n)$, which are $rho$-correlated for each $j$, i.e. $mathbb{P}[X_j=Y_j] = {1+rhoover 2}$. We study the question of how large (small) the probability $mathbb{P}[X in A, Yin B]$ can be among all sets $A,Bsubset{0,1}^n$ of a given cardinality. For sets $|A|,|B| = Theta(2^n)$ it is well known that the largest (smallest) probability is approximately attained by concentric (anti-concentric) Hamming balls, and this can be proved via the hypercontractive inequality (reverse hypercontractivity). Here we consider the case of $|A|,|B| = 2^{Theta(n)}$. By applying a recent extension of the hypercontractive inequality of Polyanskiy-Samorodnitsky (J. Functional Analysis, 2019), we show that Hamming balls of the same size approximately maximize $mathbb{P}[X in A, Yin B]$ in the regime of $rho to 1$. We also prove a similar tight lower bound, i.e. show that for $rhoto 0$ the pair of opposite Hamming balls approximately minimizes the probability $mathbb{P}[X in A, Yin B]$.
The determination of weight distribution of cyclic codes involves evaluation of Gauss sums and exponential sums. Despite of some cases where a neat expression is available, the computation is generally rather complicated. In this note, we determine the weight distribution of a class of reducible cyclic codes whose dual codes may have arbitrarily many zeros. This goal is achieved by building an unexpected connection between the corresponding exponential sums and the spectrums of Hermitian forms graphs.
The codewords of weight $10$ of the $[42,21,10]$ extended binary quadratic residue code are shown to hold a design of parameters $3-(42,10,18).$ Its automorphism group is isomorphic to $PSL(2,41)$. Its existence can be explained neither by a transitivity argument, nor by the Assmus-Mattson theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
