Page 266 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 266
COMBINATORIAL DESIGNS (MS-16)
Sequences in Zn with Distinct Partial Sums
Matt Ollis, matt@marlboro.edu
Marlboro College, United States
Coauthors: Jacob Hicks, Sarah Rovner-Frydman, John Schmitt
Let Zn = {0, 1, . . . , n − 1} be the integers modulo n. For a sequence of elements a1, . . . , ak
of Zn, define its partial sums b0, . . . , bk by b0 = 0 and bi = a1 + · · · + ai for 1 ≤ i ≤ k. For
which subsets S ⊆ Zn \ {0} is it possible to order the elements of S so that the partial sums are
distinct?
When the sum of the elements of S is 0, there can be no such ordering. Alspach conjectures
that this is the only obstacle; that is, every subset S whose sum is nonzero has an ordering with
distinct partial sums.
We show how to translate the problem into one of finding monomials with non-zero coeffi-
cients in particular polynomials over Zp, where p is a prime divisor of n, using Alon’s Combi-
natorial Nullstellensatz. The approach offers hope for a full proof of the conjecture, and can be
used in conjunction with a computational approach in cases where n = pt with p prime and t
and |S| small.
Universal sequences and Euler tours in hypergraphs
Deryk Osthus, d.osthus@bham.ac.uk
University of Birmingham, United Kingdom
Coauthors: Daniela Kühn, Stefan Glock, Felix Joos
We show that a quasirandom k-uniform hypergraph G has a tight Euler tour subject to the
necessary condition that k divides all vertex degrees. The case when G is complete confirms a
$100 conjecture of Chung, Diaconis and Graham from 1989 on the existence of universal cycles
for the k-subsets of an n-set.
Our proof is based on random walks and the proof of the existence of H-designs (by Glock,
Kühn, Lo and Osthus), i.e. decompositions of a complete hypergraph into copies of an arbitrary
hypergraph H (subject to divisibility conditions).
A reduction of the spectrum problem for sun systems
Anita Pasotti, anita.pasotti@unibs.it
University of Brescia, Italy
Coauthors: Marco Buratti, Tommaso Traetta
A k-cycle with a pendant edge attached to each vertex is called a k-sun. When we approached
the existence problem for k-sun systems of order v, complete solutions were known only for
k = 3, 4, 5, 6, 8, 10, 14 and for k = 2t. Here, we reduce this problem to the orders v in the range
2k < v < 6k satisfying the obvious necessary conditions. Thanks to this result, we provide a
complete solution whenever k is an odd prime, and some partial results whenever k is twice a
prime.
264
Sequences in Zn with Distinct Partial Sums
Matt Ollis, matt@marlboro.edu
Marlboro College, United States
Coauthors: Jacob Hicks, Sarah Rovner-Frydman, John Schmitt
Let Zn = {0, 1, . . . , n − 1} be the integers modulo n. For a sequence of elements a1, . . . , ak
of Zn, define its partial sums b0, . . . , bk by b0 = 0 and bi = a1 + · · · + ai for 1 ≤ i ≤ k. For
which subsets S ⊆ Zn \ {0} is it possible to order the elements of S so that the partial sums are
distinct?
When the sum of the elements of S is 0, there can be no such ordering. Alspach conjectures
that this is the only obstacle; that is, every subset S whose sum is nonzero has an ordering with
distinct partial sums.
We show how to translate the problem into one of finding monomials with non-zero coeffi-
cients in particular polynomials over Zp, where p is a prime divisor of n, using Alon’s Combi-
natorial Nullstellensatz. The approach offers hope for a full proof of the conjecture, and can be
used in conjunction with a computational approach in cases where n = pt with p prime and t
and |S| small.
Universal sequences and Euler tours in hypergraphs
Deryk Osthus, d.osthus@bham.ac.uk
University of Birmingham, United Kingdom
Coauthors: Daniela Kühn, Stefan Glock, Felix Joos
We show that a quasirandom k-uniform hypergraph G has a tight Euler tour subject to the
necessary condition that k divides all vertex degrees. The case when G is complete confirms a
$100 conjecture of Chung, Diaconis and Graham from 1989 on the existence of universal cycles
for the k-subsets of an n-set.
Our proof is based on random walks and the proof of the existence of H-designs (by Glock,
Kühn, Lo and Osthus), i.e. decompositions of a complete hypergraph into copies of an arbitrary
hypergraph H (subject to divisibility conditions).
A reduction of the spectrum problem for sun systems
Anita Pasotti, anita.pasotti@unibs.it
University of Brescia, Italy
Coauthors: Marco Buratti, Tommaso Traetta
A k-cycle with a pendant edge attached to each vertex is called a k-sun. When we approached
the existence problem for k-sun systems of order v, complete solutions were known only for
k = 3, 4, 5, 6, 8, 10, 14 and for k = 2t. Here, we reduce this problem to the orders v in the range
2k < v < 6k satisfying the obvious necessary conditions. Thanks to this result, we provide a
complete solution whenever k is an odd prime, and some partial results whenever k is twice a
prime.
264
