Search

A subset S $S$ of a group (G,+) $(G,+)$ is t $t$‐weakly sequenceable if there is an ordering (y1,...,yk) $({y}_{1},{\rm{\ldots }},{y}_{k})$ of its elements such that the partial sums s0,s1,...,sk ${s}_{0},{s}_{1},{\rm{\ldots }},{s}_{k}$, given by s0=0 ${s}_{0}=0$ and si=∑j=1iyj ${s}_{i}={\sum }_{j=1}^{i}{y}_{j}$ for 1≤i≤k $1\le i\le k$, satisfy si≠sj ${s}_{i}\ne {s}_{j}$ whenever and 1≤∣i−j∣≤t $1\le | i-j| \le t$. By Costa et al., it was proved that if the order of a group is pe $pe$ then all sufficiently large subsets of the nonidentity elements are t $t$‐weakly sequenceable when p>3 $p\gt 3$ is prime, e≤3 $e\le 3$ and t≤6 $t\le 6$. Inspired by this result, we show that, if G $G$ is the semidirect product of Zp ${{\mathbb{Z}}}_{p}$ and Z2 ${{\mathbb{Z}}}_{2}$ and the subset S $S$ is balanced, then S $S$ admits, regardless of its size, an alternating parityt $t$‐weak sequencing whenever p>3 $p\gt 3$ is prime and t≤8 $t\le 8$. A subset of G $G$ is balanced if it contains the same number of even elements and odd elements and an alternating parity ordering alternates even and odd elements. Then using a hybrid approach that combines both Ramsey theory and the probabilistic method we also prove, for groups G $G$ that are semidirect products of a generic (nonnecessarily abelian) group N $N$ and Z2 ${{\mathbb{Z}}}_{2}$, that all sufficiently large balanced subsets of the nonidentity elements admit an alternating parity t $t$‐weak sequencing. The same procedure works also for studying the weak sequenceability for generic sufficiently large (not necessarily balanced) sets. Here we have been able to prove that, if the size of a subset S $S$ of a group G $G$ is large enough and if S $S$ does not contain 0, then S $S$ is t $t$‐weakly sequenceable. [ABSTRACT FROM AUTHOR]

A subset A $A$ of an abelian group G $G$ is sequenceable if there is an ordering (a1,...,ak) $({a}_{1},\ldots ,{a}_{k})$ of its elements such that the partial sums (s0,s1,...,sk) $({s}_{0},{s}_{1},\ldots ,{s}_{k})$, given by s0=0 ${s}_{0}=0$ and si=∑j=1iaj ${s}_{i}={\sum }_{j=1}^{i}{a}_{j}$ for 1≤i≤k $1\le i\le k$, are distinct, with the possible exception that we may have sk=s0=0 ${s}_{k}={s}_{0}=0$. In the literature there are several conjectures and questions concerning the sequenceability of subsets of abelian groups, which have been combined and summarized by Alspach and Liversidge into the conjecture that if a subset of an abelian group does not contain 0 then it is sequenceable. If the elements of a sequenceable set A $A$ do not sum to 0 then there exists a simple path P $P$ in the Cayley graph Cay[G:±A] $Cay[G:\pm A]$ such that Δ(P)=±A ${\rm{\Delta }}(P)=\pm A$. In this paper, inspired by this graph–theoretical interpretation, we propose a weakening of this conjecture. Here, under the above assumptions, we want to find an ordering whose partial sums define a walk W $W$ of girth bigger than t $t$ (for a given t

For fixed integers $n$ and $b\geq k$ , let $A(b,k,n)$ the largest size of a subset of $\{1,2,\ldots,b\}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$. In this paper, we determine new exponential upper bounds for different values of $b$ and $k$. A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new class of partially filled arrays that, as Heffter arrays, are related to difference families, graph decompositions and biembeddings. A non-zero sum Heffter array N H (m , n ; h , k) is an m × n p.f. array with entries in Z 2 n k + 1 such that: each row contains h filled cells and each column contains k filled cells; for every x ∈ Z 2 n k + 1 ∖ { 0 } , either x or − x appears in the array; the sum of the elements in every row and column is different from 0 (in Z 2 n k + 1). Here first we explain the connections with relative difference families and with path decompositions of the complete multipartite graph. Then we present a complete solution for the existence problem and a constructive complete solution for the square case and for the rectangular case with no empty cells when the additional, very restrictive, property of being "globally simple" is required. Finally, we show how these arrays can be used to construct biembeddings of complete graphs. [ABSTRACT FROM AUTHOR]

We derive a simple proof, based on information theoretic inequalities, of an upper bound on the largest rates of q -ary 2 ‾ -separable codes that improves recent results of Wang for any q ≥ 13. For the case q = 2 , we recover a result of Lindström, but with a much simpler derivation. The method easily extends to give bounds on B 2 codes which, although not improving on Wang's results, use much simpler tools and might be useful for future applications. [ABSTRACT FROM AUTHOR]

Let { a 1 ,... , a n } be a set of positive integers with a 1 < ⋯ < a n such that all 2 n subset sums are distinct. A famous conjecture by Erdős states that a n > c ⋅ 2 n for some constant c , while the best result known to date is of the form a n > c ⋅ 2 n / n . In this paper, inspired by an information-theoretic interpretation, we extend the study to vector-valued elements a i ∈ Z k and we weaken the condition by requiring that only sums corresponding to subsets of size smaller than or equal to λ n be distinct. For this case, we derive lower and upper bounds on the smallest possible value of a n. [ABSTRACT FROM AUTHOR]