Talks in Combinatorics

Next Friday (July 4) we have three 30-minute-talks in combinatorics at Edifici històric of Universitat de Barcelona in the seminar room iA (ground floor of Matemàtiques i Informàtica). The tentative schedule is the following (abstracts below):

11:00 Simeon Ball (Universitat Politècnica de Catalunya)
The forbidden subgraph problem

11:40 Hoang La (Université Paris-Saclay)
DOM-Boundedness: An Analog of chi-Boundedness for Domination in Graphs

12:20 Xiaodi Song (Northwestern Polytechnical University, Xi'an)
On the algebraic connectivity of token graphs and graphs under perturbations

Feel free to join, invite people that might be interested or tell me if I should add someone to the list. We will broadcast the talks through zoom at: https://ub-edu.zoom.us/j/96659426700?pwd=16wWJUhhBv1lxntGj3cHBaWy6hAayZ.1

Talks

Simeon Ball: The forbidden subgraph problem

This talk will investigate the problem of determining the function ex(n,H), the number of edges a graph on n vertices can have which does not have any copies of H as a subgraph. The asymptotic behaviour of ex(n,H) is known for all non-bipartite graphs H (Erdos-Stone theorem) and for a few small bipartite graphs H. We will look closely at some geometric constructions which improve probabilistic lower bounds when H is a complete bipartite graph and when H is an even cycle.


Hoang La: DOM-Boundedness: An Analog of chi-Boundedness for Domination in Graphs

In graph coloring, the chromatic number chi of a graph i.e., the minimum number of colors required to color the vertices such that adjacent vertices receive different colors, is often not well-approximated by the clique number ω, the size of the largest complete subgraph. For instance, there exist many constructions of triangle-free graph families (ω = 2) with arbitrarily large chromatic numbers. Graph families for which chi is closely related to ω are said to be chi-bounded. More formally, a family 𝔽 is χ-bounded if there exists a function f such that for every graph G in 𝔽, ω(G) ≤ χ(G) ≤ f(ω(G)). chi-boundedness is a well-studied area in graph theory.

A dominating set is a set of vertices whose closed neighborhood covers all vertices of the graph. In proper coloring, the goal is to partition the vertex set into the smallest number of independent sets. In contrast, for domination, the trivial solution (e.g., taking all vertices) yields one dominating set, but the challenge lies in partitioning the vertices into as many disjoint dominating sets as possible. This maximum number is known as the domatic number, denoted DOM(G), and computing it is NP-hard.

A graph cannot have more than δ(G) + 1 disjoint dominating sets, where δ(G) is the minimum degree of G. There are also families of graphs with DOM(G) = 2 and arbitrarily large δ(G)—analogous to how chi can be arbitrarily large while ω remains small. Thus, minimum degree plays for DOM the role that clique number plays for chi. In this talk, we introduce and study DOM-bounded families of graphs: families 𝔽 for which there exists a function f such that for every graph G in 𝔽, DOM(G) ≤ δ(G) + 1 ≤ f(DOM(G)).

We present recent results in this direction, including analogs of the Gyárfás–Sumner conjecture for the domatic number, as well as a fractional version of the problem.

This work was done in collaboration with Quentin Chuet, François Pirot, and Hossein Zare.


Xiaodi Song: On the algebraic connectivity of token graphs and graphs under perturbations

Given a graph G = (V, E) on n vertices and an integer k between 1 and n − 1, the k-token graph F_k(G) has vertices representing the k-subsets of V , and two vertices are adjacent if their symmetric difference is the two end-vertices of an edge in E. Using the theory of Markov chains of random walks and the interchange process, it was proved that the algebraic connectivities (second smallest Laplacian eigenvalues) of G and F_k(G) coincide, but a combinatorial/algebraic proof is elusive. In this talk, we show that such equality holds using the latter approach for different new classes of graphs under perturbations, such as extended cycles, extended complete bipartite graphs, kite graphs, and graphs with a cut clique. Kite graphs are formed by a graph (head) with several paths (tail) rooted at the same vertex.