In this thesis, we investigate three problems in extremal combinatorics, using methods from combinatorics, representation theory, finite field theory and probabilistic combinatorics.
In this thesis we perform calculations on the CFT side of the duality between N = 4 supersymmetric Yang-Mills theory and type IIB string theory on AdS5 x S5. The results are used to study quantum ...gravity on AdS. Chapters 3 and 4 explore the structure and combinatorics of the quarter BPS sector with gauge groups U(N), SO(N) and Sp(N) in the planar free field limit. For U(N), we identify the multi-traces with a word monoid, with aperiodic single traces corresponding to Lyndon words. For SO(N) and Sp(N) we generalise Lyndon words using minimally periodic conditions. We present the quarter-BPS generating function for SO(N)/Sp(N) gauge groups. Chapter 5 examines the permutation algebras behind operator construction in the free field theory with SO(N) and Sp(N) gauge groups. There is a rich group independent structure, including formulae for correlators expressed purely in terms of permutations. We introduce Schur and restricted Schur bases for the baryonic sector of the SO(N) theory, derive covariant bases for the quarter-BPS sectors of SO(N) and Sp(N) theories, and calculate their correlators. Chapter 6 studies the projection of the half-BPS sector from the U(N) theory to the SO(N)/Sp(N) theory, dual to an orientifold projection of S5 to RP5. This is characterised by a plethystic refinement of Littlewood-Richardson coefficients, expressible in terms of the combinatorics of domino diagrams. A second expression for the projection is derived in terms of a product of SO(N)/Sp(N) giant graviton states. Chapter 7 looks at the quarter-BPS sector of the U(N) theory at weak coupling. Multi-symmetric functions allow systematic study of the finite N properties, involving combinatorics of set partitions. We construct a quarter-BPS, finite N-compatible, U(2) covariant, orthogonal basis, labelled by a U(N) Young diagram and a multiplicity, for which we derive precise counting results. These are interpreted as quarter-BPS deformations of the half-BPS giant graviton states.
In this thesis we consider five problems in extremal combinatorics all of which which are all amenable to approaches based on local structure. The first part of this thesis looks at rainbow subgraphs ...at extremal thresholds. We show that as soon as they appear, we can also find rainbow copies of Perfect Matchings, H-factors and Hamilton cycles in large graphs. We then look to random digraphs and consider the D(n, p) model in which each edge is present independently with probability p. We find tail bounds on the size of the largest strongly connected component in the critical window around p = 1/n. Finally, we consider the partition function of the ferromagnetic Potts model on graphs of bounded maximum degree. We show that there exists an open set in C containing an interval 1, w inside which the partition function has no zeros.
In this paper, we study a Ramsey-type problem for equations of the form ax+by=p(z). We show that if certain technical assumptions hold, then any 2-colouring of the positive integers admits infinitely ...many monochromatic solutions to the equation ax+by=p(z). This entails the 2-Ramseyness of several notable cases such as the equation ax+y=zn for arbitrary a∈Z+ and n≥2, and also of ax+by=aDzD+…+a1z∈Zz such that gcd(a,b)=1, D≥2, a,b,aD>0 and a1≠0.
We introduce an algorithm for the uniform generation of infinite runs in concurrent systems under a partial order probabilistic semantics. We work with trace monoids as concurrency models. The ...algorithm outputs on-the-fly approximations of a theoretical infinite run, the latter being distributed according to the exact uniform probability measure. The average size of the approximation grows linearly with the time of execution of the algorithm. The execution of the algorithm only involves distributed computations, provided that some - costly - precomputations have been done.
The forbidden number $\mathrm{forb}(m,F)$, which denotes the maximum number
of unique columns in an $m$-rowed $(0,1)$-matrix with no submatrix that is a
row and column permutation of $F$, has been ...widely studied in extremal set
theory. Recently, this function was extended to $r$-matrices, whose entries lie
in $\{0,1,\dots,r-1\}$. The combinatorics of the generalized forbidden number
is less well-studied. In this paper, we provide exact bounds for many
$(0,1)$-matrices $F$, including all $2$-rowed matrices when $r > 3$. We also
prove a stability result for the $2\times 2$ identity matrix. Along the way, we
expose some interesting qualitative differences between the cases $r=2$, $r =
3$, and $r > 3$.
Let $G$ be a a connected graph. The Wiener index of a connected graph is the
sum of the distances between all unordered pairs of vertices. We provide
asymptotic formulae for the maximum Wiener index ...of simple triangulations and
quadrangulations with given connectivity, as the order increases, and make
conjectures for the extremal triangulations and quadrangulations based on
computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean
of the distances from $v$ to all other vertices of $G$, then the remoteness of
$G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices
$v$ of $G$. We give sharp upper bounds on the remoteness of simple
triangulations and quadrangulations of given order and connectivity.
We provide a pair of ribbon graphs that have the same rotor routing and
Bernardi sandpile torsors, but different topological genus. This resolves a
question posed by M. Chan Cha. We also show that if ...we are given a graph, but
not its ribbon structure, along with the rotor routing sandpile torsors, we are
able to determine the ribbon graph's genus.
In this extended abstract we announce a proof that, in a Coxeter group of rank 3, low elements are in bijection with small inversion sets. This gives a partial confirmation of Conjecture 2 in Dyer, ...Hohlweg '16. That same article provides the main ingredient: the bipodality of the set of small roots is used to propagate information on the vertices of inversion polytopes.
A famous conjecture of Stanley states that his chromatic symmetric function distinguishes trees. As a quasisymmetric analogue, we conjecture that the chromatic quasisymmetric function of Shareshian ...and Wachs and of Ellzey distinguishes directed trees. This latter conjecture would be implied by an affirmative answer to a question of Hasebe and Tsujie about the $P$-partition enumerator distinguishing posets whose Hasse diagrams are trees. They proved the case of rooted trees and our results include a generalization of their result.
PDF
