• home

TBA

TBA

TBA

TBA

TBA

TBA

TBA

TBA

Abstract: The boxicity of a graph G is a key graph parameter introduced by Roberts in 1969. It represents the minimum dimension d such that G can be realized as the intersection graph of a family of axis-parallel boxes in R^d. Boxicity is an important measure of structural complexity in various networks, including ecological and social systems. It also exhibits strong connections with other graph parameters such as treewidth, chromatic number, and vertex-cover number.

Determining the boxicity of a graph is computationally challenging—it is NP-hard to decide if a graph has boxicity at most 2. Consequently, much research has focused on developing efficient algorithms for specific graph classes or establishing upper bounds under particular conditions.

In this talk, we introduce a simple, general approach to determining the boxicity of a graph by studying its interval-order subgraphs. Our method leads to several new bounds, including those for Kneser graphs (confirming a conjecture by Caoduro and Lichev [Discrete Mathematics, Vol. 346, 5, 2023]), line graphs, complements of line graphs, and complements of block graphs. Notably, our approach also yields polynomial-time algorithms. In particular, we present an algorithm to compute the boxicity of complements of block graphs—marking the first non-trivial family for which boxicity can be computed in polynomial time.

This is joint work with Amna Adnan, Matthew Barclay, Josh Childs, Will Evans, Tao Gaede, and András Sebő.

Abstract: Counting lattice paths with unit up and right steps beginning at the origin that are somehow constrained by a boundary is an old problem. When the boundary is the line y=x the celebrated Chung-Feller theorem states the number of paths having k flaws (steps above the boundary) is independent of k. The classic Dyck paths are those with 0 flaws, and the Chung-Feller theorem can be used to give a simple proof of their count.

More recently, we have discovered a similar, though more complicated, result to the Chung-Feller theorem for paths constrained by a line of rational slope. In this talk, I will explain these new results and also explain other recent results on counting lattice paths.

My aim is to have a broadly accessible talk, and I will assume very little prior knowledge in this area.

This is joint work with F. Firoozi and J. Jedwab.

A proper conflict-free colouring of a graph is a (vertex-)colouring with no monochromatic edges such that for every nonisolated vertex v, the neighbourhood N(v) contains a vertex w coloured with a colour not appearing on N(v)-{w}. For a real number h, a colouring of a graph with no monochromatic edges is h-conflict-free if for every vertex v, N(v) contains at least min{deg(v), h} vertices coloured with a colour used only once in N(v). For a real number p, we define a p-peaceful colouring to be a colouring f with no monochromatic edges in which for every vertex v,

|{w in N(v) : there exists u in N(v)-{w} with f(u)=f(w)}| ≤ p.

We note that for a d-regular graph, a colouring is an h-conflict-free proper colouring precisely if it is a (d-h)-peaceful colouring. In contrast, if G is an irregular graph of maximum degree Delta then while a p-peaceful colouring and a (\Delta-p)-conflict-free colouring impose the same condition on maximum degree vertices, the peaceful colouring imposes weaker conditions on low degree vertices. We present some results on these three types of colourings. These are joint work with Chun-hung Liu.

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.