Semin Yoo (유세민), Paley-like quasi-random graphs arising from polynomials

We provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of studying various graphs defined by polynomials over finite fields, such as Paley graphs, Paley sum graphs, and graphs associated with Diophantine tuples and their generalizations from number theory. As an application, we provide new lower bounds on the clique number and independence number of general quasi-random graphs. In particular, we give a sufficient condition for the clique number of quasi-random graphs of order $n$ to be at least $(1-o(1))\log_{3.008}n$. Such a condition applies to many classical quasi-random graphs, including Paley graphs and Paley sum graphs, as well as some new Paley-like graphs we construct. If time permits, we also discuss some problems of diophantine tuples arising from number theory, which is our original motivation.

This is joint work with Seoyoung Kim and Chi Hoi Yip.

Semin Yoo (유세민) gave a talk on an analogue of q-binomial coefficients at the Discrete Math Seminar

On July 20, 2021, Semin Yoo (유세민) from the University of Rochester gave a talk on an analogue of q-binomial coefficients, counting subspaces having the Euclidean quadratic form, and its applications at the Discrete Math Seminar. She will move to KIAS next month as a postdoc. The title of her talk was “Combinatorics of Euclidean spaces over finite fields“.

Semin Yoo (유세민), Combinatorics of Euclidean spaces over finite fields

$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients, denoted by $\binom{n}{k}_{q}$, which give the number of $k$-dimensional subspaces in $\mathbb{F}_{q}^{n}$. When $q$ goes to $1$, this reverts to the binomial coefficients which measure the number of $k$-sets in $\left [ n \right ]$.

In this talk, we add one more structure in $\mathbb{F}_{q}^{n}$, which is the Euclidean quadratic form: $\text{dot}_{n}:=x_{1}^{2}+x_{2}^{2}+\cdots+x_{n}^{2}$. It turns out that the number of quadratic subspaces of Euclidean type in $(\mathbb{F}_{q}^{n},\text{dot}_{n})$ can be described as the form of the analogue of binomial coefficients. The main goal of this talk is to define the dot-analogues of the binomial coefficients and to study related combinatorics. No prior knowledge about the theory of quadratic form is required.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.