EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Random matchings in linear hypergraphs

Hyunwoo Lee

Forum of Mathematics, Sigma · 2026 · 14

DOI: 10.1017/fms.2026.10253 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Forum of Mathematics, Sigma, online erschienen am 29.07.2026. Verfasst von Hyunwoo Lee. Die Arbeit nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Research Foundation of Korea, Institute for Basic Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

For a given hypergraph H and a vertex v ∈ V ( H ) $v\in V(H)$ v element of upper V left parenthesis upper H right parenthesis , consider a random matching M chosen uniformly from the set of all matchings in H . $H.$ upper H period In 1995 , $1995,$ 1995 comma Kahn conjectured that if H is a d -regular linear k -uniform hypergraph, the probability that M does not cover v is ( 1 + o d ( 1 ) ) d − 1 / k $(1 + o_d(1))d^{-1/k}$ left parenthesis 1 plus o Subscript d Baseline left parenthesis 1 right parenthesis right parenthesis d Superscript negative 1 divided by k for all vertices v ∈ V ( H ) . $v\in V(H).$ v element of upper V left parenthesis upper H right parenthesis period This conjecture was proved for k = 2 $k = 2$ k equals 2 by Kahn and Kim in 1998. $1998.$ 1998 period In this paper, we disprove this conjecture for all k ≥ 3. $k \geq 3.$ k greater than or equals 3 period For infinitely many values of d , $d,$ d comma we construct d -regular linear k -uniform hypergraph H containing two vertices v 1 $v_1$ v 1 and v 2 $v_2$ v 2 such that P ( v 1 ∉ M ) = 1 − ( 1 + o d ( 1 ) ) d k − 2 $\mathcal {P}(v_1 \notin M) = 1 - \frac {(1 + o_d(1))}{d^{k-2}}$ script upper P left parenthesis v 1 not an element of upper M right parenthesis equals 1 minus StartFraction left parenthesis 1 plus o Subscript d Baseline left parenthesis 1 right parenthesis right parenthesis Over d Superscript k minus 2 Baseline EndFraction and P ( v 2 ∉ M ) = ( 1 + o d ( 1 ) ) d + 1 . $\mathcal {P}(v_2 \notin M) = \frac {(1 + o_d(1))}{d+1}.$ script upper P left parenthesis v 2 not an element of upper M right parenthesis equals StartFraction left parenthesis 1 plus o Subscript d Baseline left parenthesis 1 right parenthesis right parenthesis Over d plus 1 EndFraction period The gap between P ( v 1 ∉ M ) $\mathcal {P}(v_1 \notin M)$ script upper P left parenthesis v 1 not an element of upper M right parenthesis and P ( v 2 ∉ M ) $\mathcal {P}(v_2 \notin M)$ script upper P left parenthesis v 2 not an element of upper M right parenthesis in this H is best possible. In the course of proving this, we also prove a hypergraph analog of Godsil’s result on matching polynomials and paths in graphs, which is of independent interest.

Förderung

  • National Research Foundation of Korea
  • Institute for Basic Science

Zitieren

APA

Lee, H. (2026). Random matchings in linear hypergraphs. Forum of Mathematics, Sigma, 14. https://doi.org/10.1017/fms.2026.10253

Vancouver

Lee H. Random matchings in linear hypergraphs. Forum of Mathematics, Sigma. 2026;14. doi:10.1017/fms.2026.10253

BibTeX
@article{Lee2026,
  author = {Lee, Hyunwoo},
  title = {Random matchings in linear hypergraphs},
  journal = {Forum of Mathematics, Sigma},
  year = {2026},
  volume = {14},
  doi = {10.1017/fms.2026.10253}
}
Kostenlos starten →