• home

Abstract: Given a matching M of a hypercube, does there exist a Hamiltonian cycle that contains every edge of M? This problem was posed by Ruskey and Savage in 1993, and remains open. If M is a perfect matching a Hamiltonian cycle does exist, as shown by Fink in 2007. In this talk, we will explore Fink's proof and examine some subsequent developments in the study of this problem.

Abstract:
A sequence of tournaments is said to be quasirandom if it behaves as a sequence of random tournaments would. In 1991, Chung, Graham, and Wilson provided a list of equivalent properties that any sequence of random tournaments satisfies with high probability. We say that a tournament H forces quasirandomness if every sequence that asymptotically has the expected number of copies of H is quasirandom. Nevertheless, it was shown that almost only transitive tournaments are quasirandom forcing. We then modify the definition of quasirandom forcing by considering only sequences of nearly regular tournaments and characterize all tournaments on at most five vertices that force quasirandomness in this new setting.

Abstract: Algebraic graph theory begins by associating a matrix to a graph and asking how the eigenvalues of the former relate to the structure of the latter. In the past fifteen or so years, horizons have broadened to include variants of graphs (such as signed graphs or directed graphs) which require variants of adjacency matrices such as signed or Hermitian adjacency matrices. I will focus on the topic of characterizing the graphs whose associated matrices have at most three distinct eigenvalues. I will discuss old results in the undirected and signed graph case and then present some new results for oriented graphs.

Based on joint work with S. Akbari, J. Aloni, B. Mohar and S. Xia.

Abstract: The peaceable queens problem asks to determine the maximum number $a(n)$ such that there is a placement of $a(n)$ white queens and $a(n)$ black queens on an $n \times n$ chessboard so that no queen can capture any queen of the opposite color.

We consider the peaceable queens problem and its variant on the toroidal board. For the regular board, we show that $a(n) \leq 0.1716n^2$, for all sufficiently large $n$. This improves on the bound $a(n) \leq 0.25n^2$ of van Bommel and MacEachern.

For the toroidal board, we provide new upper and lower bounds. Somewhat surprisingly, our bounds show that there is a sharp contrast in behaviour between the odd torus and the even torus. Our lower bounds are given by explicit constructions. For the upper bounds, we formulate the problem as a non-linear optimization problem with at most 100 variables, regardless of the size of the board. We solve our non-linear program exactly using modern optimization software.

We also provide a local search algorithm and a software implementation which converges very rapidly to solutions which appear optimal. Our algorithm is sufficiently robust that it works on both the regular and toroidal boards. For example, for the regular board, the algorithm quickly finds the so-called Ainley construction.

This is joint work with Katie Clinch, Matthew Drescher, and Abdallah Saffidine.

Abstract:
School timetabling is a complex problem in combinatorial optimization, requiring the best possible assignment of course sections to teachers, timeslots, and classrooms.

For educational institutions, the Master Timetable dictates to every single teacher and student where they need to be at each hour of the school day. Given its importance, school administrators spend weeks or months constructing the annual Master Timetable, often using Post-it notes or wall magnets to assign a teacher, classroom, and timeslot to each section of a course.

When timetables are constructed by hand, the process is often 10% mathematics and 90% politics, leading to errors, inefficiencies, and resentment among teachers and students.

To address these concerns, a field of Discrete Mathematics known as "automated timetabling" has emerged, to create mathematically-optimal timetables for schools.

Over the past five years, I have had the privilege of creating over 50 Master Timetables for various high schools across Canada, including all three of Victoria's independent schools. In this informal interactive talk, I will describe how I create these timetables by modelling the school's constraints as an Integer Linear Program.

Abstract: Combinatorial Configurations lay between block designs and hypergraphs. When these incidence structures can be embedded in the plane, we call them Geometric Configurations. In this talk, we will explore several results in the study of configurations, including an extension of Erdős and Kelly's result on the minimal regular graph containing a given graph, applied to linear hypergraphs.

Abstract: Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory of graph minors, fixed parameter complexity and combinatorial sparsity.

In this talk, we will survey structural and algorithmic results concerning width and depth parameters of matroids. We will view matroids as purely combinatorial objects and discuss their structural properties related to depth and width decompositions. As an algorithmic application, we will present matroid based algorithms that can uncover a hidden Dantzig-Wolfe-like structure of instances of integer programs (if such structure is present).

The most recent results presented in the talk are based on joint work with Marcin Briański, Jacob Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.

Abstract: A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of n points in the plane. Since then a great variety of extremal problems in finite planar point sets have been studied. In this talk, we examine several such problems, all of which have in common that they can be reduced to the study of the independence number of an auxiliary hypergraph.

1) What is the size of the largest subset of the n x n grid whose points determine distinct slopes?

2) What is the size of the largest monotone general position subset of the n x n grid?

3) Given n points in the plane, how many triangles can be approximate congruent to equilateral triangles?

The results presented are partially joint work with Balogh, Dumitrescu and Liu.

Abstract: In how many ways can an m x n chessboard be tiled using 2 x 1 tiles? The solution is given by the number of perfect matchings in a related graph. Although computationally difficult in general, in this circumstance we are able to efficiently count these matchings.

Originally shown by P.W Kastelyn in 1961, I shall present an adapted solution given by Jiří Matoušek in his book "Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra" published in 2010.

An (m, n)-mixed graph consists of a set of vertices, any two of which may be joined by either an edge of one of m colours or an arc of one of n colours, or not be joined at all. The operation of switching at a vertex v of an (m, n)-mixed graph with respect to an element of a subgroup \Gamma of S_m x S_n x S_2 permutes the colours of the edges incident with v, the colours of the arcs incident with v, and the orientation of the arcs incident with v. Switching defines an equivalence relation on the set of all (m, n)-mixed graphs: (m, n)-mixed graphs G and H are \Gamma-switch-equivalent if there exists a sequence of switches that transform G into H.

