We may not have regular talks yet, but we are trying to
revive our seminar (under a new name!). DM talks under a different
umbrella are included.
| SERIES | C&O Discrete Math Seminar |
| TITLE | My favorite problem in secret sharing |
| SPEAKER | Andrej Bogdanov, University of Ottawa |
| DATE | Friday, September 27, 2024 |
| TIME | 15:00 |
| ROOM | STM 364 |
| ABSTRACT |
A bit of information is shared among Alice, Bob, Carol, Dave, Fred, and Eve. Any four of them can recover it, yet any three of them know nothing about it. Is this possible? In 1979 Shamir showed that it is, provided each party can spare log 7 bits of memory. What if they are log 1 bit short? I will tell you why this question fascinates me, why I believe that it can be cracked, and how a circuitous route from “does P equal NP?” leads to it. |
| SERIES | C&O Discrete Math Seminar |
| TITLE | Three short talks on covering arrays, and
one on the Honeymoon Oberwolfach Problem |
| SPEAKERS | Kianoosh Shokri, Prangya Parida, Lucia
Moura, and Masoomeh Akbari |
| DATE | Friday, November 22, 2024 |
| TIME | 14:30 |
| ROOM | STM 364 |
| ABSTRACTS |
Speaker:
Kianoosh
Shokri Title: A
construction of strength-4 covering arrays using
three k-caps in PG(3, q) Abstract: A
covering
array, denoted by CA(N; t, k, v), is an N x k array
over an alphabet with v
symbols with the property that for any t-set of
column indices c_1, ..., c_t,
each t-tuple of the alphabet occurs at least once as
a row of the sub-array
indexed by c_1, ..., c_t. Here, N is the size,
and t is the strength of
the covering array.
Raaphorst, Moura, and
Stevens (2014) give a construction for a CA(2q^3-1;
3, q^2 + q + 1, q), which
is obtained by two projective planes PG(2,q) such
that any three collinear
points in one, is mapped to three non-collinear
points in the other.
A k-cap of PG(m-1, q) is
a set of k points of PG(m-1, q), no three of which
are collinear. In PG(3,q),
an ovoid is a k-cap with a maximum size of k. In a paper by Tzanakis, Moura, Panario,
and Stevens (2016), a
CA(511; 4, 17, 4) is constructed, which was formed
by two ovoids in PG(3, q)
such that any four coplanar points in one, is mapped
to four non-coplanar
points in the other.
In this talk, we give a
construction for strength-4 covering arrays using
three k-caps in PG(3,q),
which has been verified for odd prime powers q, 3
<= q <= 101. We
conjecture that our construction is valid for any
odd prime power q. This is
joint work with Lucia Moura. Speaker:
Prangya
Parida Title:
Cover-free families on graphs Abstract:
A family of subsets
of a t-set is called a
d-cover-free family if no subset is contained in
the union of any d other
subsets. We denote by t(d, n) the minimum t
for which there exists a
d-cover-free family of a t-set with n subsets.
Cover-free families (CFF) have
wide applications in combinatorial group testing,
where a d-CFF(t, n) can be
used to identify d defective items in a group of n
items with t tests. It is
well-known that t(1, n) can be obtained by
applying the famous Sperner's
Theorem. For d \geq 2, we rely on bounds for t(d,
n). Erdös, Frankl, and
Füredi provided bounds for t(2, n) using the
probabilistic method, given by 3.106
\log(n) < t(2, n) < 5.512 \log(n). Using a
derandomization technique,
Porat and Rothschild presented a deterministic
polynomial-time algorithm to
construct d-CFFs that achieves t = O(d^2 \log(n).
Some upper bounds on t(2, n)
(in some cases exact bounds) for small values
of n are provided by Li, van
Rees, and Wei in 2006. In
this talk, we extend the definition of a cover-free
family to include a graph
G, which we denote as \overline{G}-CFF, where the
edges of the graph specify
the pair of subsets whose union must not cover any
other subset. We denote by
t(G) the minimum t for which there exists a
\overline{G}-CFF. The
traditional 2-CFF(t, n) is a special case of
\overline{G}-CFF when G is a
complete graph of n vertices. This generalization of
cover-free families
provides a richer combinatorial structure that
lies between being a 1-CFF
and a 2-CFF. We
will discuss some classical results on cover-free
families, along with general
constructions of \overline{G}-CFFs, as well as
specific constructions for certain
families of graphs. We prove that for a graph G with
n vertices, t(1, n)
\leq t(G) \leq t(2, n) and show that for an infinite
family of Star graphs S_n
with n vertices, t(S_n) = t(1, n). Interestingly, we
also give a construction
of CFFs on a Path (P_n) or Cycle (C_n) with n
vertices using a mixed-radix Gray
code. This yields an upper bound for t(P_n) and
t(C_n) that is smaller than the
lower bound of t(2, n) mentioned above. This
is joint work with Lucia Moura. Speaker: Lucia
Moura Title: New
families
of strength-3 covering arrays using LFSR sequences Abstract: A
covering
array of strength t, denoted by CA(N; t, k, v), is
an N x k array C over an
alphabet with v symbols with the property that for
any subarray consisting of t
columns of C, every t-tuple of the alphabet appears
at least once as a row of
the subarray.
An orthogonal array is a
special case of a covering array, where each
$t$-tuple appears the same number
lambda of times, so N=lambda v^t.
Given t, k, v, we aim to
determine CAN(t, k, v) which is the minimum N for
which a CA(N; t, k, v)
exists. This is a hard problem in general, so we
seek good upper bounds for
CAN.
Raaphorst, Moura
and Stevens (DCC 2014) gave a construction for a
CA(2q^3-1; 3, q^2 + q + 1, q),
using linear feedback shift register sequences LFSR.
In the present work (to
appear in the Journal of Combinatorial Designs
2024), we explore the use of
this ``good'' ingredient to build covering arrays of
strength $3$ with a larger
number of columns via recursive constructions and
elimination of equivalent
rows. Several of these covering arrays
improve the best upper bounds
currently found in Colbourn's covering array tables.
This is joint work with
Kianoosh Shokri. Speaker:
Masoomeh Akbari Title: The Generalized
Honeymoon Oberwolfach Problem with one large table
of size 2m Abstract: The Honeymoon
Oberwolfach Problem (HOP), introduced by Šajna, is a
recent variant of the
classic Oberwolfach Problem. This problem asks
whether it is possible to seat
2m₁ + 2m₂ + ... + 2mₜ = 2n participants, consisting of n
newlywed couples, at t round
tables of sizes 2m₁, 2m₂, ..., 2mₜ for 2n - 2 successive nights so that
each participant sits next
to their spouse each night and next to each other
participant exactly once. HOP
has been studied by Jerade, Lepine, and Šajna, with
some significant cases
already solved.
We generalize HOP by allowing tables of size
two, rather than a minimum
size of four as previously defined in HOP. Thus, in
the generalized HOP, we aim
to seat the 2n participants at s tables of size 2
and t round tables of sizes
2m₁, 2m₂, ..., 2mₜ, with the requirement that 2n = 2s +
2m₁
+ 2m₂ + ... + 2mₜ and mᵢ ≥ 2. Our current goal is to
prove that the necessary
condition for the HOP with s tables of size 2 and
one large table of size 2m to
have a solution is sufficient. In this talk, we will
present a general approach
to this problem and discuss the progress we have
made so far. |
| SERIES | |
| TITLE |
|
| SPEAKER |
|
| DATE |
|
| TIME |
|
| ROOM |
|
| ABSTRACT |