LAUSR.org creates dashboard-style pages of related content for over 1.5 million academic articles. Sign Up to like articles & get recommendations!

Stability on Matchings in 3-Uniform Hypergraphs

Photo from wikipedia

Given a positive integer r , let $$[r]=\{1,\ldots ,r\}$$ [ r ] = { 1 , … , r } . Let n ,  m be positive integers such that… Click to show full abstract

Given a positive integer r , let $$[r]=\{1,\ldots ,r\}$$ [ r ] = { 1 , … , r } . Let n ,  m be positive integers such that n is sufficiently large and $$1\le m\le \lfloor n/3\rfloor -1$$ 1 ≤ m ≤ ⌊ n / 3 ⌋ - 1 . Let H be a 3-graph with vertex set [ n ], and let $$\delta _1(H)$$ δ 1 ( H ) denote the minimum vertex degree of H . The size of a maximum matching of H is denoted by $$\nu (H)$$ ν ( H ) . Kühn, Osthus and Treglown (2013) proved that there exists an integer $$n_0\in \mathbb {N}$$ n 0 ∈ N such that if H is a 3-graph with $$n\ge n_0$$ n ≥ n 0 vertices and $$\delta _1(H)>{n-1\atopwithdelims ()2}-{n-m\atopwithdelims ()2}$$ δ 1 ( H ) > n - 1 2 - n - m 2 , then $$\nu (H)\ge m$$ ν ( H ) ≥ m . In this paper, we show that there exists an integer $$n_1\in \mathbb {N}$$ n 1 ∈ N such that if $$|V(H)|\ge n_1$$ | V ( H ) | ≥ n 1 , $$\delta _1(H)>{n-1\atopwithdelims ()2}-{n-m\atopwithdelims ()2}+3$$ δ 1 ( H ) > n - 1 2 - n - m 2 + 3 and $$\nu (H)\le m$$ ν ( H ) ≤ m , then H is a subgraph of $$H^*(n,m)$$ H ∗ ( n , m ) , where $$H^*(n,m)$$ H ∗ ( n , m ) is a 3-graph with vertex set [ n ] and edge set $$E(H^*(n,m))=\{e\subseteq [n]: |e|=3 \text{ and } e\cap [m] \ne \emptyset \}$$ E ( H ∗ ( n , m ) ) = { e ⊆ [ n ] : | e | = 3 and e ∩ [ m ] ≠ ∅ } . The minimum degree condition is best possible.

Keywords: uniform hypergraphs; stability matchings; matchings uniform

Journal Title: Graphs and Combinatorics
Year Published: 2022

Link to full text (if available)


Share on Social Media:                               Sign Up to like & get
recommendations!

Related content

More Information              News              Social Media              Video              Recommended



                Click one of the above tabs to view related content.