Schedule for: 24w5204 - 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.

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.

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.

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.

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

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.

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.

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.

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.

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 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.

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

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

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.

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.

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$.

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.