# Seminars & Events for Discrete Mathematics Seminar

##### Stability results in graphs of given circumference

In this talk we will discuss some Turan-type results on graphs with a given circumference. Let W_{n,k,c} be the graph obtained from a clique K_{c-k+1} by adding n-(c-k+1) isolated vertices each joined to the same k vertices of the clique, and let f(n,k,c)=e(W_{n,k,c}). Improving the Erdos-Gallai theorem, Kopylov proved in 1977 that for c<n, any 2-connected graph G on n vertices with circumference c has at most max (f(n,2,c),f(n,[c/2],c)) edges, with equality if and only if G equals W_{n,2,c} or W_{n,[c/2],c}. Recently, Furedi et al. obtained a stability version of Kopylov's theorem.

##### Rainbow matchings.

Given a family F_1,...,F_m of sets of edges in a graph or hypergraph, a ``rainbow matching'' is a choice of disjoint edges

e_1 in F_1,..., e_m in F_m. The talk is on open problems regarding this notion, some old and some new results, and what topology has to contribute to the subject.

##### Ranks of matrices with few distinct entries

Many applications of linear algebra method to combinatorics rely on the bounds on ranks of matrices with few distinct entries and constant diagonal. In this talk, I will explain some of these application. I will also present a classification of sets L for which no low-rank matrix with entries in L exists.

##### Packing the discrete torus

Let H be an induced subgraph of the toroidal grid Z_k^m and suppose that

| V(H)| divides some power of k. We show that if k is even then (for

large m) the torus has a perfect vertex-packing with induced copies of H.

This extends a result of Gruslys. On the other hand, when k is odd and not a prime power, we disprove a conjecture of Gruslys: we show that there are choices of H such that there is no m for which Z_k^m has a perfect vertex-packing with copies of H.

We also discuss edge-packings, and disprove a conjecture of Gruslys, Leader and Tan by exhibiting a graph H such that H embeds in a hypercube, but no hypercube has a perfect edge-packing with copies of H.

Joint work with Marthe Bonamy and Natasha Morrison.

Next week: Greta Panova

##### Packing the discrete torus

Let H be an induced subgraph of the toroidal grid Z_k^m and suppose that

|V(H)| divides some power of k. We show that if k is even then (for

large m) the torus has a perfect vertex-packing with induced copies of H.

This extends a result of Gruslys. On the other hand, when k is odd and not a prime power, we disprove a conjecture of Gruslys: we show that there are choices of H such that there is no m for which Z_k^m has a perfect vertex-packing with copies of H.

We also discuss edge-packings, and disprove a conjecture of Gruslys, Leader and Tan by exhibiting a graph H such that H embeds in a hypercube, but no hypercube has a perfect edge-packing with copies of H.

Joint work with Marthe Bonamy and Natasha Morrison.

##### Hook formulas for counting skew Standard Young Tableaux with applications

Enumeration of linear extensions (total orderings) of partially ordered sets (posets) is a classical topic in discrete mathematics. In the case of Young diagrams, these linear extensions are the Standard Young Tableaux, which give bases for the irreducible representations of the symmetric group, and are the favorite objects in algebraic combinatorics, with applications from statistical mechanics to algebraic geometry.

##### Graph searches on structured families of graphs

Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. Some families of graphs have a vertex ordering characterization, and we review how graph searching is used to produce such vertex orderings . These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance).

In this talk, we focus on two graph searches: Lexicographic breadth first search (LexBFS), and Lexicographic depth first search (LexDFS).