In the last years, the theorem of Weil on multiplicative character sums has been very frequently used for getting existence results on combinatorial designs of various kinds. Case by case, the theorem has been applied directly and sometimes this required long and tedious calculations that could be avoided using a result that is a purely algebraic consequence of it. Here this result will be used, in particular, for giving a quick proof of the existence of a (q, k, λ) difference family for any admissible prime power $q > {k \chosse 2}^{2k}/g^{2k−2}$ where $g = \gcd({k \choose 2},λ)$, improving in this way the original bound $q > {k \choose}^{k^2 −k}$ given by R.M. Wilson [R.M. Wilson, Cyclotomic and difference families in elementary abelian groups, J. Number Theory 4 (1972) 17–47]. More generally, given any simple graph Γ, we prove that there exists an elementary abelian Γ-decomposition of the complete graph $K_q$ for any prime power q ≡ 1 (mod 2e) with $q > d^2e^{2d}$ where d and e are the max–min degree and the number of edges of Γ, respectively. This improves, in some cases enormously, Wilson’s bound $q > e^{k^2−k}$ where k is the number of vertices of Γ (see [R.M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, in: C.St.J.A. Nash-Williams, J.H. van Lint (Eds.), Proc. Fifth British Combinatorial Conference. in: Congr. Numer., vol. XV, 1975, pp. 647–659]). The algebraic consequence of the theorem of Weil will be also applied for getting significative existence results on Γ-decompositions of a complete g-partite graph $K_{g×q}$ with q a prime power.

Combinatorial designs and the theorem of Weil on multiplicative character sums

BURATTI, Marco;
2009

Abstract

In the last years, the theorem of Weil on multiplicative character sums has been very frequently used for getting existence results on combinatorial designs of various kinds. Case by case, the theorem has been applied directly and sometimes this required long and tedious calculations that could be avoided using a result that is a purely algebraic consequence of it. Here this result will be used, in particular, for giving a quick proof of the existence of a (q, k, λ) difference family for any admissible prime power $q > {k \chosse 2}^{2k}/g^{2k−2}$ where $g = \gcd({k \choose 2},λ)$, improving in this way the original bound $q > {k \choose}^{k^2 −k}$ given by R.M. Wilson [R.M. Wilson, Cyclotomic and difference families in elementary abelian groups, J. Number Theory 4 (1972) 17–47]. More generally, given any simple graph Γ, we prove that there exists an elementary abelian Γ-decomposition of the complete graph $K_q$ for any prime power q ≡ 1 (mod 2e) with $q > d^2e^{2d}$ where d and e are the max–min degree and the number of edges of Γ, respectively. This improves, in some cases enormously, Wilson’s bound $q > e^{k^2−k}$ where k is the number of vertices of Γ (see [R.M. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, in: C.St.J.A. Nash-Williams, J.H. van Lint (Eds.), Proc. Fifth British Combinatorial Conference. in: Congr. Numer., vol. XV, 1975, pp. 647–659]). The algebraic consequence of the theorem of Weil will be also applied for getting significative existence results on Γ-decompositions of a complete g-partite graph $K_{g×q}$ with q a prime power.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/174602
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 50
  • ???jsp.display-item.citation.isi??? 44
social impact