Algomanet – spring 2025
Basic information
The two Algomanet courses given by Jan Volec and Xuding Zhu, which are scheduled for the spring 2025, will take place in the week June 30 – July 4 at the Charles University in Prague. The courses will be delivered on site only, starting at 9am on Monday June 30 and concluding in late afternoon on Friday July 4.
Jan Volec: Flag algebra method
Flag algebras provides a systematic tool for applying double counting and
Cauchy-Schwarz formulas in the setting of counting substructures in (large)
discrete objects (graphs, hypergraphs, permutations, set of points in the
plane). The method was pioneered by Razborov in 2007, building up on a previous
work of Bondy. Since then, it has successfully solved a number of open
questions in extremal combinatorics.
In this course, we will first introduce the general framework of flag algebras
together with closely related notions from graph limits, and then focus on
applications of the framework in graph theory, permutations and Ramsey theory.
Xuding Zhu: Applications of Combinatorial Nullstellensatz to graph colourings
The Combinatorial Nullstellensatz gives a sufficient condition for a polynomial P(x1, x2, . . . , xn) ∈ F[x1, x2, . . . , xn] to have a non-zero point in a given grid S1×S2×. . .×Sn, where Si ⊆ F. Many combinatorial problems can be stated as the existence of a non-zero point of a polynomial in a certain grid, and hence have the potential of applying Combinatorial Nullstellensatz. This series of lectures explains some applications of Combinatorial Nullstellensatz to graph coloring and related problems. We focus on methods that show certain monomials in the expansion of a polynomial are non-vanishing, i.e., having non-zero coefficients. These include Alon-Tarsi orientations, interpolation formula and permanent method. These methods are illustrated with applications to problems in list colouring of graphs, vertex-edge weighting of graphs, list of forbidden out-degree orientations of graphs, etc.