概要 - 非交差数の一般の厳しい制限（境界交差点数に対して厳しい）
タイトル
非交差数の一般の厳しい制限（境界交差点数に対して厳しい）
時間
2025-07-28 15:50:38
著者
{"Gaspard Charvy","Tomáš Masařík"}
カテゴリ
{math.CO,cs.CG,cs.DM,68R10,"G.2.2; F.2.2"}
リンク
http://arxiv.org/abs/2507.20937v1
PDF リンク
http://arxiv.org/pdf/2507.20937v1
概要
この論文は、グラフの交差点のない数の概念を調査しています。これは、グラフを交差点なしで表現するのに必要な最小の描画数を測定します。著者たちは、交差点のない数に対する新しい下界を提供し、これが密グラフに対して厳密で、すべてのグラフに対して拡張的に厳密です。 鍵となるアイデアは、グラフの単一の描画で交差点のないエッジができる最大の数である最大交差点のないサブグラフ数を使用することです。著者たちは、交差点のない数が最大交差点のないサブグラフ数の平方根以上であることを示し、この界の厳密性を示す構造を提供しました。 著者たちはまた、交差点のない数と他のグラフパラメータ、例えば交差点数や厚みとの関係について議論しました。彼らは、交差点のない数が厚みよりも低く、厚みの2倍よりも高いことを示しました。 この論文の主な貢献は以下の通りです： * 密グラフに対して厳密で、すべてのグラフに対して拡張的に厳密な交差点のない数の新しい下界。 * 密グラフに対するこの下界の厳密性を示す構造。 * 交差点のない数と他のグラフパラメータとの関係についての議論。 著者たちは、下界がすべてのグラフに対して厳密であるかどうかや、交差点のない数と厚みとの間に大きな差があるグラフが存在するかどうかなどのいくつかの未解決問題を提起しました。 全体として、この論文はグラフの可視化研究に重要な貢献を提供し、交差点のない数と他のグラフパラメータとの関係についての新しい洞察を提供しています。
推奨論文
「高階Busy Beaver関数」という言葉を日本語に翻訳すると、「高次元ベジー関数」となります。ただし、この用語は日本語の技術文献や論文ではあまり使用されていないため、専門的な文献や論文のタイトルや抽象で見られるかもしれません。以下は一般的な翻訳例です： 高次元ベジー関数 あるいは、より詳細に説明する場合は： 高階の忙しいバーバー関数 「高次元」とは、関数の次数を指し、数学や計算機科学の分野で「次数」という言葉はよく使用されます。一方、「ベジー関数」は、テオレム・ベジーの名前をとって命名された関数で、特定の計算機の動作を表す関数です。
時間までのイベントモデルを使用して、新しい長期的なUNOSデータセットを通じて心臓移植における待機リスト死亡率予測のベンチマーク評価
NoHumansRequired: 自動化高品質画像編集トリプルミニング
5Gにおけるアクティブ攻撃耐性：認証とキー合意の新しいアプローチ
ホモシフトのブロック貼り合わせクラスの不決定性
ベイズ双重降下
YOLOを使用したエッジFPGAのためのリアルタイム物体検出と分類
Steiner Orientationの構造パラメータ
顔認識精度に与える顔フィルタの影響を研究するための包括的評価枠組み
公開量子コンピュータ上での非侵襲的測定による時間の順序とLeggett-Garg不平等の検証