• home

Abstract: Many fundamental problems in extremal combinatorics can be expressed as inequalities in graph homomorphism densities. In this talk, I will introduce some new results on this topic. Our research involves Sidorenko's conjecture, Kohayakawa-Nagle-R{\"o}dl-Schacht conjecture and common graphs. Moreover, I will share some recent advancements in problems of homomorphism densities for tournaments.

Abstract: A classical question in extremal (hyper)graph theory asks for tight minimum degree conditions which force the existence of certain spanning structures in large graphs, generalising Dirac's theorem from 1952. One aspect of this concerns tiling graphs with identical vertex disjoint copies of a small subgraph. For example, asking for tight minimum codegree conditions in a k-uniform hypergraph which force a perfect matching (under the obvious additional necessary condition that the number of vertices is divisible by k). Whilst there has been a lot of interest in these types of tiling problem, still very few results are known. We share a new result in this area, which is joint work with Amarja Kathapurkar, Natasha Morrison and Richard Mycroft.

Abstract: In defining colouring of oriented graphs via homomorphism one finds an easily checkable necessary condition for a valid colouring — vertices at directed distance at most two must receive different colours. With this idea in mind we extend the definition of quasi-transitive digraph to mixed graphs. In this talk we explore a full characterisation of quasi-transitive mixed graphs of degree at most three and find that the general problem of deciding if a graph admits a mixed orientation as a quasi-transitive mixed graph is NP-complete.

Abstract: Let $G$ be a graph with $n$ vertices. Let $A(G)$ be its adjacency matrix. Let $\lambda_1(G), \lambda_2(G)$ denote the largest and second largest eigenvalues of the adjacency matrix. Bollob\'{a}s and Nikiforov (2007) conjectured that for any graph $G \neq K_n$ with $m$ edges \[\lambda_1^2+\lambda_2^2\le \bigg( 1-\frac{1}{\omega(G)}\bigg)2m,\] where $\omega(G)$ denotes the clique number of $G$. In this talk, we prove this conjecture for graphs with not so many triangles, using the method of triangle counting. This is a joint work with Hitesh Kumar.

Abstract: An edge mapping of a graph is a function f:E(G) -> E(G) where f(e) \neq e for all e in E(G). A subgraph H of G is called f-free if for every e in E(H) f(e) \notin E(H). A graph G is called unavoidable for a graph H if every edge mapping of G has at least one f-free copy of H and minimally unavoidable if no proper subgraph of G also satisfies this property. In this talk, we will discuss the set of all minimally unavoidable graphs for a graph H for several different types of graphs H.

ABSTRACT: A network of interacting qubits (usually subatomic particles) can be modelled by a connected weighted undirected graph $G$. The vertices and edges of $G$ represent the qubits and their interactions in the network, respectively. Quantum mechanics dictate that the evolution of the quantum system determined by $G$ over time is completely described by the unitary matrix $U(t)=\exp(itA)$, where $A$ is the adjacency matrix of $G$. Here, we interpret the modulus of the $(u,v)$ entry of $U(t)$ as the probability that the quantum state at vertex $u$ is found in $v$ at time $t$. In this talk, we discuss how the algebraic and spectral properties of a graph influence its ability to perform quantum state transfer.

Abstract: We show that \((n,d,\lambda)\)-graphs with \(\lambda=O(d/log^3n)\) are universal with respect to all bounded degree spanning trees. This significantly improves upon the previous best bound due to Han and Yang, and makes progress towards a problem of Alon, Krivelevich, and Sudakov from 2007. The key new idea in our proof relies on the existence of sorting networks of logarithmic depth, as given by a celebrated construction of Ajtai, Koml\'{o}s and Szemer\'{e}di, with further applications to the vertex disjoint paths problem. Joint work with Joseph Hyde, Alp M\"{u}yesser, and Matías Pavez-Signé.

Abstract: A combinatorial object is said to be quasirandom if it exhibits certain properties that are typically seen in a truly random object of the same kind. It is known that a permutation is quasirandom if and only if the pattern density of each of the twenty-four 4-point permutations is close to 1/24, which is its expected value in a random permutation. In other words, the set of all twenty-four 4-point permutations is quasirandom-forcing. Moreover, it is known that there exist sets of eight 4-point permutations that are also quasirandom-forcing. Breaking the barrier of linear dependency of perturbation gradients, we show that every quasirandom-forcing set of 4-point permutations must have cardinality at least five.

Abstract: A geometric graph $G$ is a graph $G$ whose vertices are drawn in the plane such that no three vertices are collinear, and each edge of G is a straight line segment. A geometric homomorphism from geometric graph $G$ to geometric graph $H$ is a homomorphism that preserves crossings. Similar to the regular chromatic number, the geochromatic number of a geometric graph $G$ is the smallest integer $n$ such that there is a geometric homomorphism from $G$ to a geometric clique $K_n$.

In this talk, we will particularly discuss the relation between chromatic numbers and geochromatic numbers. Even for a bipartite graph, its geochromatic number can be unbounded. However, if the graph is not too "dense", for example, every pair of crossing has distance at least $2$, then its geochromatic number is bounded by a constant.

Abstract: Strong cocomparability graphs are the reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows 01, 10. Strong cocomparability graphs form a subclass of cocomparability graphs (i.e., the complements of comparability graphs) and can be recognized in polynomial time.

In his seminal paper, Gallai characterized cocomparability graphs in terms of a forbidden structure called asteroids. Gallai proved that cocomparability graphs are precisely those reflexive graphs which do not contain asteroids.

In this talk, I will present a characterization of strong cocomparability graphs which is analogous to Gallai's characterization for cocomparability graphs. More precisely, I will show that strong cocomparability graphs are precisely those reflexive graphs which do not contain weak edge-asteroids (a weaker version of asteroids). The characterization also leads to a polynomial time recognition algorithm for strong cocomparability graphs.

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.