• home

Abstract: For fixed n, consider the symmetric group S_n on the symbols 1,...,n and the set of *star* transpositions, the transpositions that contain the symbol n. A *star factorization* of a permutation b in S_n of length k is the writing of b as the product of k star transpositions. Goulden and Jackson (2009) showed that the number of such factorizations only depends on the conjugacy class of b and not on b itself, a remarkable fact given the special role the symbol n plays amongst star transpositions. We supply the first fully combinatorial proof of this fact that works for all lengths k, and our methods connect star factorizations to monotone factorizations. Star transpositions are connected to Jucys-Murphy elements, and we explain how our result can give expressions for the *transitive* image of certain symmetric functions evaluated at Jucys-Murphy elements.

This is joint work with Jesse Campion Loth (Heilbronn Institute and the University of Bristol).

The theory of combinatorial limits, which provides analytic tools to represent and study large discrete structures, resulted in new views on a wide range of topics in mathematics and computer science and also opened new connections between combinatorics and other areas of mathematics. In the talk, we will introduce basic concepts from the theory of combinatorial limits and apply its methods to several specific problems from extremal combinatorics and particularly from Ramsey theory.

Ramsey theory statements guarantee the existence of ordered substructures in large objects such as in the following classical statement proven by Ramsey in 1930: if N is sufficiently large, then for any partition of k-tuples of N points into finitely many classes, there exist n points such that all k-tuples formed by these n points belong to the same class. We will study quantitative versions of Ramsey type statements and present a solution of a 30-year-old problem on the existence of high chromatic graphs with small Ramsey multiplicity. In relation to general questions concerning the interplay of combinatorial limits and extremal combinatorics, we will present, among others, a counterexample to a conjecture of Lovász on finitely forcible optima of extremal combinatorics problems

In 2021, Mohar introduced the game of Cops and Robber on geodesic spaces. The game captures the behavior of the Cops and Robber game played on graphs and that of continuous pursuit-evasion games. Analogous to one of the main open problems for the Cops and Robber game on graphs, Mohar conjectured that the cop number of a geodesic surface of genus $g$ is at most $O(\sqrt{g})$. Surprisingly, this upper bound can be significantly improved on surfaces of constant curvature which will be the main focus of this talk.

             It turns out that the cop number of compact spherical and Euclidean surfaces is at most $2$. Even more surprisingly, the cop number of compact hyperbolic surfaces is also at most $2$, independently of their genus. We will also consider the strong cop number of these surfaces and present several generalizations to higher-dimensions.

Joint work with Bojan Mohar and Alexandra Wesolek.

Given two graphs H and G, the homomorphism density t(H,G) represents the likelihood that a random mapping from V(H) to V(G) is a homomorphism. Sidorenko Conjecture states that for any bipartite graph H, t(H,G) is greater or equal to t(K_2,G)^{e(H)}.

Introducing a binary relation H \geq T if and only if t(H,G)^{e(T)} \geq t(T,G)^{e(H)} for all graphs G, we establish a partial order on the set of non-empty connected graphs. Employing a technique by Kopparty and Rossman, which involves the use of entropy to define a linear program, we derive several necessary and sufficient conditions for two trees T, F satisfy T\geq F. Furthermore, we show how important results and open problems in extremal graph theory can be reframed using this binary relation.

Joint work with Natalie Behage, Gabriel Crudele, and Jonathan Noel.

Let X be a finite subset of \mathbb{Z}^d of cardinality at least 3. We say a subset of [n]^d is X-free if it does not contain a non-trivial scaled or translated copy of X. Let r_X(n) be the cardinality of the largest X-free subset of [n]^d. How big can r_X(n) be? The Multidimensional Szemerédi's Theorem of Furstenberg and Katznelson states that r_X(n) = o(n), though exact asymptotics are not known. A natural second question asks: how many X-free subsets of [n]^d are there? We show that for infinitely many n \in \mathbb{N}, the number of X-free subsets is 2^{O(r_X(n))}. This work generalizes previous work of Balogh, Liu, and Sharifzadeh, who considered when X is a k-term arithmetic progression, and Kim, who considered when X is a corner.

Abstract: Turán-type problems for hypergraphs have been an intriguing area of research. Despite significant efforts, the Turán density of F is known for only a few three-uniform hypergraphs F. This talk concerns Turán-type problems for 3-uniform tight cycles C_k, where the number of vertices k is not divisible by 3.

The Turán density of a hypergraph F is the maximum density of an n-vertex hypergraph that does not contain any member of F. Mubayi and Rödl gave an ``iterated blow-up'' construction showing that the Turán density of C_5 is at least 2sqrt{3}-3, and this bound is conjectured to be tight. Interestingly, their construction also excludes C_k for larger k not divisible by 3, indicating that it might be the extremal construction for these hypergraphs as well. Indeed, we have recently shown that the Turán density of C_k is 2sqrt{3}-3 for sufficiently large k, in a joint result with Shoham Letzter and Alexey Pokrovskiy.

Abstract: Given graphs $G$ and $H$ and a positive integer $q$, an $(H,q)$-coloring of $G$ is an edge-coloring in which each copy of $H$ receives at least $q$ colors. Erdős and Shelah raised the question of determining the minimum number of colors, $f(G,H,q)$, which are required for an $(H,q)$-coloring of $G$. Determining $f(K_n,K_p,2)$ for all $n$ and $p$ is equivalent to determining the classical multicolor Ramsey numbers. Recently, Mubayi and Joos introduced the use of a new method for proving upper bounds on these generalized Ramsey numbers; by finding a “conflict-free" matching in an appropriate auxiliary hypergraph, they determined the values of $f(K_{n,n},C_4,3)$ and $f(K_n,K_4,5)$. In this talk, we will show how to generalize their approach to give bounds on the generalized Ramsey numbers for several families of graphs. This is joint work with Deepak Bal, Patrick Bennett, and Shira Zerbib.

