SCIENTIFIC PROGRAMS AND ACTIVITIES

September 22, 2019
THE FIELDS INSTITUTE FOR RESEARCH IN MATHEMATICAL SCIENCES
May 1-2, 2014

Ottawa-Carleton Discrete Mathematics Daysto be held at Carleton University, Room HP4351(map)SPEAKER ABSTRACTS

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.

--------------------------------------------------------------------

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.

--------------------------------------------------------------------

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

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