기초과학연구원 이산수학그룹
On June 18, 2024, Semin Yoo (유세민) from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on a generalization of Paley graphs and the quasi-randomness. The title of her talk was “Paley-like quasi-random graphs arising from polynomials“.
The IBS Discrete Mathematics Group welcomes Dr. Semin Yoo (유세민), a new research fellow at the IBS Discrete Mathematics Group, from April 1, 2024. She received her Ph.D. from the University of Rochester under the supervision of Prof. Jonathan Pakianathan. She is interested in combinatorics, discrete geometry, and number theory in finite fields.
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.
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“.
$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.