Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn hypergraph Lagrangians
174
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
It is conjectured by Frankl and Furedi that the $r$-uniform hypergraph 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$-uniform hypergraphs with $m$ edges in cite{FF}. Motzkin and Straus theorem confirms this conjecture when $r=2$. For $r=3$, it is shown by Talbot in cite{T} that this conjecture is true when $m$ is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for $r$-uniform hypergraphs. As an implication of this connection, we prove that the $r$-uniform hypergraph 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$-uniform graphs with $t$ vertices and $m$ edges satisfying ${t-1choose r}leq m leq {t-1choose r}+ {t-2choose r-1}-[(2r-6)times2^{r-1}+2^{r-3}+(r-4)(2r-7)-1]({t-2choose r-2}-1)$ for $rgeq 4.$
rate research
Read More
Frankl and Furedi conjectured in 1989 that the maximum Lagrangian, denoted by $lambda_r(m)$, among all $r$-uniform hypergraphs of fixed size $m$ is achieved by the minimum hypergraph $C_{r,m}$ under the colexicographic order. We say $m$ in {em principal domain} if there exists an integer $t$ such that ${t-1choose r}leq mleq {tchoose r}-{t-2choose r-2}$. If $m$ is in the principal domain, then Frankl-Furedis conjecture has a very simple expression: $$lambda_r(m)=frac{1}{(t-1)^r}{t-1choose r}.$$ Many previous results are focusing on $r=3$. For $rgeq 4$, Tyomkyn in 2017 proved that Frankl-F{u}redis conjecture holds whenever ${t-1choose r} leq m leq {tchoose r} -{t-2choose r-2}- delta_rt^{r-2}$ for a constant $delta_r>0$. In this paper, we improve Tyomkyns result by showing Frankl-F{u}redis conjecture holds whenever ${t-1choose r} leq m leq {tchoose r} -{t-2choose r-2}- delta_rt^{r-frac{7}{3}}$ for a constant $delta_r>0$.
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].
In 1965, Motzkin and Straus [5] provided a new proof of Turans theorem based on a continuous characterization of the clique number of a graph using the Lagrangian of a graph. This new proof aroused interests in the study of Lagrangians of r-uniform graphs. The Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. Sidorenko and Frankl-Furedi applied Lagrangians of hypergraphs in finding Turan densities of hypergraphs. Frankl and Rodl applied it in disproving Erdos jumping constant conjecture. In most applications, we need an upper bound for the Lagrangian of a hypergraph. Frankl and Furedi conjectured that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of $N^(r)$ has the largest Lagrangian of all r-uniform graphs with m edges. Talbot in [14] provided some evidences for Frankl and Furedis conjecture. In this paper, we prove that the r-uniform graph with m edges formed by taking the first m sets in the colex ordering of $N^(r)$ has the largest Lagrangian of all r-uniform graphs on t vertices with m edges when ${t choose r}-3$ or ${t choose r}-4$. As an implication, we also prove that Frankl and Furedis conjecture holds for 3-uniform graphs with ${t choose 3}-3$ or ${t choose 3}-4$ edges.
Let $mathcal{H}$ be a $t$-regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m times n$ incidence matrix of $mathcal{H}$ and let us denote $lambda =max_{v perp overline{1},|v| = 1}|Mv|$. We show that the discrepancy of $mathcal{H}$ is $O(sqrt{t} + lambda)$. As a corollary, this gives us that for every $t$, the discrepancy of a random $t$-regular hypergraph with $n$ vertices and $m geq n$ edges is almost surely $O(sqrt{t})$ as $n$ grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
Motzkin and Straus established a close connection between the maximum clique problem and a solution (namely graph-Lagrangians) to the maximum value of a class of homogeneous quadratic multilinear functions over the standard simplex of the Euclidean space in 1965. This connection provides a new proof of Turans theorem. Recently, an extension of Motzkin-Straus theorem was proved for non-uniform hypergraphs whose edges contain 1 or 2 vertices in cite{PPTZ}. It is interesting if similar results hold for other non-uniform hypergraphs. In this paper, we give some connection between polynomial programming and the clique of non-uniform hypergraphs whose edges contain 1, or 2, and more vertices. Specifically, we obtain some Motzkin-Straus type results in terms of the graph-Lagrangian of non-uniform hypergraphs whose edges contain 1, or 2, and more vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
