# Schedule for: 24w5204 - Cross-Community Collaborations in Combinatorics

Beginning on Sunday, June 23 and ending Friday June 28, 2024

All times in Banff, Alberta time, MDT (UTC-6).

Sunday, June 23 | |
---|---|

16:00 - 17:30 | Check-in begins at 16:00 on Sunday and is open 24 hours (Front Desk - Professional Development Centre) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building. (Vistas Dining Room) |

20:00 - 22:00 | Informal gathering (TCPL Foyer) |

Monday, June 24 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

08:45 - 09:00 |
Introduction and Welcome by BIRS Staff ↓ A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions. (TCPL 202) |

09:00 - 10:00 | Open problem session (TCPL 202) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 12:00 | Open problem session (TCPL 202) |

12:00 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

13:00 - 14:00 |
Shagnik Das: Explicit constructions of strong blocking sets and minimal codes ↓ A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. In this talk we present a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the $(k−1)$-dimensional projective space over $\mathbb{F}_q$ that have size $O(qk)$. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of $\mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$, for every prime power $q$, for which $n=O(qk)$.
This is joint work with Noga Alon, Anurag Bishnoi and Alessandro Neri. (TCPL 202) |

14:00 - 14:20 |
Group Photo ↓ Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo! (TCPL Foyer) |

14:20 - 15:00 | Open problem session (Online) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 18:00 | Open problem session/group work (TCPL 202) |

18:00 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building. (Vistas Dining Room) |

Tuesday, June 25 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

09:00 - 10:00 |
Asaf Ferber: Quantum algorithms on graphs ↓ In this talk I'll give a short introduction to quantum computation and will illustrate how to utilize it in order to speed up some classical graph algorithms. In particular, we will present an asymptotically tight result for learning a Hamilton cycle using OR querries, and obtain a polynomial improvement for the best known (Delta+1)-coloring graph quantum algorithm for coloring a graph with maximum degree Delta.
This is based on joint works with Liam Hardiman (UCI), and with Xiaonan Chen (UCI) and Liam Hardiman. (TCPL 202) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 12:00 | Group work (Other (See Description)) |

12:00 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

13:00 - 13:30 |
Amedeo Sgueglia: Tight Hamilton cycles with high discrepancy ↓ In discrepancy-type problems in graphs, the question is whether for a given host graph, any r-colouring of its edges must contain a specified subgraph "with high discrepancy", meaning that within this subgraph one of the colour classes is significantly larger than each of the other ones. We initiate the study of such questions for hypergraphs. Our main result is a discrepancy version of the celebrated theorem of R\"odl, Ruci\'nski and Szemer\'edi on tight Hamilton cycles in Dirac hypergraphs.
Joint work with Lior Gishboliner and Stefan Glock. (TCPL 202) |

13:30 - 14:00 |
Anna Gujgiczer: Hedetniemi's conjecture: What is left? ↓ Hedetniemi conjectured in 1966, that $\chi (G\times H) = \min\{\chi (G), \chi (H)\}$ is true for every graphs $G$ and $H$. This conjecture was refuted in 2019, but still, a lot of open questions remained. We can reformulate the conjecture in multiple ways, for example with the function $f(n) = min\{\chi(G\times H)\ |\ \chi(G)=\chi(H)=n\}$ the reformulation is that $f(n) = n$ for all $n$. Due to the counterexamples, we know that $f(n) < n$ for big enough $n$, but it is still not known if this function is bounded or not. Another possible reformulation is to say that all complete graphs are multiplicative, meaning that $G \times H \to K_n$ implies $G \to K_n$ or $H \to K_n$ for every graph pair $G$ and $H$ (where $\to$ denotes the existence of graph homomorphism). It is an interesting question in general to determine which graphs are multiplicative and which are not.
In this talk we will summarize what is known so far and what are the interesting open questions in this area. (TCPL 202) |

14:00 - 15:00 | Group work (Other (See Description)) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 17:00 | Group work (Other (See Description)) |

17:00 - 18:00 | Progress reports (Other (See Description)) |

17:30 - 19:30 |
Dinner ↓ A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building. (Vistas Dining Room) |

Wednesday, June 26 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

09:00 - 10:00 |
Sophie Spirkl: Induced subgraphs and treewidth ↓ Treewidth is a graph parameter which is useful both for structure and for algorithms. Robertson and Seymour showed which graph minors and which subgraphs "cause" large treewidth. However, the question "Which induced subgraphs cause large treewidth?" is still wide open, and I'll you some pieces of the answer that have been found so far. (TCPL 202) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 12:00 | Group work (Other (See Description)) |

