Loading Events

« All Events

  • This event has passed.

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

June 18 Tuesday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)

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.


June 18 Tuesday
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Room B332
IBS (기초과학연구원) + Google Map


Sang-il Oum (엄상일)
View Organizer Website
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: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.