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-M 問題の評価基準として適切でなくなったと結論付けています。
Erd\H{o}s Matching (Conjecture) Theorem
本論文は、極値組合せ論における長年の未解決問題であったエルデシュのマッチング予想を証明したものである。
Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers
この論文は、有限体上のベクトル関数のほとんどが自明な拡張アフィン安定化群を持つことを証明し、これにより EA 同値性のクラス数が単純な推定値に漸近的に一致することや、ランダムな関数が EA 同値となる確率が超指数関数的に小さいことを示し、暗号原語設計におけるランダムサンプリング戦略の有効性を裏付けている。
On the Multi-Commodity Flow with convex objective function: Column-Generation approaches
この論文は、リンクの混雑度に応じて凸関数的に増加するコストを最小化する容量制約付き多商品フロー問題（分割可能および非分割可能の両方）に対し、凸関数やブラックボックス関数にも対応できる列生成法に基づく効率的な最適化アルゴリズムを提案するものである。
Circular chromatic index of small graphs
本論文は、最大次数が 4 から 6 の小規模なグラフおよび多重グラフの円環色指数を体系的に決定し、特定の値を持つ無限族を構成することで、円環色指数がの直下に存在しないとする「上部ギャップ予想」の辺連結性に関する変種を反証するものである。
Domination polynomial of co-maximal graphs of integer modulo ring
この論文は、整数剰余環 の共極大グラフの支配多項式を研究し、特定の に対する明示的な公式、一般 における構造式、および支配根の性質に関する結果を導出しています。
Hierarchical threshold structure in Max-Cut with geometric edge weights
本論文は、幾何学的な重み付けがなされた完全グラフ上の Max-Cut 問題において、重み比 の値に応じて最適解が異なる「孤立カット」の階層的な閾値構造を厳密に解析し、 の場合にこれらの孤立カットが全カットの中で最適であるという仮説を提唱しています。
Degree-Based Weighted Adjacency Matrices: Spectra, Integrality, and Edge Deletion Effects
本論文は、完全多部グラフの重み付き隣接行列のスペクトルと整数性、および辺の削除がグラフのエネルギーやスペクトル半径に与える影響を解析し、先行研究の誤りを修正するとともに未解決問題を解決する。
Some polynomial classes for the acyclic orientation with parity constraint problem
本論文は、部分集合 T の頂点における入次数の偶奇を制約する有向グラフの非巡回化問題について、3 つの必要条件を特定し、これらが十分条件となる多項式時間解法可能なグラフクラスを階層的に分類・特徴付けるとともに、その包含関係を証明する。
On Supports for graphs of bounded genus
この論文は、有界種数のホストグラフ上で定義された交差自由な連結部分グラフからなるハイパーグラフ（およびその双対や交差ハイパーグラフ）に対して、同様に有界種数のサポートグラフが存在することを示し、平面領域に対する既知の結果を一般化するとともに、有界種数面上のハイパーグラフに関するパッキング・カバリング問題や彩色問題への統一的な分析手法を提供するものである。
Edge densities of drawings of graphs with one forbidden cell
この論文は、特定のセルタイプを含まないグラフ描画（-free 描画）における辺密度の上限と下限を、描画様式やグラフの種類のあらゆる組み合わせに対して体系的に研究し、ほとんどのセルタイプにおいて辺密度が に対して線形か超線形になることを示すとともに、単純グラフの描画可能性に関する完全な特徴付けや準平面描画の新たな下限値の改善など、既存の結果を大幅に拡張・精緻化しています。
Localization: A Framework to Generalize Extremal Graph Problems
本論文は、極値グラフ理論の問題を局所的に定式化して集約する「局所化」という枠組みを用いて、最大次数や経路長が制限されたグラフにおける部分グラフの数の上限を改善し、極値グラフの構造的特徴を明らかにするものである。
When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure
この論文は、葉の数が の 個の系統樹が共有する共通構造がほとんどない場合、それらを表現するために必要なリチキュレーション（交差）の数が、 の値に応じて に近い値、あるいは のオーダーに達することを示し、多数の系統樹を表現するネットワークの複雑性の下限を明らかにするものである。
Complexity of Linear Subsequences of -Automatic Sequences
この論文は、-自動列の線形部分列の複雑性を研究し、自動機構築における状態数やランタイムの分析、Zantema と Bosma による最近の問いへの解答、および内部列の部分語複雑性との関係性を明らかにするものです。
An Upper Bound for the Double Domination Number in Maximal Outerplanar Graphs
本論文は、最大外平面グラフにおける重複支配数の上限が であるという既知の仮説について、以前の証明が不完全であった点を指摘し、その結果の正当性を完全な証明によって確立したことを述べています。
Explicit Formulas and Unimodality Phenomena for General Position Polynomials
本論文は、グラフの一般位置集合を数える多項式について完全多部グラフやコロナグラフなどの特定のグラフクラスに対する明示的な式を導出し、その対数凹性や単峰性に関する性質を調べ、部分サイズが小さい場合の成立と大きい場合の反例を示すとともに、一般位置多項式の単峰性が多くの自然なグラフクラスで保持されることを証明しています。
The Unit Gap: How Sharing Works in Boolean Circuits
この論文は、AND と NOT を用いたブール回路において、回路サイズと論理式サイズの差が常に 0 または 1 であることを証明し、その差が 1 となる条件や共有の必要性に関する厳密な定理を確立したものである。