Tag: 이현우

By utilizing the recently developed hypergraph analogue of Godsil’s identity by the second author, we prove that for all $n\ge k\ge 2$, one can reconstruct the matching polynomial of an $n$-vertex $k$-uniform hypergraph from the multiset of all induced sub-hypergraphs on $\lfloor \frac{k-1}{k}n\rfloor +1$ vertices. This generalizes the well-known result of Godsil on graphs in 1981 to every uniform hypergraph. As a corollary, we show that for every graph $F$, one can reconstruct the number of $F$-factors in a graph under analogous conditions. We also constructed examples that imply the number $\lfloor \frac{k-1}{k}n\rfloor +1$ is the best possible for all $n\ge k\ge 2$ with $n$ divisible by $k$. This is joint work Donggyu Kim.

For a given hypergraph $H$ and a vertex $v\in V(H)$, consider a random matching $M$ chosen uniformly from the set of all matchings in $H.$ In $1995,$ 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}$ for all vertices $v\in V(H)$. This conjecture was proved for $k=2$ by Kahn and Kim in 1998. In this paper, we disprove this conjecture for all $k\ge 3.$ For infinitely many values of $d,$ we construct $d$-regular linear $k$-uniform hypergraph $H$ containing two vertices $v_1$ and $v_2$ such that $\mathcal{P}(v_1\notin M)=1–\frac{(1+o_d(1))}{d^{k-2}}$ and $\mathcal{P}(v_2\notin M)=\frac{(1+o_d(1))}{d+1}.$ The gap between $\mathcal{P}(v_1\notin M)$ and $\mathcal{P}(v_2\notin M)$ 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.

Dirac’s theorem determines the sharp minimum degree threshold for graphs to contain perfect matchings and Hamiltonian cycles. There have been various attempts to generalize this theorem to hypergraphs with larger uniformity by considering hypergraph matchings and Hamiltonian cycles.

We consider another natural generalization of the perfect matchings, Steiner triple systems. As a Steiner triple system can be viewed as a partition of pairs of vertices, it is a natural high-dimensional analogue of a perfect matching in graphs.

We prove that for sufficiently large integer $n$ with $n\equiv 1\text{ or }3(\mathrm{mod}6),$ any $n$-vertex $3$-uniform hypergraph $H$ with minimum codegree at least $(\frac{3+\sqrt{57}}{12}+o(1))n=(0.879\dots +o(1))n$ contains a Steiner triple system. In fact, we prove a stronger statement by considering transversal Steiner triple systems in a collection of hypergraphs.

We conjecture that the number $\frac{3+\sqrt{57}}{12}$ can be replaced with $\frac{3}{4}$ which would provide an asymptotically tight high-dimensional generalization of Dirac’s theorem.

For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let ${\delta }_{sub}(n,H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$, we asymptotically determined the value of ${\delta }_{sub}(n,H)$. More precisely, for every graph $H$ with at least one edge, there is a constant $1<{\xi }^{\ast }(H)\le 2$ such that ${\delta }_{sub}(n,H)=(1-\frac{1}{{\xi }^{\ast }(H)}+o(1))n$ if $H$ has a bipartite subdivision with two parts having different parities. Otherwise, the threshold depends on the parity of $n$.