On some problems concerning the commonality of graphs Sejin Ko
- Title
- On some problems concerning the commonality of graphs Sejin Ko
- Other Titles
- 그래프의 commonality와 연관된 문제들에 대한 연구
- Author
- 고세진
- Alternative Author(s)
- Sejin Ko
- Advisor(s)
- 권오정
- Issue Date
- 2024. 2
- Publisher
- 한양대학교 대학원
- Degree
- Master
- Abstract
- A graph $H$ is \emph{common} if the number of monochromatic copies of $H$ in a 2-edge-colouring of the complete graph $K_n$ is asymptotically minimised by the random colouring. Classifying common graphs is a wide-open problem. However, we make progress in different directions.
We prove that, given $k,r>0$, there exists a $k$-connected common graph with chromatic number at least $r$. The result is built upon the recent breakthrough of Kr\'a\v{l}, Volec, and Wei who obtained common graphs with arbitrarily large chromatic number and answers a question of theirs. Additionally, we prove that there exists a graph with even girth which is not density common. Based on the local variant of Sidorenko's conjecture, we prove that if $H_1$ has an even girth, there exist $H_2$ and $p$ such that $(H_1,H_2)$ is $(p,1-p)$-common.
- URI
- http://hanyang.dcollection.net/common/orgView/200000720696https://repository.hanyang.ac.kr/handle/20.500.11754/188579
- Appears in Collections:
- GRADUATE SCHOOL[S](대학원) > MATHEMATICS(수학과) > Theses (Master)
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML