Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn $3$-uniform hypergraphs avoiding a cycle of length four
109
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this note we show that the maximum number of edges in a $3$-uniform hypergraph without a Berge cycle of length four is at most $(1+o(1))frac{n^{3/2}}{sqrt{10}}$. This improves earlier estimates by GyH{o}ri and Lemons and by Furedi and Ozkahya.
rate research
Read More
In this paper we show that the maximum number of hyperedges in a $3$-uniform hypergraph on $n$ vertices without a (Berge) cycle of length five is less than $(0.254 + o(1))n^{3/2}$, improving an estimate of Bollobas and GyH{o}ri. We obtain this result by showing that not many $3$-paths can start from certain subgraphs of the shadow.
There is a remarkable connection between the maximum clique number and the Lagrangian of a graph given by T. S. Motzkin and E.G. Straus in 1965. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we explore evidences that the Lagrangian of a 3-uniform hypergraph is related to the order of its maximum cliques when the number of edges of the hypergraph is in certain range. In particular, we present some results about a conjecture introduced by Y. Peng and C. Zhao (2012) and describe a combinatorial algorithm that can be used to check the validity of the conjecture.
Let K_4^3-2e denote the hypergraph consisting of two triples on four points. For an integer n, let t(n, K_4^3-2e) denote the smallest integer d so that every 3-uniform hypergraph G of order n with minimum pair-degree delta_2(G) geq d contains floor{n/4} vertex-disjoint copies of K_4^3-2e. Kuhn and Osthus proved that t(n, K_4^3-2e) = (1 + o(1))n/4 holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, t(n, K_4^3-2e) = n/4 when n/4 is odd, and t(n, K_4^3-2e) = n/4+1 when n/4 is even. A main ingredient in our proof is the recent `absorption technique of Rodl, Rucinski and Szemeredi.
The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi in cite{FF} conjectured that the $r$-graph with $m$ edges formed by taking the first $m$ sets in the colex ordering of ${mathbb N}^{(r)}$ has the largest Lagrangian of all $r$-graphs with $m$ edges. In this paper, we give some partial results for this conjecture.
A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in [7]. This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It has been also applied in spectral graph theory. Estimating the Lagrangians of hypergraphs has been successfully applied in the course of studying the Turan densities of several hypergraphs as well. It is useful in practice if Motzkin-Straus type results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus result to hypergraphs is false. We attempt to explore the relationship between the Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. In this paper, we give some Motzkin-Straus type results for r-uniform hypergraphs. These results generalize and refine a result of Talbot in [19] and a result in [11].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
