Search

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [ABSTRACT FROM AUTHOR]

Let r \geq k \geq 2 and K(k) r,n denote the complete n-balanced r-partite k-uniform hypergraph, whose vertex set consists of r parts, each has n vertices, and whose edge set contains all the k-element subsets with no two vertices from one part. A decomposition of K(k) r,n is a partition of E(K(k) r,n). A perfect matching (resp., Hamilton tight cycle) decomposition of K(k) r,n is a decomposition of K(k) r,n into perfect matchings (resp., Hamilton tight cycles). In this paper, we prove that if k | n (resp., 2 - k and k | n), then K(k) k+1,n (resp., K(k) k+2,n) has a perfect matching decomposition. We also prove that for any integer k \geq 2, K(k) k+1,n has a Hamilton tight cycle decomposition. In all cases, we use constructive methods involving number theory. In fact, we confirm two conjectures proposed by Zhang, Lu, and Liu [Appl. Math. Comput., 386 (2020), 125492]. [ABSTRACT FROM AUTHOR]

M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687{694] that a bipartite digraph of minimum out-degree at least 3 contains two vertex disjoint directed cycles of different lengths. In this paper, we disprove this conjecture. Further, we classify strong tournaments and strong bipartite tournaments of minimum out-degree 3 without two vertex disjoint directed cycles of different lengths. [ABSTRACT FROM AUTHOR]

Given a graph H, the Tur'an number ex(n,H) is the largest number of edges in an Hfree graph on n vertices. We make progress on a recent conjecture of Conlon, Janzer, and Lee [More on the Extremal Number of Subdivisions, arXiv:1903.10631v1, 2019] on the Tur'an numbers of bipartite graphs, which in turn yields further progress on a conjecture of Erdos and Simonovits [Combinatorica, 1 (1981), pp. 25-42]. Let s, t, k = 2 be integers. Let Kk s,t denote the graph obtained from the complete bipartite graph Ks,t by replacing each edge uv in it with a path of length k between u and v such that the st replacing paths are internally disjoint. It follows from a general theorem of Bukh and Conlon [J. Eur. Math. Soc. (JEMS), 20 (2018), pp. 1747-1757] that ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Conlon, Janzer, and Lee recently conjectured that for any integers s, t, k = 2, ex(n,Kk s,t) = O(n1+ 1k - 1 sk). Among many other things, they settled the k = 2 case of their conjecture. As the main result of this paper, we prove their conjecture for k = 3, 4. Our main results also yield infinitely many new so-called Tur'an exponents: rationals r ? (1, 2) for which there exists a bipartite graph H with ex(n,H) = T(nr), adding to the lists recently obtained by Jiang, Ma, and Yepremyan [On Tur'an Exponents of Bipartite Graphs, arXiv:1806.02838, 2018], by Kang, Kim, and Liu [On the Rational Tur'an Exponent Conjecture, arXiv:1811.06916, 2018], and by Conlon, Janzer, and Lee. Our method builds on an extension of the Conlon-Janzer-Lee method. We also note that the extended method also gives a weaker version of the Conlon-Janzer-Lee conjecture for all k = 2. [ABSTRACT FROM AUTHOR]