# Combinatorics

## On vertex-transitive graphs with a unique hamiltonian circle

We will discuss graphs that have a unique hamiltonian cycle and are vertex-transitive, which means there is an automorphism that takes any vertex to any other vertex. Cycles are the only examples with finitely many vertices, but the situation is more interesting for infinite graphs. (Infinite graphs do not have "hamiltonian cycles," but there are natural analogues.) The case where the graph has only finitely many ends is not difficult, but we do not know whether there are examples with infinitely many ends. This is joint work in progress with Bobby Miraftab.

## Height gaps for coefficients of D-finite power series

A power series $f(x_1,\ldots,x_m)\in \mathbb{C}[[x_1,\ldots,x_m]]$ is said to be D-finite if all the partial derivatives of $f$ span a finite dimensional vector space over the field $\mathbb{C}(x_1,\ldots,x_m)$. For the univariate series $f(x)=\sum a_nx^n$, this is equivalent to the condition that the sequence $(a_n)$ is P-recursive meaning a non-trivial linear recurrence relation of the form:

$$P_d(n)a_{n+d}+\cdots+P_0(n)a_n=0$$ where the $P_i$'s are polynomials. In this talk, we consider D-finite power series with algebraic coefficients and discuss the growth of the Weil height of these coefficients. This is from a joint work with Jason Bell and Umberto Zannier in 2019 and a more recent work in June 2022.

## Non-realizability of polytopes via linear programming

A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction. The search space for these polynomials is ideal of Grassmann-Plücker relations, which quickly becomes too large to efficiently search, and in most instances where this technique is used, additional assumptions on the structure of the desired polynomial are necessary.

In this talk, I will describe how by changing the search space, we are able to use linear programming to exhaustively search for similar polynomial certificates of non-realizability without any assumed structure. We will see that, perhaps surprisingly, this elementary strategy yields results that are competitive with more elaborate alternatives and allows us to prove non-realizability of several interesting polytopes.

## Subgraphs in Semi-random Graphs

The semi-random graph process can be thought of as a one player game. Starting with an empty graph on n vertices, in each round a random vertex u is presented to the player, who chooses a vertex v and adds the edge uv to the graph (hence 'semi-random'). The goal of the player is to construct a small fixed graph G as a subgraph of the semi-random graph in as few steps as possible. I will discuss this process, and in particular the asympotically tight bounds we have found on how many steps the player needs to win. This is joint work with Trent Marbach, Pawel Pralat and Andrzej Rucinski.

## Combinatorial structures in perturbative quantum field theory

I will give an overview of a few places where combinatorial structures have an interesting role to play in quantum field theory and which I have been involved in to varying degrees, from the Connes-Kreimer Hopf algebra and other renormalization Hopf algebras, to the combinatorics of Dyson-Schwinger equations and the graph theory of Feynman integrals.

For other events in this series see the quanTA events website.

## Richard Guy and the Encyclopedia of Integer Sequences: A Fifty-Year Friendship

Richard Guy was a supporter of the database of integer sequences right from its beginning in the 1960s. This talk will be illustrated by sequences that he contributed, sequences he wrote about, and especially sequences with open problems that he would have liked but that I never got to tell him about.

## The Unity of Combinatorics: Connections and Wonders

An account of how a great Guy and his Brown coauthor created a 300-page book entitled "The Unity of Combinatorics" out of a 30-page paper from 1995 of the same name. The latter was an outline of a proposed lecture series, whose purpose was to feature the many connections within the vast area of combinatorics, thereby dispelling the then prevalent notion that combinatorics is just a bag of tricks. In writing the book, we took this notion and ran with it --- and how!

I'll talk about a number of these connections and some topics that seem almost magical, including Beatty sequences, Conway worms, games played with turtles instead of coins, and a way of viewing the non-negative integers as a field. The book begins with a child playing with colored blocks on his living-room rug and ends with a description of the Miracle Octad Generator. Finally, I'll talk about working with this gentlemanly giant of the world of numbers and sequences and patterns and games.

## Unsolved Combinatorial Games Richard K. Guy liked and others he would have liked

Richard started the Unsolved Problems in Combinatorial Games Column. I'll consider some of his favourites, talk about some developments, and add a few reminiscences.

## Random discrete surfaces

A triangulation of a surface is a way to divide it into a finite number of triangles. Let us pick a random triangulation uniformly among all those with a fixed size and genus. What can be said about the behaviour of these random geometric objects when the size gets large? We will investigate three different regimes: the planar case, the regime where the genus is not constrained, and the one where the genus is proportional to the size. Based on joint works with Baptiste Louf, Nicolas Curien and Bram Petri.

- Read more about Random discrete surfaces
- 1513 reads

## Explicit results about primes in Chebotarev's density theorem

Let $L/K$ be a Galois extension of number fields with Galois group $G$, and let $C⊂G$ be a conjugacy class. Attached to each unramified prime ideal p in OK is the Artin symbol $\sigma p$, a conjugacy class in $G$. In 1922 Chebotarev established what is referred to his density theorem (CDT). It asserts that the number $\pi C(x)$ of such primes with $\sigma p=C$ and norm $Np≤x$ is asymptotically $\left|C\right|\left|G\right|\mathrm{Li} (x)$ as $x\rightarrow\infty$ where $\mathrm{Li} (x)$ is the usual logarithmic integral. As such, CDT is a generalisation of both the prime number theorem and Dirichlet's theorem on primes in arithmetic progressions. In light of Linnik's result on the least prime in an arithmetic progression, one may ask for a bound for the least prime ideal whose Artin symbol equals C. In 1977 Lagarias and Odlyzko proved explicit versions of CDT and in 1979 Lagarias, Montgomery and Odlyzko gave bounds for the least prime ideal in the CDT. Since 2012 several unconditional explicit results of these theorems have appeared with contributions by Zaman, Zaman and Thorner, Ahn and Kwon, and Winckler. I will present several recent results we have proven with Das, Ng, and Wong.