Schedule for: 22w5107 - Cross-community collaborations in combinatorics

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

In the 1960's, Erdős and Gallai conjectured that the edges of any n-vertex graph can be decomposed into $O(n)$ cycles and edges. In 2014, Conlon, Fox and Sudakov made the first general progress on this by showing an n-vertex graph can always be decomposed into $O(n \log\log n)$ cycles and edges. I will discuss how to improve the $\log\log n$ in this bound to the iterated logarithm function, and the tools and methods involved. This is joint work with Matija Bucić

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!

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

I'll introduce some objects, concepts, and questions from statistical physics, then explain how one can look at problems in extremal and enumerative combinatorics from this perspective. I'll describe methods from statistical physics for enumerating independent sets in graphs and how these can be combined with combinatorial tools like graph containers.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

The burning number $b(G)$ of the graph $G$ is the minimum $k$ such that $V(G)$ can be covered by vertex sets of subgraphs $G_1, \ldots, G_k$ such that $G_i$ has radius at most $i-1$. The burning number conjecture of Bonato, Janssen and Roshanbin states that $b(G) \leq \lceil \sqrt{n} \rceil$ for any connected $n$ vertex graph. We will show that $b(G) \leq(1+o(1)) \sqrt{n}$ by considering continuous and fractional variants of the problem.

The Erd\H{o}s-R\'enyi random graph $G(n,d/n)$ and the random $d$-regular graph both model graphs with average degree $d$. In 2013, building on more than sixty years of results, Coja-Oghlan et al.~showed that for large values of $d$, a.a.s.~the chromatic number of these graphs is concentrated on a single value. In the spirit of the workshop, we try applying the diverse set of tools developed to answer this question to a new problem. The oriented chromatic number of a graph, introduced by Courcelle in 1989, is the size of the smallest tournament to which an oriented graph has a homomorphism. In joint work with Karen Gunderson, we bound the oriented chromatic number of directed Erd\H{o}s-R\'enyi and $d$-regular models. Our results indicate the directed problem presents unique and interesting challenges that are worthy of further study.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A central problem in extremal graph theory is to study degree conditions that force a graph G to contain a copy of some large or even spanning graph F. One of the most classical results in this area is Dirac's theorem on Hamilton cycles. An extension of this theorem is the Posa-Seymour conjecture on powers of Hamilton cycles, which has been proved for large graphs by Komlos, Sarkozy and Szemeredi. Extension of these results to hypergraphs, using codegree conditions and tight (powers of) cycles, have been studied by various authors. We give an overview of the known results, and then show a codegree condition which is sufficient for ensuring arbitrary powers of tight Hamilton cycles, for any uniformity. This could be seen as an approximate hypergraph version of the Posa-Seymour conjecture. On the way to our result, we show that the same codegree conditions are sufficient for finding a copy of every spanning hypergraph of bounded tree-width which admits a tree decomposition where every vertex is in a bounded number of bags. This is joint work with Nicolas Sanhueza-Matamala and Matias Pavez-Signe.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

An interesting question in the spectral graph theory is about the structure of the eigenvectors of matrices associated with graphs. A graph is \textit{weakly Hadamard diagonalizable (WHD)} if its Laplacian matrix $L$ can be diagonalized with a weakly Hadamard matrix. In other words, if $L = PDP^{-1}$, where $D$ is a diagonal matrix and P has the property that all entries in $P$ are from $\{ 0,-1,1 \}$ and that $P^{t}P$ is a tridiagonal matrix. In this talk, I will present some necessary and sufficient conditions for a graph to be WHD. Also some families of graphs which are WHD, will be presented.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

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.