KPPY 69

Traditionally, the distributions of runs and patterns have been studied via combinatorial analysis. For example, Mood (1940) wrote: "The distribution problem is, of course, a combinatorial one, and the whole development depends on some identities in combinatory analysis" and Wald and Wolfowitz, 1940; David, 1947; Hirano, 1986; Godbole, 1990. However, finding the appropriate combinatorial identities to derive the probability distributions can be difficult, if not impossible, for complex runs, and this perhaps is the reason why the exact distributions of many common runs remain unknown especially for non-i.i.d. cases. Furthermore, the required identities often differ even for similar runs, and hence, even in the simplest case of independent and identically distributed (i.i.d.) two-state trials (so-called "Bernoulli trials"), each new distribution. In this talk, I want to introduce two kinds of waiting time problem. First, Consider an infinite sequence of Bernoulli trials $\{X_i \mid i = 1, 2, . . .\}$. Let $W(k)$ denote the waiting time, the number of trials needed, to get either $k$ consecutive ones or $k$ consecutive zeros. The probability distribution of $W(k)$ is derived for both independent and homogeneous two-state Markovian Bernoulli trials, using a generalized Fibonacci sequence of order $k$. For independent Bernoulli trials, the special case of the symmetric trial with $p = 1/2$ is considered. Second, Let $V(k)$ denote the waiting time, the number of trials needed to get consecutive $k$ ones. We propose recurrence algorithms for the probability distribution function (pdf) and the probability generating function (pgf) of the sequences $V(k)$ of independent and Markov dependent Bernoulli trials using generalized Fibonacci sequences of order $k$.

Online Ramsey theory is a study on the online version of Ramsey theory. Given a fixed graph $H$ and a class $\mathcal{C}$ of graphs, an {\it online Ramsey game} $(H, \mathcal{C})$ is a game between two players Builder and Painter with the following rules: An unbounded set of vertices is given as an initial state, and on each turn Builder introduces a new edge with the constraint that the resulting graph must be in $\mathcal C$ and Painter colors the new edge either red or blue. Builder wins if Painter is forced to make a monochromatic copy of $H$ at some point of the game, and Painter wins if a monochromatic copy of $H$ can be avoided forever. Online Ramsey theory was first investigated in 2004 by Grytczuk, Hałuszczak, and Kierstead where they studied online Ramsey theory on forests, $k$-colorable graphs, outerplanar graphs, and planar graphs. Recently, Petříčková continue the study on planar graphs further by disproving a conjecture by Grytczuk, Hałuszczak, and Kierstead. We future carry on the study of online Ramsey theory by extending results from both papers. This is joint work with Ilkyoo Choi and Jisu Jeong and Sang-il Oum.

For a ring $R$, the zeta function of $R$ is defined by \[ \zeta_R(s)=\sum_{n=0}^{\infty} a_n n^{-s},\] where $a_n$ is the number of (left) ideals of $R$ with index $n$. We only view the zeta function as a formal Dirichlet series. Every graph which has the three distinct integral eigenvalues of its adjacency matrix has the adjacency algebra of the form $\mathbb{Z}[x]/(x(x-\alpha)(x-\beta))$, where $\alpha$ and $\beta$ are nonzero distinct integers. In this case, we compute its zeta function.

Affine Schubert calculus is an extension of Schubert calculus to affine Grassmannians and affine flag varieties. The new approach to affine Schubert calculus is made possible by the discovery of certain explicitly defined symmetric functions called k-Schur functions. The k-Schur functions, which arose in the study of the seemingly unrelated Macdonald theory, were shown to be connected to the geometry and topology of the affine Grassmannian. In this talk, we will define k-Schur functions and strong Schur functions as symmetric functions and elements in affine nilCoxeter algebra. After digesting their combinatorics, I will connect some of their combinatorial properties with algebraic/geometric properties of affine Grassmannians and affine flag varieties. It was shown by Kumar and Kostant that the structure coefficients of the cohomology of affine Grassmannians and affine flag varieties is the same as the structure coefficients of the coproduct of nilCoxeter algebra. We will briefly review this theory and connect it with combinatorics. This will produce the Pieri rule for the affine flag variety.

Given a colouring $f$ of a graph $G$, consider the process of recolouring a single vertex $v$ to obtain a new colouring $f'$. Given two colourings $f$ and $g$ of $G$, a natural question is can $g$ be obtained from $f$ through a sequence of such single vertex recolourings? In the case of classical $k$-colourings Cereceda, van den Heuvel, and Johnson have shown that this question can be answered in polynomial time when $k=3$. Whereas, Bonsma and Cereceda have shown the problem is PSPACE-complete for $k \geq 4$. We extend this work to circular $(p,q)$-colourings. We establish that for $p/q < 4$ the problem is polynomial, and it is PSPACE-complete for $p/q \geq 4$. This is joint work with Sean McGuinness, Ben Moore, and Jon Noel.