اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe $rho$-Capacity of a Graph
95
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 $ma
thrm{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 larg
e (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 t
he 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
