[일반] 머수적 그래프 말고 해석적 그래프론 같은 것도 있음??

[wlltmpr..(wlltmprdclvr6)]

해석사랑

- dc official App

[딴따라(125.134)]

막 확률론적 방정식 같은걸로 PPAP 춰서 하한 상한 구하는거임 에르되시 같은 사람이 할만한 발상이네

[익명(211.212)]

Random graph, Graph limits

[익명(211.212)]

Random graph 이론에서는 특정 그래프 클래스 내 원소들에 대해서 확률을 부여해주고, 그 확률이 커지면 대체적으로 (almost surely) 내부의 원소들이 어떤 성질을 갖는지 관찰하는데.. 예를 들어서 모든 n개의 정점을 갖는 그래프에 대해서 각 edge에 대해서 존재할 확률 p로 주고 모든 nC2개의 edge에 대해서 그 사건을 independent하게 만들어줄 때 얻어지는 대표적인 Erdos-Renyi 모델 G(n,p)가 있고..

[익명(211.212)]

성질을 관찰하는 것으로는 예를 들어서 p를 어떻게 주느냐에 따라서 G(n,p)의 그래프들이 연결이 될것인가? 같은 질문을 던질수 있고, 단적으로 p >> log(n)/n 정도면 n이 커지면 G(n,p)의 그래프가 연결일 확률이 1로 수렴하고, p << log(n)/n이면 n이 커질때 G(n,p)의 그래프가 연결이 아닐 확률이 1로 수렴하게 됨. 이런 식으로 모든 nontrivial monotone property에는 어떤 threshold p*가 있어서, p/p* = w(1)이면 G(n,p)가 almost surely하게 그 성질을 갖게 되고 p/p* = o(1)이면 G(n,p)가 almost surely하게 그 성질을 갖지 않게 됨. (Bollobas-Thomason)

[익명(211.212)]

어떤 p에 따라서 G(n,p)의 개형의 dynamics가 어떻게 변하는지를 다루는 seminal한 결과로는 Erdos와 Renyi의 phase transition에 관한 1960년대 결과가 있고.. G(n,p) 외에도 상황에 따라서 다루는 여러 model이 있음. (e.g. regular random graph들의 클래스를 다루는데 유용한 Bollobas의 configuration model이 있음) 관련 survey로는 Wormald의 것이 있음 :
https://www.math.uwaterloo.ca/~nwormald/papers/regsurvey.pdf

[익명(211.212)]

실제로 이산수학(discrete math)과 연속수학(continuous math)에서 다루는 대상은 다른 경우가 많고 서로 연관이 있지만 다루는 방법론도 다른 경우가 많은데, 예를 들어서 이산수학의 방법론을 이용해서 연속수학의 문제를 해결할 수 있나? 반대로는 연속수학의 방법론을 이용해서 이산수학의 문제를 해결할 수 있을까? 의 생각을 학자들이 많이 하게 됨. (대표적으로 Tao의 이에 관한 video 참고 :
https://www.youtube.com/watch?v=IS9fsr3yGLE)

[익명(211.212)]

Graph limit 이론에서는 그래프들의 모임에 어떤 metric을 주어서 그것의 limit들의 모임에 대해서 연구함. Limit들의 모임에 대해서 이것저것 여러 성질을 규명하기도 하지만, 위의 discrete vs continuous의 관점에서 볼 때, limit들의 공간 (continuous) 에서 어떤 성질을 규명함으로써 그래프들의 공간 (discrete) 의 유의미한 정리를 만들어낼 수 있는가? 의 방향으로도 연구가 되고 있음.

[익명(211.212)]

이에 대한 예시로는 dense graph들의 limit들의 공간인 Graphon들의 모임이 있고, 이 Graphon들의 모임이 compact metric space를 만든다는 사실을 이용해서 dense graph들의 Szemeredi regularity lemma를 보일수 있지.

[익명(175.223)]

님 대체 정체가 머에요

[익명(211.212)]

위의 설명을 보기에는 random graph 이론이 그냥 특정 확률분포 하에서 랜덤그래프의 동향을 분석하는것에 그칠것 같지만, 예를 들어서 다른 조합론이나 그래프 이론의 결과물들을 얻는데에도 요긴하게 쓰이긴 함. 요새 학자들이 자주 써먹는 방식은 어떤 원하는 조합적 구조를 구성할 때, random한 방법론을 사용해서 원하는 구조에 '가까운' 구조를 습득한 뒤, absorbing techinique 같은 여러 다른 조합적 방법론을 이용해서 그 '가까운' 구조를 원하는 완전한 구조로 변형시키는 방식을 사용하여 문제를 해결함.

[익명(211.212)]

이 때 원하는 구조에 '가까운' 구조를 습득하고 거기에 뭔가를 덧붙여서 완전한 구조로 바꾸려면, 일반적으로 완전한 구조에 가까운 것 외에도 별도의 robust한 다른 성질들을 지니게끔 해야하는데, 그럴려면 결국 random한 구조가 특정 확률분포 하에서 어떤 성질을 w.h.p (with high probability) 가지는가? 에 관한 대답이 있어야 하고, 확률론적 조합론이 개입될 수밖에 없음. 아래 로또 문제 글의 답변에서 언급한 Keevash의 design의 존재성에 관한 논문에서도 이것과 유사한 방법론을 사용하고 (물론 가까운 구조를 완전한 구조로 변모시킬때 마무리짓는 방식은 살짝 다를수 있음), Kalai의 survey에 의하면 조합론 뿐만 아니라 다른 분야에서도 이런 방법론이 조금씩 대두됨

[익명(211.212)]

다만 이런 방식의 유일한 단점이라면, 보통 random한 구조가 w.h.p. 어떤 성질을 가진다는것에 대한 정리들은 그 구조가 충분히 클때 (예를 들어 위 댓글에서 말한 G~G(n,p)이고 p >> log n / n일때 n이 충분히 커지면 G가 연결일 확률이 1로 수렴한다) 성립하는 것이기 때문에, 결국 원하는 조합적 구조가 충분히 클때만 성립한다는 것이지 (즉 구조의 size가 작으면 아무것도 말해주지 않음). 이것은 무작위적으로 보이는 대상도 충분히 많이 모이면 결국 규칙성을 가진다는 Szemeredi의 철학하고 어느정도 일맥상통하는 방향이기도 하지. 그리고 확률론적인 방법론을 쓰다보니 방법론이 constructive하지 않다는 단점이 있음.

[ㅅㄲㅁㅇ(as1392)]

허믜 싀펄;

[익명(121.144)]

진짜 저런사람보면 개미같이느껴진다

[코세(rationnel)]

댓글 개추없나