Inequalities Involving Core, Corona, and Critical Sets in General Graphs
이 논문은 일반 그래프에서 최대 독립 집합, 코어, 코로나, 커널, 다이아뎀 및 핵과 관련된 부등식을 증명하여 레빗-만드레스쿠 (2014) 의 추측을 포함하는 두 가지 최근의 추측을 확인하고, 이를 통해 이들 개념 간의 부등식 체인을 제시합니다.
🔢 Category
math.CO
345 편의 논문
On the minimum degree of minimal --factor critical -planar graphs
이 논문은 -플래너 그래프에 대해 모든 최소 --인자 임계 그래프의 최소 차수가 이상 이하라는 추측이 성립함을 증명하여, 특히 평면 그래프에 대한 해당 추측을 해결했습니다.
Optimising two-block averaging kernels to speed up Markov chains
이 논문은 두 블록 평균화 커널을 최적화하여 마코프 체인의 혼합 속도를 가속화하는 문제를 다루며, KL 발산과 프로베니우스 거리를 기준으로 한 최적 분할을 구조적 조합 최적화 문제로 재해석하고 효율적인 근사 알고리즘을 제안합니다.
Optimal Spectral Bounds for Antipodal Graphs
이 논문은 지름이 1 이하인 평면 내 점 집합에서 거리 내의 이웃 쌍 수와 $1-\varepsilon\varepsilon^{3/4+o(1)}\varepsilon^{1/2+o(1)}$ 차수임을 증명하여, 추측된 점근적 하한을 다항 로그 인자 내에서 달성함을 보여줍니다.
Aldous property for full-flag Johnson graphs
이 논문은 풀-플래그 존슨 그래프의 스펙트럼 갭이 점 안정자 균등 분할에서 유도된 슈레이 몫과 동일함을 증명하여 황 (Huang), 황 (Huang), 치오바 (Cioabă) 가 제기한 두 가지 추측을 확인하고 풀-플래그 존슨 그래프에 대한 알도스 (Aldous) 유형의 스펙트럼 갭 현상을 입증했습니다.
Additive Subtraction Games
이 논문은 1982 년 'Winning Ways'에 소개되었으나 완전한 증명이 부재했던 가법 뺄셈 게임의 원제 2 차(regime) 에 대한 P-위치에 대한 폐쇄형 공식을 검증하고, 각 nim-값 수열이 고전적인 P-위치의 선형 이동 위에 존재함을 증명합니다.
A new lower bound for the kissing number in 19 dimensions
이 논문은 5-천공 확장 이진 골레이 코드 내부의 명시적 비선형 이진 코드를 Cohn 과 Li 의 홀수 부호수 구성과 결합하여 19 차원에서의 키싱 수 하한을 기존보다 256 증가시킨 11,948 로 개선했음을 증명합니다.
The Ricci flow with prescribed curvature on graphs
이 논문은 유한 그래프에서 린 - 루 - 야우 리치 곡률을 기반으로 한 곡률 지정 리치 흐름의 존재성과 유일성을 증명하고, 순환 길이 (girth) 가 6 이상인 그래프에서 목표 곡률이 달성 가능한 경우 지수적으로 수렴함을 보이며, 특히 상수 곡률 가중치의 존재 조건을 제시함으로써 Chow 와 Luo 가 제기한 2 차원 조합적 리치 흐름에 관한 질문 2 번에 대해 긍정적으로 답변합니다.
A note on Ramsey numbers for minors
이 논문은 가지 색으로 에지를 색칠한 완전 그래프에서 개의 정점을 가진 클릭을 마이너로 가지는 단색 그래프가 존재하도록 보장하는 최소 정점 수인 라미지 수 에 대한 점근적 상한과 하한을 제시하여, 특히 2색 경우와 일반 색 경우에 대한 정확한 점근적 행동을 규명했습니다.
M-Polynomial of Product Graphs
이 논문은 직교, 직접, 강, 사전, 대칭차, 부인, 시에르핀스키 곱 등 다양한 그래프 곱에 대해 M-다항식을 계산하는 명시적이고 간결한 공식을 제시하여, 그래프 구성 하에서 정점 차수 상호작용이 어떻게 전파되는지에 대한 통합된 구조적 설명을 제공합니다.
Maximum Inverse Sum Indeg Index of Trees and Unicyclic Graphs with Fixed Diameter
이 논문은 그래프 변환 기법을 활용하여 고정된 지름을 갖는 나무와 단사이클 그래프에서 역합인덱스 (ISI) 의 최댓값을 결정하고, 각각의 경우에 최댓값을 달성하는 극단적 그래프 구조를 규명합니다.
Anti-Ramsey forbidden poset problems
이 논문은 포셋 의 무지개색 약한 또는 강한 복사본을 포함하지 않는 $2^{[n]}\mathrm{ar}(n,P)\mathrm{ar^*}(n,P)\mathrm{La}(n,P)\mathrm{ar^*}(n,P)$의 점근적 값을 결정합니다.
Central limit theorems for high dimensional lattice polytopes: symmetric edge polytopes
이 논문은 Erdős–Rényi 무작위 그래프에서 생성된 고차원 대칭 엣지 다면체의 모서리 수와 단모듈 삼각분할에 대한 기댓값 및 분산의 점근적 성질을 규명하고, 이산 Malliavin–Stein 방법을 활용하여 중심극한정리를 증명함으로써 무작위 격자 다면체에 대한 최초의 분포적 극한 정리를 제시합니다.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
이 논문은 정수값 대칭 서모듈러 함수에서 특정 값 를 갖는 모든 컷을 다항식 크기의 표현으로 효율적으로 인코딩하는 방법을 제시하고, 이를 통해 고정된 에 대해 다항 시간 내에 특정 크기 조건을 만족하는 집합을 찾는 알고리즘을 제안합니다.
On the leading and penultimate leading coefficients for NRS(2) applied to a cubic polynomial
이 논문은 3 차 다항식에 NRS(2) 를 적용했을 때 발생하는 오차항의 최고차항 및 차고차항 계수가 과 에 대한 양계수 다항식임을 증명하여 기존 연구의 증명을 간소화하고 확장했습니다.
The complexity of finite smooth words over binary alphabets
이 논문은 이진 알파벳을 사용하는 유한 매끄러운 단어 (f-smooth words) 의 복잡도가 로 성장한다는 싱 (Sing) 의 추측에 대한 진전을 이루었으며, 특히 짝수 알파벳의 경우 이를 증명하고 모든 이진 알파벳에 대해 하한을 증명하며 홀수 알파벳에 대한 상한을 개선했습니다.
Vertex Dismissibility and Scalability of Simplicial Complexes
이 논문은 정점 해체 가능성과 쉘러빌리티를 일반화한 '정점 해체 가능' 및 '확장 가능' 심플리셜 복합체를 도입하고, 이를 대수적 이상과 연결하여 위상적·호몰로지적 위계 구조를 규명하고 다양한 고전적 정리를 포괄하는 완전한 골격적 특성을 제시합니다.
Pairwise Negative Correlation for Uniform Spanning Subgraphs of the Complete Graph
이 논문은 완전 그래프의 연결된 스패닝 서브그래프, 개의 성분을 가진 숲, 그리고 초과 를 가진 연결된 스패닝 서브그래프와 같은 세 가지 자연스러운 집합에 대한 균일 확률 측도가 이 충분히 클 때 쌍별 음의 상관관계 (p-NC) 성질을 만족함을 증명합니다.
Extremal problems in uniformly dense hypergraphs and digraphs
이 논문은 방향 그래프의 극단적 문제와 3-초그래프의 균일 터란 밀도 사이의 새로운 연결을 확립하여 특정 밀도 값을 갖는 3-초그래프에 대한 검증 가능한 조건을 제시하고, $1/24/27$과 같은 값에 대한 새로운 예시를 구성하며 기존 결과를 간결하게 증명합니다.
Combinatorial perspectives on identities for partitions with distinct even parts
이 논문은 고유의 짝수 부분을 갖는 분할에 대한 새로운 조합론적 관점을 제시하여 부호 분할 및 이색 분할과의 연결을 통해 여러 분할 항등식을 유도하고, 각 결과에 대한 쌍사증명을 구성함으로써 Andrews-El Bachraoui 와 Kılıç-Kurşungöz 이 제기한 조합론적 문제를 부분적으로 해결합니다.