Source author record

Simone Costa

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT math.GR

Catalog footprint

Research overview

10works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Improved Bounds for $(b,k)$ -hashing

For fixed integers $b\geq k$ , a problem of relevant interest in computer science and combinatorics is that of determining the asymptotic growth, with $n$ , of the largest set for which a $(b, k)$ -hash family of $n$ functions exists. Equivalently, determining the asymptotic growth of a largest 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. An important asymptotic upper bound for general $b, 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 the general $b,k$ case 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 both show how some of the latter results extend to $b\neq k$ and further strengthen the bounds for some specific small values of $b$ and $k$ . The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity which could be reduced by using more sophisticated and optimized algorithmic approaches.

preprint2022arXiv

Non-zero sum Heffter arrays and their applications

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 $\mathrm{N}\mathrm{H}(m,n; h,k)$ is an $m \times n$ p. f. array with entries in $\mathbb{Z}_{2nk+1}$ such that: each row contains $h$ filled cells and each column contains $k$ filled cells; for every $x\in \mathbb{Z}_{2nk+1}\setminus\{0\}$ , either $x$ or $-x$ appears in the array; the sum of the elements in every row and column is different from $0$ (in $\mathbb{Z}_{2nk+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 "globally simple" is required. Finally, we show how these arrays can be used to construct biembeddings of complete graphs.

preprint2022arXiv

On Sequences in Cyclic Groups with Distinct Partial Sums

A subset of an abelian group is {\em sequenceable} if there is an ordering $(x_1, \ldots, x_k)$ of its elements such that the partial sums $(y_0, y_1, \ldots, y_k)$ , given by $y_0 = 0$ and $y_i = \sum_{j=1}^i x_i$ for $1 \leq i \leq k$ , are distinct, with the possible exception that we may have $y_k = y_0 = 0$ . We demonstrate the sequenceability of subsets of size $k$ of $\mathbb{Z}_n \setminus \{ 0 \}$ when $n = mt$ in many cases, including when $m$ is either prime or has all prime factors larger than $k! /2$ for $k \leq 11$ and $t \leq 5$ and for $k=12$ and $t \leq 4$ . We obtain similar, but partial, results for $13 \leq k \leq 15$ . This represents progress on a variety of questions and conjectures in the literature concerning the sequenceability of subsets of abelian groups, which we combine and summarize into the conjecture that if a subset of an abelian group does not contain 0 then it is sequenceable.

preprint2022arXiv

On the number of non-isomorphic (simple) $k$ -gonal biembeddings of complete multipartite graphs

This article aims to provide exponential lower bounds on the number of non-isomorphic $k$ -gonal biembeddings of the complete multipartite graph into orientable surfaces. For this purpose, we use the concept, introduced by Archdeacon in 2015, of Heffer array and its relations with graph embeddings. In particular we show that, under certain hypotheses, from a single Heffter array, we can obtain an exponential number of distinct graph embeddings. Exploiting this idea starting from the arrays constructed by Cavenagh, Donovan and Yazici in 2020, we obtain that, for infinitely many values of $k$ and $v$ , there are at least $k^{\frac{k}{2}+o(k)} \cdot 2^{v\cdot \frac{H(1/4)}{(2k)^2}+o(v)}$ non-isomorphic $k$ -gonal biembeddings of $K_v$ , where $H(\cdot)$ is the binary entropy. Moreover about the embeddings of $K_{\frac{v}{t}\times t}$ , for $t\in\{1,2,k\}$ , we provide a construction of $2^{v\cdot \frac{H(1/4)}{2k(k-1)}+o(v,k)}$ non-isomorphic $k$ -gonal biembeddings whenever $k$ is odd and $v$ belongs to a wide infinite family of values.

preprint2022arXiv

Weak Sequenceability in Cyclic Groups

A subset $A$ of an abelian group $G$ is sequenceable if there is an ordering $(a_1, \ldots, a_k)$ of its elements such that the partial sums $(s_0, s_1, \ldots, s_k)$ , given by $s_0 = 0$ and $s_i = \sum_{j=1}^i a_i$ for $1 \leq i \leq k$ , are distinct, with the possible exception that we may have $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 in $[4]$ 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$ do not sum to $0$ then there exists a simple path $P$ in the Cayley graph $Cay[G:\pm A]$ such that $Δ(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$ of girth bigger than $t$ (for a given $t < k$ ) and such that $Δ(W) = \pm A$ . This is possible given that the partial sums $s_i$ and $s_j$ are different whenever $i$ and $j$ are distinct and $|i-j|\leq t$ . In this case, we say that the set $A$ is $t$ -weak sequenceable. The main result here presented is that any subset $A$ of $\mathbb{Z}_p\setminus \{0\}$ is $t$ -weak sequenceable whenever $t<7$ or when $A$ does not contain pairs of type $\{x,-x\}$ and $t<8$ .

preprint2021arXiv

New upper bounds for $(b,k)$ -hashing

For fixed integers $b\geq k$ , the problem of perfect $(b,k)$ -hashing asks for the asymptotic growth of largest subsets of $\{1,2,\ldots,b\}^n$ such that for any $k$ distinct elements in the set, there is a coordinate where they all differ. An important asymptotic upper bound for general $b, 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 the general $b,k$ case 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 both show how some of the latter results extend to $b\neq k$ and further strengthen the bounds for some specific small values of $b$ and $k$ . The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity.

preprint2020arXiv

New bounds for perfect $k$ -hashing

Let $C\subseteq \{1,\ldots,k\}^n$ be such that for any $k$ distinct elements of $C$ there exists a coordinate where they all differ simultaneously. Fredman and Komlós studied upper and lower bounds on the largest cardinality of such a set $C$ , in particular proving that as $n\to\infty$ , $|C|\leq \exp(n k!/k^{k-1}+o(n))$ . Improvements over this result where first derived by different authors for $k=4$ . More recently, Guruswami and Riazanov showed that the coefficient $k!/k^{k-1}$ is certainly not tight for any $k>3$ , although they could only determine explicit improvements for $k=5,6$ . For larger $k$ , their method gives numerical values modulo a conjecture on the maxima of certain polynomials. In this paper, we first prove their conjecture, completing the explicit computation of an improvement over the Fredman-Komlós bound for any $k$ . Then, we develop a different method which gives substantial improvements for $k=5,6$ .

preprint2020arXiv

Relative Heffter arrays and biembeddings

Relative Heffter arrays, denoted by $\mathrm{H}_t(m,n; s,k)$ , have been introduced as a generalization of the classical concept of Heffter array. A $\mathrm{H}_t(m,n; s,k)$ is an $m\times n$ partially filled array with elements in $\mathbb{Z}_v$ , where $v=2nk+t$ , whose rows contain $s$ filled cells and whose columns contain $k$ filled cells, such that the elements in every row and column sum to zero and, for every $x\in \mathbb{Z}_v$ not belonging to the subgroup of order $t$ , either $x$ or $-x$ appears in the array. In this paper we show how relative Heffter arrays can be used to construct biembeddings of cyclic cycle decompositions of the complete multipartite graph $K_{\frac{2nk+t}{t}\times t}$ into an orientable surface. In particular, we construct such biembeddings providing integer globally simple square relative Heffter arrays for $t=k=3,5,7,9$ and $n\equiv 3 \pmod 4$ and for $k=3$ with $t=n,2n$ , any odd $n$ .

preprint2020arXiv

Some new results about a conjecture by Brian Alspach

In this paper we consider the following conjecture, proposed by Brian Alspach, concerning partial sums in finite cyclic groups: given a subset $A$ of $\mathbb{Z}_n\setminus \{0\}$ of size $k$ such that $\sum_{z\in A} z\not= 0$ , it is possible to find an ordering $(a_1,\ldots,a_k)$ of the elements of $A$ such that the partial sums $s_i=\sum_{j=1}^i a_j$ , $i=1,\ldots,k$ , are nonzero and pairwise distinct. This conjecture is known to be true for subsets of size $k\leq 11$ in cyclic groups of prime order. Here, we extend such result to any torsion-free abelian group and, as a consequence, we provide an asymptotic result in $\mathbb{Z}_n$ . We also consider a related conjecture, originally proposed by Ronald Graham: given a subset $A$ of $\mathbb{Z}_p\setminus\{0\}$ , where $p$ is a prime, there exists an ordering of the elements of $A$ such that the partial sums are all distinct. Working with the methods developed by Hicks, Ollis and Schmitt, based on the Alon's combinatorial Nullstellensatz, we prove the validity of such conjecture for subsets $A$ of size $12$ .

preprint2014arXiv

On MPS construction of blocking sets in projective spaces: a generalization

In this paper we provide a generalization of the MPS construction of blocking sets of $PG(r,q^n)$ using subspaces of dimension $s\leq n-2$ . By this construction, we determine a new non-planar example in $PG(3,q^6)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Simone Costa

Research overview

Is this your work?

10 publications

Improved Bounds for $(b,k)$ -hashing

Non-zero sum Heffter arrays and their applications

On Sequences in Cyclic Groups with Distinct Partial Sums

On the number of non-isomorphic (simple) $k$ -gonal biembeddings of complete multipartite graphs

Weak Sequenceability in Cyclic Groups

New upper bounds for $(b,k)$ -hashing

New bounds for perfect $k$ -hashing

Relative Heffter arrays and biembeddings

Some new results about a conjecture by Brian Alspach

On MPS construction of blocking sets in projective spaces: a generalization

See the researcher in context

Building this map preview

Simone Costa

Research overview

Is this your work?

10 publications

Improved Bounds for (b,k)(b,k)(b,k)-hashing

Non-zero sum Heffter arrays and their applications

On Sequences in Cyclic Groups with Distinct Partial Sums

On the number of non-isomorphic (simple) kkk-gonal biembeddings of complete multipartite graphs

Weak Sequenceability in Cyclic Groups

New upper bounds for (b,k)(b,k)(b,k)-hashing

New bounds for perfect kkk-hashing

Relative Heffter arrays and biembeddings

Some new results about a conjecture by Brian Alspach

On MPS construction of blocking sets in projective spaces: a generalization

See the researcher in context

Building this map preview

Improved Bounds for $(b,k)$ -hashing

On the number of non-isomorphic (simple) $k$ -gonal biembeddings of complete multipartite graphs

New upper bounds for $(b,k)$ -hashing

New bounds for perfect $k$ -hashing