12:00 - 13:00 |
Lunch ↓ Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building. (Vistas Dining Room) |

13:00 - 17:00 | Free Afternoon (Banff National Park) |

17:30 - 19:30 |
Dinner ↓ |

Thursday, June 27 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ |

09:00 - 10:00 |
Bhargav Narayanan: Anticoncentration and Antichain Codes ↓ A basic problem at the intersection of probability and combinatorics is the Littlewood-Offord anti-concentration problem: given real numbers a_1, … , a_n, what is the largest possible point probability of the random sum a_1 X_1 + … + a_n X_n for iid Bernoulli random variables X_1, … , X_n? Several variants of this problem, involving additional arithmetic constraints on the numbers a_1, … , a_n, have proved to both be deep and widely applicable; two notable examples of such variants include the Sarkozy-Szemeredi theorem (resolving the Erdos-Moser problem) and Halasz's theorem. A few years ago, it became evident to me that all these arithmetic results are in fact specializations of a more abstract, purely combinatorial phenomenon. In this talk, I will take the scenic route to the recent proof (with Ben Gunby, Xiaoyu He and Sam Spiro) of such an abstract result, regarding the density of “antichain codes” in the Boolean hypercube, surveying the history of these problems and some of the many applications along the way. (TCPL 202) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 12:00 | Group work (Other (See Description)) |

12:00 - 13:00 |
Lunch ↓ |

13:00 - 15:00 | Group work (Other (See Description)) |

13:00 - 13:30 |
Aditya Potukuchi: Triangle-free graphs: Order and disorder ↓ The main focus of my talk is the following question:
{\em How does a typical triangle-free graph on $[n]$ with a $m$ edges ``look''?}
A starting point to is a seminal result of Osthus, Pr\"{o}mel, and Taraz, which sates that when $m > (1+o(1))\frac{\sqrt{3}}{4}n^{3/2}$, then a typical triangle-free graph is bipartite. I will present (to the best of my knowledge) our current state of understanding of the answer to this question as $m$ gets smaller. I will particularly focus on the regime when $m = \Theta(n^{3/2})$, which sees a shift from `order' to `disorder’ (I will also attempt to justify the use of these words). I will describe various (typical) structural properties of the graphs and, more importantly, the heuristics and techniques used.
Joint work with Matthew Jenssen, Will Perkins, and Michael Simkin (TCPL 202) |

13:30 - 14:00 |
Stacie Baumann: A Proof of the $(n,k,t)$ Conjectures ↓ An \emph{$(n,k,t)$- graph} is a graph on $n$ vertices in which every
set of $k$ vertices contain a clique on $t$ vertices. Tur\'an's Theorem (complemented) states that the unique minimum $(n,k,2)$-graph is a disjoint union of cliques. We prove that minimum $(n,k,t)$-graphs are always disjoint unions of cliques for any $t$ (despite nonuniqueness of extremal examples), thereby generalizing Tur\'an's Theorem and confirming two conjectures of Hoffman et al. This is joint work with Joseph Briggs. (TCPL 202) |

14:00 - 15:00 | Group work (Other (See Description)) |

15:00 - 15:30 | Coffee Break (TCPL Foyer) |

15:30 - 17:30 | Group work (Other (See Description)) |

17:30 - 19:30 |
Dinner ↓ |

Friday, June 28 | |
---|---|

07:00 - 08:45 |
Breakfast ↓ |

09:00 - 10:00 |
Julia Böttcher: Graph universality ↓ Given a class $G$ of $n$-vertex graphs, how can we construct a host graph $H$ that contains them all as subgraphs? Graphs $H$ with this property are called universal for $G$, and the question gets interesting when we put certain restrictions on $H$. For example, we might be interested in a graph $H$ with as few edges as possible, or a graph $H$ which has only $n$ vertices itself and still only few edges. Or we might ask when certain random graphs are universal for $G$. This all leads to a variety of interesting and challenging problems. In the talk, I will explain what is known and what is open for some classes of graphs $G$. I will also detail some techniques that I recently used with my co-authors Peter Allen and Anita Liebenau for progress when $G$ consists of all $D$-degenerate graphs for a fixed $D$. (TCPL 202) |

10:00 - 10:30 | Coffee Break (TCPL Foyer) |

10:30 - 12:00 | Wrap up and progress (Other (See Description)) |

10:30 - 11:00 |
Checkout by 11AM ↓ 5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM. (Front Desk - Professional Development Centre) |

12:00 - 13:30 | Lunch from 11:30 to 13:30 (Vistas Dining Room) |