HYGENE: A Diffusion-based Hypergraph Generation Method
이 논문은 기존에 존재하지 않았던 딥러닝 기반의 초그래프 생성 방법론인 HYGENE 를 제안하며, 확산 모델을 활용해 이분 그래프 표현을 기반으로 국소적 확장을 통해 복잡하고 다양한 초그래프 구조를 효과적으로 생성하는 것을 목표로 합니다.
💻 Category
cs.DM
48 편의 논문
Rigidity of polytopes with edge length and coplanarity constraints
이 논문은 모서리 길이와 면의 평면성만 보존하는 새로운 다면체 강성 개념을 제시하여 3 차원에서 볼록 다면체가 일반적으로 강하다는 것을 증명하고, 고차원에서의 강성에 대한 추측과 향후 연구 과제를 제안합니다.
There is no prime functional digraph: Seifert's proof revisited
이 논문은 1971 년 랄프 사이퍼트가 증명했으나 최근까지 잊혀졌던 '소 함수성 방향 그래프의 부재'라는 결과를 현대적인 용어와 간결한 논증으로 재해석하여 제시합니다.
Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows
이 논문은 기존 TSPTW 벤치마크 인스턴스의 구조적 취약점을 간파하여 50 개 이상의 고객으로 구성된 모든 사례를 초단위로 해결하는 정밀 알고리즘을 제시함으로써, 해당 인스턴스들이 더 이상 문제의 난이도를 평가하거나 머신러닝 학습용 데이터셋으로 적합하지 않음을 경고합니다.
Erd\H{o}s Matching (Conjecture) Theorem
이 논문은 개의 원소로 이루어진 집합에서 개의 서로소인 부분집합을 포함하지 않는 -원소 부분집합들의 모임의 최대 크기에 대한 에르되시 (Erdős) 매칭 추측을 증명했습니다.
Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers
이 논문은 유한체 위의 벡터 함수 대부분이 자명한 확장 아핀 안정화군을 가지며, 이로 인해 확장 아핀 동치류의 수가 단순 추정치와 점근적으로 일치하고 무작위 함수가 동치일 확률이 극히 낮음을 증명하여 암호학적 원시 설계에 무작위 샘플링 전략이 유효함을 보여줍니다.
On the Multi-Commodity Flow with convex objective function: Column-Generation approaches
이 논문은 대역폭 제한에 따른 링크 비용의 증가를 고려한 볼록 목적 함수를 가진 다중 상품 흐름 문제를 해결하기 위해, 분할 가능 및 분할 불가능 변형에 적용 가능한 컬럼 생성 기반의 효율적인 최적화 알고리즘을 제안합니다.
Circular chromatic index of small graphs
이 논문은 최대 차수가 4, 5, 6 인 작은 그래프와 다중 그래프의 원형 색수 (circular chromatic index) 를 체계적으로 규명하고, 이를 통해 '상한 갭 추측 (Upper Gap Conjecture)'의 에지 연결성 변형들을 반증하는 무한한 그래프 족을 구성합니다.
Domination polynomial of co-maximal graphs of integer modulo ring
이 논문은 정수 모듈로 의 환과 관련된 공최대 그래프의 지배 다항식을 연구하여, 특정 값에 대한 명시적 공식을 유도하고 그 단조성 및 로그 오목성을 증명하며, 일반적인 에 대한 구조적 표현과 지배 근의 경계를 제시합니다.
Hierarchical threshold structure in Max-Cut with geometric edge weights
이 논문은 기하급수적으로 감소하는 가중치를 가진 완전 그래프의 Max-Cut 문제에서 고립된 절단 (isolated cuts) 이 특정 임계값 구간에서 최적 해가 되며, 인 경우 전역 최적 해가 될 것이라는 가설을 제시하고 이를 수학적으로 증명 및 검증합니다.
Degree-Based Weighted Adjacency Matrices: Spectra, Integrality, and Edge Deletion Effects
이 논문은 완전 k-분할 그래프의 가중 인접 행렬 스펙트럼과 적분성을 규명하고, 간선 삭제에 따른 에너지 및 스펙트럼 반경 변화에 관한 기존 연구의 오류를 수정하고 미해결 문제를 해결하며, 왕관형 k-분할 그래프의 가중 스펙트럼을 계산합니다.
Some polynomial classes for the acyclic orientation with parity constraint problem
이 논문은 무순환 방향성 그래프에서 특정 정점 집합에 대한 홀수 차수 조건을 만족하는 방향성 할당 문제의 복잡성을 분석하고, 세 가지 필요 조건이 충분 조건이 되는 다항식 시간 해결 가능한 그래프 클래스들을 정의하며, 이러한 클래스 간의 포함 관계를 규명하고 직교곱 경로 및 사이클에 대한 해의 존재성을 특징짓는 구성적 알고리즘을 제시합니다.
On Supports for graphs of bounded genus
본 논문은 유한한 종수 (genus) 를 가진 호스트 그래프와 교차 자유 (cross-free) 조건을 만족하는 연결 부분그래프 집합으로 정의된 교차 초그래프에 대해, 역시 유한한 종수를 가지는 서포트를 구성할 수 있음을 증명하여 평면 서포트 구성 결과의 일반화를 제공하고 포장 및 커버링 문제와 초그래프 색칠 문제에 대한 통합 분석을 제시합니다.
Edge densities of drawings of graphs with one forbidden cell
이 논문은 특정 셀 유형이 금지된 그래프 그림의 최대 간선 수를 다양한 그림 스타일과 그래프 유형에 대해 체계적으로 분석하여, 대부분의 경우 간선 밀도가 선형 또는 초선형임을 증명하고 기존 하한을 개선하는 등 포괄적인 상하한 경계를 제시합니다.
Localization: A Framework to Generalize Extremal Graph Problems
이 논문은 국소화 (localization) 프레임워크를 활용하여 최대 차수나 경로 길이에 제한이 있는 그래프에서 -클릭 수에 대한 기존 상한을 개선하고, 이를 달성하는 극단적 그래프의 구조적 특성을 규명합니다.
When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure
이 논문은 개의 잎을 가진 개의 계통수가 거의 공통 구조를 공유하지 않을 때, 이를 표현하는 네트워크에 필요한 망입 (reticulation) 수가 상한과 거의 일치하는 하한을 가진다는 것을 증명하여, 여러 계통수를 표현하는 데 필요한 망입 수의 이론적 한계를 규명했습니다.
Complexity of Linear Subsequences of -Automatic Sequences
이 논문은 -자동화 수열의 선형 부분열과 내부 수열의 복잡성 간의 관계를 규명하고, Zantema 와 Bosma 의 최근 질문을 해결하며, Büchi 산술을 기반으로 한 자동화 구성의 상태 및 실행 시간 복잡성을 분석합니다.
An Upper Bound for the Double Domination Number in Maximal Outerplanar Graphs
이 논문은 Abd Aziz 등 이전 연구의 증명이 불완전했음을 지적하고, 최대 외평면 그래프의 이중 지배수가 이하임을 완전히 증명합니다.
Explicit Formulas and Unimodality Phenomena for General Position Polynomials
이 논문은 완전多部部 그래프와 코로나 그래프에 대한 일반 위치 다항식의 명시적 공식을 유도하고, 부분 크기 인 균형 완전多部部 그래프에서 로그 오목성과 단조성 (unimodality) 이 성립함을 증명하며 더 큰 에서는 반례가 존재함을 보여줍니다.
The Unit Gap: How Sharing Works in Boolean Circuits
이 논문은 AND-NOT 기저에서 부울 회로와 부울 식의 최소 크기 차이가 항상 0 또는 1 임을 증명하고, 이 차이가 1 인 경우 오직 하나의 팬아웃 2 게이트에 의한 공유 구조에서만 발생하며, 특정 변수 수 조건 하에서 공유가 불필요하거나 임계값을 갖는다는 일련의 정리들을 제시합니다.