Page 259 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 259
COMBINATORIAL DESIGNS (MS-16)
Separating hash families have numerous applications in combinatorial cryptography and in the
construction of various combinatorial arrays; typically, one only considers whether two symbols
are the same or different. We instead employ symbols that have algebraic significance.
We consider an SHFλ(N ; k, qs, {w1, . . . , ws}) whose symbols are column vectors from Fqs.
The entry in row r and column c of the SHF is denoted by vr,c. Suppose that C1, . . . , Cs is a
set of disjoint sets of columns. Row r is covering for {C1, . . . , Cs} if, whenever we choose s
columns {γi ∈ Ci : 1 ≤ i ≤ s}, the s × s matrix [vr,γ1 · · · vr,γs] is nonsingular over Fq. Then
the SHFλ(N ; k, qs, {w1, . . . , ws}) is covering if, for every way to choose {C1, . . . , Cs}, there
are at least λ covering rows.
We establish that covering separating hash families of type 1td1 give an effective construc-
tion for detecting arrays, which are useful in screening complex systems to find interactions
among t or fewer factors without being masked by d or fewer other interactions. This connec-
tion easily accommodates outlier and missing responses in the screening. We explore asymp-
totic existence results and explicit constructions using finite geometries for covering separating
hash families. We develop randomized and derandomized construction algorithms and discuss
consequences for detecting arrays. This is joint work with Violet R. Syrotiuk (ASU).
Factorizations of infinite graphs
Simone Costa, simone.costa@unibs.it
University of Brescia, Italy
Coauthor: Tommaso Traetta
Let F = {Fα : α ∈ A} be a family of infinite graphs. The Factorization Problem F P (F, Λ)
asks whether F can be realized as a factorization of a given infinite graph Λ, namely, whether
there is a factorization G = {Γα : α ∈ A} of Λ such that each Γα is a copy of Fα.
Inspired by the results on regular 1-factorizations of infinite complete graphs [1] and on the
resolvability of infinite designs [4], we study this problem when Λ is either the Rado graph R
or the complete graph Kℵ of infinite order ℵ. When F is a countable family, we show that
F P (F, R) is solvable if and only if each graph in F has no finite dominating set. Generaliz-
ing the existence result of [2], we also prove that F P (F, Kℵ) admits a solution whenever the
cardinality F coincides with the order and the domination numbers of its graphs.
Finally, in the case of countable complete graphs, we show some non-existence results when
the domination numbers of the graphs in F are finite.
References
[1] S. Bonvicini and G. Mazzuoccolo. Abelian 1-factorizations in infinite graphs, European J.
Combin., 31 (2010), 1847–1852.
[2] S. Costa. A complete solution to the infinite Oberwolfach problem, J. Combin. Des., 28
(2020), 366–383.
[3] S. Costa and T. Traetta. Factorizing the Rado graph and infinite complete graphs, Submit-
ted (arXiv:2103.11992).
[4] P. Danziger, D. Horsley and B. S. Webb. Resolvability of infinite designs, J. Combin.
Theory Ser. A, 123 (2014), 73–85.
257
Separating hash families have numerous applications in combinatorial cryptography and in the
construction of various combinatorial arrays; typically, one only considers whether two symbols
are the same or different. We instead employ symbols that have algebraic significance.
We consider an SHFλ(N ; k, qs, {w1, . . . , ws}) whose symbols are column vectors from Fqs.
The entry in row r and column c of the SHF is denoted by vr,c. Suppose that C1, . . . , Cs is a
set of disjoint sets of columns. Row r is covering for {C1, . . . , Cs} if, whenever we choose s
columns {γi ∈ Ci : 1 ≤ i ≤ s}, the s × s matrix [vr,γ1 · · · vr,γs] is nonsingular over Fq. Then
the SHFλ(N ; k, qs, {w1, . . . , ws}) is covering if, for every way to choose {C1, . . . , Cs}, there
are at least λ covering rows.
We establish that covering separating hash families of type 1td1 give an effective construc-
tion for detecting arrays, which are useful in screening complex systems to find interactions
among t or fewer factors without being masked by d or fewer other interactions. This connec-
tion easily accommodates outlier and missing responses in the screening. We explore asymp-
totic existence results and explicit constructions using finite geometries for covering separating
hash families. We develop randomized and derandomized construction algorithms and discuss
consequences for detecting arrays. This is joint work with Violet R. Syrotiuk (ASU).
Factorizations of infinite graphs
Simone Costa, simone.costa@unibs.it
University of Brescia, Italy
Coauthor: Tommaso Traetta
Let F = {Fα : α ∈ A} be a family of infinite graphs. The Factorization Problem F P (F, Λ)
asks whether F can be realized as a factorization of a given infinite graph Λ, namely, whether
there is a factorization G = {Γα : α ∈ A} of Λ such that each Γα is a copy of Fα.
Inspired by the results on regular 1-factorizations of infinite complete graphs [1] and on the
resolvability of infinite designs [4], we study this problem when Λ is either the Rado graph R
or the complete graph Kℵ of infinite order ℵ. When F is a countable family, we show that
F P (F, R) is solvable if and only if each graph in F has no finite dominating set. Generaliz-
ing the existence result of [2], we also prove that F P (F, Kℵ) admits a solution whenever the
cardinality F coincides with the order and the domination numbers of its graphs.
Finally, in the case of countable complete graphs, we show some non-existence results when
the domination numbers of the graphs in F are finite.
References
[1] S. Bonvicini and G. Mazzuoccolo. Abelian 1-factorizations in infinite graphs, European J.
Combin., 31 (2010), 1847–1852.
[2] S. Costa. A complete solution to the infinite Oberwolfach problem, J. Combin. Des., 28
(2020), 366–383.
[3] S. Costa and T. Traetta. Factorizing the Rado graph and infinite complete graphs, Submit-
ted (arXiv:2103.11992).
[4] P. Danziger, D. Horsley and B. S. Webb. Resolvability of infinite designs, J. Combin.
Theory Ser. A, 123 (2014), 73–85.
257
