# KPPY 87

Jungtaek Oh, Jang Soo Kim, Sergey Goryainov, Sejeong Bang, Boram Park

Jun 15, 2018 (friday). 11am - 5:30pm at KNU

Schedule | ||

11:00am - 11:50 |
Jungtaek Oh KNU | Distribution theory of Runs and Patterns |

12pm - 1:25 | Lunch | |

1:30 - 2:20 |
Jang Soo Kim Sungkyunkwan University | Lecture hall tableaux |

2:30 - 3:20 |
Sergey Goryainov Russian Academy of Sciences | On eigenfunctions and maximal cliques of Paley graphs of square order |

3:30 - 4:20 |
Sejeong Bang Yeungnam University | Parameters of geometric and antipodal distance-regular graphs |

4:30 - 5:20 |
Boram Park Ajou University | Trees in a graph with large acyclic chromatic number |

## Abstracts

Jungtaek Oh

Distribution theory of Runs and Patterns

Distribution theory of Runs and Patterns

We propose recurrence algorithms for the probability distribution function (p.d.f.) and the probability generating function (p.g.f.) of the waiting time for the number of trials needed to get $k$ consecutive ones, in a sequence of independent, or Markov dependent, Bernoulli trials. This uses generalized Fibonacci sequences of order $k$. Maximum likelihood estimation (MLE) methods for the probability distributions are presented in both cases with simulation examples. The probability distribution of the waiting time, the number of trials needed, to get either $k$ consecutive ones or zeroes for the first time 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 a symmetric trial with $p = 1/2$ is considered. We consider the distribution of runs and patterns related to run lengths for multi-state trials. Finally, we generalize negative binomial distributions of order $k$ using Bernoulli trials with a geometrically varying success probability.

Jang Soo Kim

Lecture hall tableaux

Lecture hall tableaux

We introduce lecture hall tableaux, which are fillings of a skew Young diagram satisfying certain conditions. Lecture hall tableaux generalize both lecture hall partitions and anti-lecture hall compositions, and also contain reverse semistandard Young tableaux as a limit case. We show that the coefficients in the Schur expansion of multivariate little $q$-Jacobi polynomials are generating functions for lecture hall tableaux. Using a Selberg-type integral we show that the moment of multivariate little $q$-Jacobi polynomials, which is equal to a generating function for lecture hall tableaux of a Young diagram, has a product formula. We also explore various combinatorial properties of lecture hall tableaux. This is joint work with Sylvie Corteel.

Sergey Goryainov

On eigenfunctions and maximal cliques of Paley graphs of square order

On eigenfunctions and maximal cliques of Paley graphs of square order

In this talk we present a family of maximal cliques of size $\frac{q+1}{2}$ or $\frac{q+3}{2}$,
accordingly as $q\equiv 1(4)$ or $q\equiv 3(4)$,
in Paley graphs of order $q^2$, where $q$ is an odd prime power.
After that we use the new cliques to define a family of eigenfunctions corresponding
to both non-principal eigenvalues and having support size $q+1$,
which is the minimum possible value by the weight-distribution bound.
Finally, we prove that the constructed eigenfunction comes from an equitable partition.

Sejeong Bang

Parameters of geometric and antipodal distance-regular graphs

Parameters of geometric and antipodal distance-regular graphs

In this talk, we study parameters of geometric and antipodal distance-regular graphs. By using this result, we show the non-existence of some geometric and antipodal distance-regular graphs and we will give a diameter bound for them.

Boram Park

Trees in a graph with large acyclic chromatic number

Trees in a graph with large acyclic chromatic number

The

When considering the class $\mathcal C$ of graphs with no $F$ as an induced subgraph, it is not hard to see that every graph in $\mathcal C$ has bounded chromatic number if and only if $F$ is a complete graph of size at most two. We study this phenomena for the class of graphs with no $F$ as a subgraph for $H$-avoiding coloring. We completely characterize all graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded $H$-avoiding chromatic number for a large class of graphs $H$. As a corollary, our main result implies a characterization of graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded acyclic chromatic number. This talk is based on joint work with Ilkyoo Choi (Hankuk University of Foreign Studies) and Ringi Kim (Korea Advanced Institute of Science and Technology).

*chromatic number*of a graph is the minimum $k$ such that the graph has a proper $k$-coloring. There are many coloring parameters in the literature that are proper colorings that also forbid bicolored subgraphs. Some examples are $2$-distance coloring, acyclic coloring, and star coloring, which forbid a bicolored path on three vertices, bicolored cycles, and a bicolored path on four vertices, respectively. We capture this notion by defining an*$H$-avoiding $k$-coloring*to be a proper $k$-coloring that forbids a bicolored subgraph $H$.When considering the class $\mathcal C$ of graphs with no $F$ as an induced subgraph, it is not hard to see that every graph in $\mathcal C$ has bounded chromatic number if and only if $F$ is a complete graph of size at most two. We study this phenomena for the class of graphs with no $F$ as a subgraph for $H$-avoiding coloring. We completely characterize all graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded $H$-avoiding chromatic number for a large class of graphs $H$. As a corollary, our main result implies a characterization of graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded acyclic chromatic number. This talk is based on joint work with Ilkyoo Choi (Hankuk University of Foreign Studies) and Ringi Kim (Korea Advanced Institute of Science and Technology).