Speaker: Trung Chau (UM)
Title: Multiplicity of negative one of independence polynomials of graphs
Time: 2:30pm
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/63619782230 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: We will discuss a small study of the multiplicity of negative one of independence polynomials of graphs. In commutative algebra, this invariant equals the a-invariant of the corresponding edge ideals. In graph theory, this invariant has not been studied as a topic on its own, but much work has been done on whether this invariant is equal to or larger than zero, as this is related to the reduced Euler characteristic of the independence complex of a graph. This is joint work with Om Prakash Bradwaj, Sayeed Ikram, Gargi Lather, Vasudeva Nanjangud, and Chitra Venugopal.
Speaker: Sophie Spirkl (Waterloo)
Title: Cliques and colouring in tournaments
Time: 2:30pm
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/63619782230 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: Tournaments are orientations of complete graphs, and many graph theory questions — in particular, from the world of induced subgraphs — have analogues in tournaments. In particular, notions of colouring (due to Neumann-Lara) and clique number (Aboulker, Aubian, Charbit, Lopes) exist. I will tell you what these are, as well as some of what we know about them, and questions that remain.
Speaker: Sean Longbrake (Emory University)
Title: An extremal result for powers of trees
Time: 2:30pm
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/63619782230 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: Given a graph $H$, the extremal number $\ex(n,H)$ is the maximum number of edges in an $n$-vertex
graph not containing $H$ as a subgraph. For nonbipartite graphs, this function is well-understood, but for bipartite graphs, little is known in the general case.
One motivating conjecture in the field is the following of Bukh and Conlon. Let $T^p$ be the graph formed by taking $p$ copies of $T$ which agree on their leaf set and are otherwise disjoint. Let $\ell(T)$ be the number of leaves of $T$. For certain so-called balanced trees T, Bukh and Conlon conjectured $\ex(n, T^p) = O(n^{2 - (v(T) - \ell(T))/e(T)})$.
Conlon and Janzer proved this theorem for the height two-tree $F_{r, s}$ formed by taking an $K_{1, r}$ and adding to leaf $s$ new neighbors, as long as $r \geq s + 2$. In joint work with Jiang and Yepremyan, we proved the Bukh and Conlon conjecture for the subdivision of $F_{r, s}$, formed by replacing each edge of $F_{r, s}$ with a path with two edges, as long as $r \geq 2s + 3$.
In this talk, I will give some background on this problem and its origins, as well as give some intuition on the structure of the proof.
Speaker: Tatsuhiro Suga (Tohoku University)
Title: On the Complexity of Independent Set and Vertex Cover Reconfiguration under Extended Adjacency of Solutions
Time: 2:30pm
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/63619782230 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: In a reconfiguration problem on graphs, we are given two feasible solutions to a graph problem. We are then asked whether one solution can be transformed into the other through a sequence of feasible intermediate solutions under a prescribed reconfiguration rule, which defines when two solutions are adjacent. Traditionally, such problems have been studied under rules that change at most one element at a time. These rules are natural, and they keep each operation simple. In some settings, however, they can be too restrictive, because more flexible operations, such as changing several elements simultaneously, may be permitted. Motivated by this, we study the reconfiguration of independent sets and vertex covers under a rule that allows up to k vertices to be replaced at once.
In this talk, we will show how the value of k and the class of input graphs affect the computational complexity of these problems. Depending on these parameters, the problems range from polynomial-time solvable to NP-complete or PSPACE-complete.
This is joint work with Shuichi Hirahara, Naoto Ohsaka, Akira Suzuki, Yuma Tamura, and Xiao Zhou.
Speaker: Jimmy Zhu (UM CS)
Title: Coin-flipping games
Time: 2:30pm
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/63619782230 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: Consider a game with n players, f < n/2 of which may be "bad". In each round t, the bad players have an outcome f(t) they wish to force; they flip "adversarial" coins while the good players flip fair coins. The game continues to another round if the majority coin flip is f(t). How long does it take to detect a bad player, with high probability?
Speakers: Lila Crew and Xinyue Fan (Waterloo)
Title: Large Clique Number in Tournaments
Time: 2:30pm
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/63619782230 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: A tournament is an oriented complete graph; these structures show up frequently in voting theory and biology. There is a notion of clique number for a tournament T: the largest k such that for every total ordering of V(T), there is an order-agreeing transitive subtournament of size k. Unlike in graphs, it is not immediately clear that tournaments can have large clique number, much less that clique number is dependent on specific substructures. In this talk, we prove that there are two infinite families of tournaments (A_n and D_n) such that if a tournament T is (A_k,D_k)-free for any k, then T has bounded clique number. The proof synthesizes a number of classical and recently-developed techniques in the area, so we take the opportunity to highlight these ideas for the audience to give insight into the style of arguments commonly used in current research. This is joint work with Hidde Koerts, Ben Moore, and Sophie Spirkl.
Speaker: Colin Desmarais (TU Wien)
Title: TBA
Time: 2:30pm
Room: 225 St Paul's College
Zoom link: https://umanitoba.zoom.us/j/63619782230 password the first 6 Fibonacci numbers (starting with 11...)
Abstract: TBA