Adjacency polynomial of a graph and combinatorial Nullstellensatz
Chromatic polynomial, k - critical graphs
Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture
이거라는데 뭘 다루는지 감도 안오네요 ㅠㅠ
Chromatic polynomial, k - critical graphs
Gallai-Roy theorem, Acyclic coloring, Hadwiger's conjecture
이거라는데 뭘 다루는지 감도 안오네요 ㅠㅠ
퀸세정은 사랑입니다!!! - dc official App
Coloring 위주를 다룰거 같네. Nullstellensatz 소개하는 이유는 alon-tarsi 정리 증명하려고 하는거 같고
Combinatorial nullstellensatz는 조합론에서 사용되는 polynomial method 중에서 가장 기본적인 녀석 중 하나고 많은 응용이 있음. Graph coloring에도 응용되는데, 대표적인 예가 Alon-Tarsi 정리이고, 나열한 주제들이 모두 coloring에 관련된걸 보면 아마 이걸 다룰듯.
Hadwiger conjecture는 4색정리보다 더 강한 내용을 담은 conjecture인데, 전형적인 노답 conjecture 중 하나라서 아주 특별한 경우들만 증명된거라서 어떤식으로 수업을 진행할지 감이 안오는데, 아마 내 예상엔 추측 소개하고 Wagner 정리 (K5에 대한 conjecture와 4색정리가 동치) 정도만 보이고 끝낼것 같다
관련해서 제대로 찾아보려면 어떤 걸 보면 될까요? - dc App
https://m.tau.ac.il/~nogaa/PDFS/null2.pdf
Alon의 survey
감사합니다! - dc App
그래프이론전공 왜 하나요? - dc App
Wagner 정리는 이 survey의 Theorem 1.3이고 여기에 증명이 있는데
https://people.math.gatech.edu/~thomas/PAP/bcc.pdf
단점은 좀 강한 정리인 splitter thm을 썼음. 노가다로 안쓰고 우회할수 있는데 직접 시도해보는것도 괜찮음
오호. 쉽진 않겠지만 연습문제삼아 풀어보도록 하겠습니다! - dc App