Abstract: In this talk we consider the oriented colouring problem for graphs with bounded Euler genus. That is we consider the smallest $k$ such that all oriented graphs embeddable on surfaces of Euler genus at most $g$ necessarily have an oriented homomorphism to a graph of order $k$. For convenience given a fixed $g$ and $k$, we let $\chi_o(g) = k$. We will discuss our proofs that $\Omega((\frac{g^2}{\log{g}})^{\frac{1}{3}}) \leq \chi_o(g) \leq (1+o(1))g^{6400}$, which improves the prior upper bound of order $2^{O(g^{\frac{1}{2}+o(1)})}$ and lower bound of order $\Omega(\sqrt{g})$, as well as exploring how our bounds might be improved in future work.

Joint work with Peter Bradshaw (University of Illinois Urbana Champaign), and Jingwei Xu (University of Illinois Urbana Champaign).

In Graph Theory, the well-known problems of packing and independence are generalized by broadcast packing and broadcast independence. As an analogy, placing cell towers (of various powers) in a network so that the signals do not interfere is a broadcast packing problem. Placing cell towers in a network where the signals can interfere at any point except the towers is a broadcast independence problem. In this talk, I will present explicit formulas for the broadcast independence and packing numbers of perfect binary and k-ary trees, along with the proof techniques used to determine these formulas. Furthermore, I will present a linear time algorithm for computing the broadcast independence number of spiders. This research was motivated by the question “Can we determine the broadcast independence number of other subclasses of the class of trees? In particular, what about k-ary trees?”, which was posed by Ahmane et al. in their paper On the broadcast independence number of caterpillars.

This is joint work with Dr. Richard Brewster.

Abstract: Let q=1 mod 4 be a prime power and let F_q be the finite field of q elements. The Paley graph of order q is the graph with vertex set F_q, such that two vertices are adjacent if and only if their difference is a square in F_q. Paley graphs play an important role in many branches of combinatorics and number theory. Among many exciting questions related to Paley graphs, estimating their clique number is of importance. In this talk, I will report recent progress on the lower bounds and upper bounds on the clique number of Paley graphs and Paley-like graphs. Joint work with Seoyoung Kim, Jozsef Solymosi, and Semin Yoo.

Since suggested by Tur\'an in 1941, determining the Tur\'an density of hypergraphs has been a notoriously difficult problem at the center of extremal combinatorics. Subsequently, several natural variants of this problem have been suggested, most prominently the uniform Tur\'an density by Erd\H{o}s and S\'os and the codegree Tur\'an density by Mubayi and Zhao. Roughly speaking, the Tur\'an density is the threshold of the edge density above which large hypergraphs are guaranteed to contain a copy of a fixed hypergraph~$F$. Similarly, the uniform Tur\'an density and the codegree Tur\'an density are the thresholds of the local density and the minimum codegree, respectively, above which large hypergraphs are guaranteed to contain a copy of~$F$. In this talk, we will discuss recent results which determine several variants of the Tur\'an density in new instances and make progress towards a problem of Erd\H{o}s and S\'os. Further, we will present our recent result with Piga which states that there are hypergraphs with arbitrarily small codegree Tur\'an density. This is in contrast to the behaviour of the classical Tur\'an density and the uniform Tur\'an density due to results by Erd\H{o}s and by Reiher, R\"odl, and Schacht, respectively.

Based on joint works with Chen, Conlon, Piga, and Sales.

Evelyne will be giving her talk remotely (on Zoom). Local participants are still encouraged to come to COR A128 to view it on the projector.

Abstract: Suppose a graph G has list chromatic number k. It is easy to see that if L is a (k+1)-list assignment for G, then G admits two L-colourings f and g where f(v) =/= g(v) for every vertex v in the graph. But what if we want still more disjoint L-colourings? In this talk, I will discuss recent progress towards determining the list packing number of various classes of planar graphs: that is, the smallest number k such that if L is a k-list assignment for an arbitrary graph G in the class under study, then L can be decomposed into k disjoint L-colourings. All results I will discuss also hold in the correspondence colouring framework. Joint work with Daniel Cranston.

Abstract: In 1974 Erdős and Rothschild asked the following question: given integers k, s and a large n, what is the maximum number of s-edge-colourings of an n-vertex graph free of a monochromatic k-vertex clique? A follow up question is to determine which graph(s) attain this maximum. Recent work of Pikhurko, Staden and Yilma shows that in most cases this problem reduces to considering complete multipartite graphs and only counting a natural family of K_k-free "template" colourings of their edge set. Despite this reduction, the Erdős-Rothschild problem has only been solved for some small s and k. Various generalisations of this problem have been considered in the literature, where instead of forbidding monochromatic cliques, we forbid other, non-monochromatic, patterns on a clique. We consider the problem of maximising the number of s-edge-colourings without triangles which see exactly two colours, and show that for every s, the extremal graph is an r-partite Turán graphs where r is easy to compute for any given s. This is joint work with Pranshu Gupta, Emil Powierski and Katherine Staden.