Robert Coulter,
The University of Delaware
Title: Permutation polynomials, representation theory, and projective
planes
We shall describe a recently developed method for constructing
groups of permutation polynomials (PPs) using representation theory.
Though the method can construct PP classes of interest in their
own right, the original motivation for its development comes from
a problem in projective geometry, that of constructing (or proving
non-existence of) certain types of projective planes. The underlining
ideas that connect the PP construction to these certain types
of projective planes will also be discussed.
--------------------------------------------------------------------
Peter Danziger, Ryerson University
Title: Orthogonally Resolvable Designs
A common notion in various combinatorial objects such as graph
decompositions, designs or packings is that of resolvability.
All of these objects partition the edges of a graph into specified
subgraphs called blocks. A resolution class is
a set of blocks which partition the point set, and
we say an object is {\em resolvable} if the set of blocks itself
may be partitioned into parallel classes. In fact, it may be possible
to partition the block set in different ways so as to obtain two
different resolutions. Two resolutions are considered orthogonal
if each pair of parallel classes intersect in at most one block.
We provide an introduction to this area and consider some recent
work, including some interesting generalisations.
--------------------------------------------------------------------
Pu Gao, University of Toronto
Title: Random graphs: spanning tree packing, arboricity, the
densest subgraph problem and beyond
I will focus on three problems in random graph theory: the spanning
tree packing (STP) number, the arboricity and the densest subgraph
of a (random) graph $G$.
These three seemingly unrelated problems have close connections
due to a classical theorem by Nash-Williams. Consider $G$ as a
binomial random graph $G(n,p)$. We determine the spanning tree
packing number of $G(n,p)$ for any $p=p(n)\in [0,1]$, where Nash-William's
theorem serves as a main ingredient in the proof. I will explain
how this result can be used to determine the arboricity of $G(n,p)$.
In the second part of this talk,
I will relate the graph arboricity to the densest subgraph problem
and graph orientability using Nash-Williams' theorem and a classical
result by Hakimi. The orientability of random graphs has been
extensively studied due to its application to a certain version
of load balancing. I will briefly survey research in this area
and show how our result on the arboricity of $G(n,p)$ closes a
gap in the orientability problem (and thereby the load balancing
problem). To end the talk, I will present some new results relating
to the densest subgraph problem together with some open problems
in this direction.
This contains joint work with Nick Wormald and with Xavier
P\'{e}rez-Gim\'{e}nez and Cristiane Sato.
--------------------------------------------------------------------
Luke Postle, Emory University
Title: On the minimum density of 4-critical graphs of girth five
Resolving a conjecture of Gallai, Kostochka and Yancey recently
proved that the minimum density of k-critical graphs is k/2 -
1/(k-1). Their bounds are tight given Ore's construction. Their
proof uses a new technique which allows reducible configuration/discharging
proofs to be applied to k-critical graphs. For k=4, their result
says that if G is a 4-critical graph, then |E(G)| >= (5|V(G)|-2)/3,
which in turn gives a short proof of Grotzsch's Theorem that every
triangle-free planar graph is 3-colorable.
In this talk, I will present some new results which improve their
bound for some classes of graphs. In particular, I will discuss
the following result: If G is a 4-critical graph of girth five,
then $|E(G)| \geq ((5+epsilon)|V(G)|-2)/3$ for some epsilon >
0. As a corollary, every 4-critical of girth five embedded in
a surface of genus g has at most O(g) vertices, which is a deep
result of Dvorak, Kral, and Thomas that in turn improved Thomassen's
earlier breakthrough result that there are only finitely many
such graphs on a given surface.
--------------------------------------------------------------------
Ivelisse Rubio, University of Puerto Rico, Río Piedras
Title: Construction of systems of polynomial equations with exact
p-divisibility via the covering method
We present an elementary method to compute the exact $p$-divisibility
of exponential sums of systems of polynomial equations over the
prime field. The method provides a framework that allows us to
unify and improve previously known results, and to provide a way
to construct families of systems of polynomial equations that
are solvable over the prime field. In the case of $p=2$ the results
are applied to non-balanced Boolean functions and the $2$-divisibility
of Hamming weights of deformed Boolean functions.
--------------------------------------------------------------------
Adrian Vetta, McGill University
Tittle: "A discrete view of economics."
Traditionally, most questions in economics have been analysed
using non-atomic scales. On the other hand, many economic concepts
such as equilibria in games or markets are fundamentally combinatorial
in nature. I will present two applications, concerning market
equilibria and industrial organisation, where taking a discrete
outlook can be illuminating.
--------------------------------------------------------------------
Mufutau Akinwande
Title: Correlation of pseudorandom sequences obtained from
de Bruijn graphs
Pseudorandom sequences with good correlation properties play
an important role in many secure communication systems. In this
talk, we will describe and illustrate sets of pseudorandom sequences
obtained recursively from de Bruijn graphs which have good correlation
functions and critically analyze how we investigate all homomorphisms
that give low correlation values between binary sequences. We
compute their correlation functions, which for certain nontrivial
homomorphisms turn out to be asymptotically within a factor of
2.5 of the Welch bound.
--------------------------------------------------------------------
Malihe Aliasgari, Amirkabir University of Technology
Title: $\mathbb{Z}$-module associated to integer programming for
decoding $q$-ary codes
By using a relation between binomial ideals and submodules of
$\mathbb{Z}^n$, we define a submodule associated with the integer
programming problem. By computing the reduced Gr\"obner basis
of the submodule, we consider the decoding problem of non-binary
$q$-ary codes as an integer program problem. Also, a hard-decision
decoding for a binary code via integer programming and Gr\"obner
basis is presented. We use the Conti et al. algorithm for decoding
$q$-ary codes. Since there is a correspondence between pure saturated
binomial ideals of $K[x_1,\ldots,x_n]$ and $\mathbb{Z}^n$-modules,
we consider the constraints of the integer programming problem
$\mbox{IP}_{H,\textbf{w},q}(\textbf{s})$ as a submodule of $\mathbb{Z}^{m+n}$
instead of a binomial ideal and show how to decode non-binary
$q$-ary codes with the $G$-norm.
Joint work with Mohammad-Reza Sadeghi.
--------------------------------------------------------------------
Amin Bahmanian, University of Ottawa
Title: Eulerian Hypergraphs
The paper written by Euler on the Seven Bridges of K\"onigsberg
(1736) is regarded as the first paper in the history of graph
theory. Given a connected graph $\mathcal G$, is it possible to
construct a ``path" starting and ending on the same vertex
which visits each edge exactly once? It is easy to see that $\mathcal
G$ posses such a path, called an Eulerian tour, if and only if
each vertex of $\mathcal G$ is of even degree. Surprisingly, very
little is known about an analogue to this notion for hypergraphs.
We extend the notion of Eulerian tours to hypergraphs and study
the existence of such tours.
Joint work with Mateja Sajna.
--------------------------------------------------------------------
Jacob Chodoriwsky and Lucia Moura, University of Ottawa
Title: An adaptive algorithm for group testing for complexes
In some testing problems, the property of being positive is not
defined on single items but on subsets of items, yielding the
so-called complex group testing. Given a set $N$ of $n$ items
with at most $d$ positive subsets of $N$, each positive subset
having cardinality at most $r$, we need to determine the set $P
\subset{\cal{P}}(N)$ of positive subsets via group tests. In this
talk, we will discuss an adaptive algorithm for group testing
for the complex model, for all $r\geq 2$, which can be seen as
a generalization of the binary splitting method for classical
group testing ($r=1$). For fixed $r$, our algorithm solves the
problem with $O(d^r \log n)$ tests.
--------------------------------------------------------------------
Shonda Gosselin, University of Winnipeg
Title: Metric Dimension of circulant graphs and Cayley hypergraphs
A hypergraph is a generalization of a graph, where an edge can
connect any number of vertices. The edge set $E$ of a hypergraph
$H$ is any set of nonempty subsets of $V(H)$, while in a graph
the cardinality of an edge is required to be at most 2. A pair
of vertices $x$ and $y$ in a graph (or hypergraph) $G$ are said
to be resolved by a vertex $w$ if the distance from $x$ to $w$
is not equal to the distance from $y$ to $w$. We say that $G$
is resolved by a set of vertices $W$ if every pair of vertices
in $G$ is resolved by some vertex in $W$. The minimum cardinality
of a resolving set for $G$ is the metric dimension of $G$. In
this talk, we bound the metric dimension of Cayley hypergraphs
on finite Abelian groups with the canonical set of generators,
and we show that the metric dimension of these hypergraphs is
related to the metric dimension of a Cartesian product of circulant
graphs. We also present some new results on the metric dimension
of circulant graphs.
Joint work with my student Adam Borchert.s
--------------------------------------------------------------------
Elizabeth Maltais, University of Ottawa
Title: Bounds for graph-intersecting packings
We give bounds for collections of partitions, or more generally
for collections of packings, whose classes intersect according
to the edges of a graph. Bollob\'as (1965) gave a bound on two
families of subsets having certain intersection properties; his
inequality can be viewed as a special case of our bounds for graph-intersecting
collections of packings, using the complete graph $K_2$. We also
apply our method to obtain new upper bounds on the number of columns
in a covering array with a fixed number of rows and alphabet with
$v \geq 3$ symbols.
Joint work with Lucia Moura and Mike Newman.
--------------------------------------------------------------------
Tony Nixon, York University
Title: Symmetry adapted Assur graphs
A realisation of a graph is a geometric embedding in $d$-space.
Such a realisation is rigid if the only edge-length preserving
motions are isometries of $d$-space. Moreover the realisation
is isostatic if deleting any single edge produces a realisation
in which there is a non-trivial motion.
For generic realisations of a pinned graph $G$, a $d$-Assur decomposition
is a decomposition of $G$ into minimal isostatic components (Assur
graphs). This decomposition is equivalent to the strongly connected
component decomposition of a natural $d$-orientation of $G$ and
to a block decomposition of the pinned rigidity matrix. Assur
graphs are a tool originally developed by mechanical engineers
to decompose mechanisms.
In this talk I will describe how these techniques extend to symmetric
mechanisms via symmetric graphs and their symmetry forced rigidity.
For a symmetry group $S$, the key tools to study such graphs are
the quotient $S$-gain graph and the orbit rigidity matrix. In
particular I will show the equivalence of minimal $S$-isostatic
components, strongly connected components of the $S$-gain graph
and indecomposable blocks in the orbit rigidity matrix.
Joint work with Bernd Schulze, Adnan Sljoka and Walter Whiteley.
--------------------------------------------------------------------
Antoine Poirier, University of Ottawa
Title: Graph contraction reconstruction
We will talk about one variant of the reconstruction conjecture,
which asserts that every simple graphs on 3 or more vertices
can be determined by its collection of vertex-deleted subgraphs.
We will go over some basic results, and talk about other types
of reconstruction, with a focus on contraction reconstruction.
In
particular, we will show that some disconnected graphs and
separable graphs can be determined by its collection of edge
contraction graphs.
--------------------------------------------------------------------
Christino Tamon, Department of Computer Science, Clarkson University
Title: Universal state transfer on graphs
A quantum walk on a graph $G$ is described by the unitary matrix
$U(t)= \exp(-itA)$, where $A$ is the adjacency matrix of $G$.
We say
$G$ has ``pretty good state transfer'' between vertices $a$ and
$b$
if for any $e>0$, there is a time $t$, where $|U(t)[a,b]| \leq
1-e$.
This notion was introduced by Godsil (2011). The state transfer
is
perfect if the above holds for $e=0$. In this work, we study a
natural
extension of this notion called ``universal'' state transfer where
we require state transfer to occur between every pair of vertices.
We prove the following results:
\begin{enumerate}
\item Graphs with universal state transfer have distinct eigenvalues
and flat eigenbasis (where each eigenvector has entries which
are equal
in magnitude).
\item The switching automorphism group of a graph with universal
state
transfer is abelian and its order divides the size of the graph.
Moreover,
if the state transfer is perfect, then the switching automorphism
group
is cyclic.
\item There is a family of prime-length cycles with complex weights
which has universal pretty good state transfer.
\item There exists a class of graphs with real symmetric adjacency
matrices which has universal pretty good state transfer. In contrast,
Kay (2011) proved that no graph with real-valued adjacency matrix
has
universal perfect state transfer.
\end{enumerate}
Keywords: quantum walk, state transfer, circulants.
This is based on joint work with S. Cameron, S. Fehrenbach, L.
Granger,
O. Hennigh and S. Shrestha.
--------------------------------------------------------------------
Georgios Tzanakis, Carleton University
Title: Construction of covering arrays of strength 4 from m-sequences
Let $q$ be a prime power and $F_q$ the finite field of $q$ elements.
A \emph{$q$-ary m-sequence} is a linear recurrence sequence of
elements
from $F_q$, with the maximum possible period. A \emph{covering
array}
$CA(N; t, k, v)$ is a $N\times k$ array with entries from an alphabet
of size $v$, with the property that any $N \times t$ sub-array
has at
least one row equal to every possible $t$-tuple. It is desirable
to
have covering arrays with the smallest possible $N$, for given
$t,k$,
and $v$. In 2013, Moura, Raaphorst and Stevens gave a construction
for covering arrays of strength $3$ using m-sequences, which are
the
best known for certain parameters. We are working on extending
this
construction to strengths larger than $3$. We have developed a
backtracking algorithm that yields covering arrays of strength
$4$.
For certain parameters, these are either the best, or close to
being
the best known. Furthermore, we have identified regularities in
our
findings and connections with finite geometry that we are currently
trying to exploit. In this talk we present the current state of
our
research.
Joint work with Lucia Moura and Daniel Panario.
--------------------------------------------------------------------
Eugene Zima, Wilfrid Laurier University
Title: Direct approach to the indefinite hypergeometric summation
In algorithms for hypergeometric indefinite summation, the so
called
dispersion of the rational certificate of the hypergeometric term
plays crucial role. The dispersion can be exponentially large
in the
size of the summand, and the running time of Gosper indefinite
summation algorithm effectively depends on the dispersion. This
means
that even when the closed form sum is small, the intermediate
results
and the running time can be exponentially large. In this talk
we will
discuss several approaches to reduction of non-essential
dependency of
the running time of Gosper algorithm on the value of dispersion
of the
summand. These approaches are implemented in Maple and show practical
improvement to the standard indefinite summation implementation.
--------------------------------------------------------------------
Top