We consider the following problems and their solutions. For a fixed subgroup \Gamma of S_m x S_n x S_2:

* determine the number of equivalence classes of k vertex (m, n)-mixed graphs under switching with respect to \Gamma.
* how hard is it to determine whether to given (m, n)-mixed graphs G and H are \Gamma-switch equivalent?
* for a fixed (m, n)-mixed graph H, how hard is it to determine whether a given (m, n)-mixed graph G can be switched with respect to \Gamma so that there is a homomorphism of the transformed (m, n)-mixed graph G’ to H? (A homomorphism is a mapping of V(G) to V(H) that preserves edges, arcs and colours.)

Abstract: Many fundamental problems in extremal combinatorics can be expressed as inequalities in graph homomorphism densities. In this talk, I will introduce some new results on this topic. Our research involves Sidorenko's conjecture, Kohayakawa-Nagle-R{\"o}dl-Schacht conjecture and common graphs. Moreover, I will share some recent advancements in problems of homomorphism densities for tournaments.

Abstract: A classical question in extremal (hyper)graph theory asks for tight minimum degree conditions which force the existence of certain spanning structures in large graphs, generalising Dirac's theorem from 1952. One aspect of this concerns tiling graphs with identical vertex disjoint copies of a small subgraph. For example, asking for tight minimum codegree conditions in a k-uniform hypergraph which force a perfect matching (under the obvious additional necessary condition that the number of vertices is divisible by k). Whilst there has been a lot of interest in these types of tiling problem, still very few results are known. We share a new result in this area, which is joint work with Amarja Kathapurkar, Natasha Morrison and Richard Mycroft.

Abstract: In defining colouring of oriented graphs via homomorphism one finds an easily checkable necessary condition for a valid colouring — vertices at directed distance at most two must receive different colours. With this idea in mind we extend the definition of quasi-transitive digraph to mixed graphs. In this talk we explore a full characterisation of quasi-transitive mixed graphs of degree at most three and find that the general problem of deciding if a graph admits a mixed orientation as a quasi-transitive mixed graph is NP-complete.

Abstract: Let $G$ be a graph with $n$ vertices. Let $A(G)$ be its adjacency matrix. Let $\lambda_1(G), \lambda_2(G)$ denote the largest and second largest eigenvalues of the adjacency matrix. Bollob\'{a}s and Nikiforov (2007) conjectured that for any graph $G \neq K_n$ with $m$ edges \[\lambda_1^2+\lambda_2^2\le \bigg( 1-\frac{1}{\omega(G)}\bigg)2m,\] where $\omega(G)$ denotes the clique number of $G$. In this talk, we prove this conjecture for graphs with not so many triangles, using the method of triangle counting. This is a joint work with Hitesh Kumar.

Abstract: An edge mapping of a graph is a function f:E(G) -> E(G) where f(e) \neq e for all e in E(G). A subgraph H of G is called f-free if for every e in E(H) f(e) \notin E(H). A graph G is called unavoidable for a graph H if every edge mapping of G has at least one f-free copy of H and minimally unavoidable if no proper subgraph of G also satisfies this property. In this talk, we will discuss the set of all minimally unavoidable graphs for a graph H for several different types of graphs H.

ABSTRACT: A network of interacting qubits (usually subatomic particles) can be modelled by a connected weighted undirected graph $G$. The vertices and edges of $G$ represent the qubits and their interactions in the network, respectively. Quantum mechanics dictate that the evolution of the quantum system determined by $G$ over time is completely described by the unitary matrix $U(t)=\exp(itA)$, where $A$ is the adjacency matrix of $G$. Here, we interpret the modulus of the $(u,v)$ entry of $U(t)$ as the probability that the quantum state at vertex $u$ is found in $v$ at time $t$. In this talk, we discuss how the algebraic and spectral properties of a graph influence its ability to perform quantum state transfer.

Abstract: We show that \((n,d,\lambda)\)-graphs with \(\lambda=O(d/log^3n)\) are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007. The key new idea in our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Koml\'{o}s and Szemer\'{e}di, with further applications to the vertex disjoint paths problem. Joint work with Joseph Hyde, Alp M\"{u}yesser, and Matías Pavez-Signé.

Abstract: A combinatorial object is said to be quasirandom if it exhibits certain properties that are typically seen in a truly random object of the same kind. It is known that a permutation is quasirandom if and only if the pattern density of each of the twenty-four 4-point permutations is close to 1/24, which is its expected value in a random permutation. In other words, the set of all twenty-four 4-point permutations is quasirandom-forcing. Moreover, it is known that there exist sets of eight 4-point permutations that are also quasirandom-forcing. Breaking the barrier of linear dependency of perturbation gradients, we show that every quasirandom-forcing set of 4-point permutations must have cardinality at least five.

Abstract: A geometric graph $G$ is a graph $G$ whose vertices are drawn in the plane such that no three vertices are collinear, and each edge of G is a straight line segment. A geometric homomorphism from geometric graph $G$ to geometric graph $H$ is a homomorphism that preserves crossings. Similar to the regular chromatic number, the geochromatic number of a geometric graph $G$ is the smallest integer $n$ such that there is a geometric homomorphism from $G$ to a geometric clique $K_n$.

In this talk, we will particularly discuss the relation between chromatic numbers and geochromatic numbers. Even for a bipartite graph, its geochromatic number can be unbounded. However, if the graph is not too "dense", for example, every pair of crossing has distance at least $2$, then its geochromatic number is bounded by a constant.