Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
홀수 사이클 그래프의 Shannon 용량에 대한 새로운 하한값을 제시합니다. LLM과의 상호작용을 통해 $C_7, C_{11}, C_{13}$ 그래프의 독립 집합을 구성함으로써 기존의 최선 하한값을 개선하는 성과를 거두었습니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv cs.AI의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기그래프 $G$의 Shannon 용량 $Θ(G)$는 노이즈가 있는 채널을 통해 오류 없이 정보를 전송할 수 있는 최대 속도를 정량화합니다. 이는 임의의 $d$에 대해 $α(G^d)^{1/d}$에 의해 하한이 결정되며, 여기서 $α(G^d)$는 $G$의 $d$차 강한 거듭제곱 (strong power)의 독립수 (independence number)입니다. 우리는 $C_7^{10}$에서 크기 $134753$, $C_{11}^{6}$에서 $21909$, 그리고 $C_{13}^{6}$에서 $62530$인 독립 집합 (independent sets)을 구성하여, 이 그래프들의 Shannon 용량에 대해 알려진 최선의 하한값을 $Θ(C_7) \geq 134753^{1/10} > 3.258020$, $Θ(C_{11}) \geq 21909^{1/6} > 5.289773$, 그리고 $Θ(C_{13}) \geq 62530^{1/6} > 6.300109$로 개선하였습니다. 또한 우리는 Shannon 용량 하한값은 개선하지 않지만, 여러 개별 홀수 사이클의 강한 거듭제곱에 대한 독립수의 최선 하한값들도 개선하였습니다. 이러한 구성들은 거대 언어 모델 (Large Language Model, LLM)과의 반복적인 상호작용을 통해 발견되었으며, 이는 명시적인 조합론적 구성 (combinatorial constructions)을 찾는 데 있어 LLM의 잠재력을 보여줍니다.