اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn hypergraph cliques and polynomial programming
173
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.$
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 t
he 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.
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 princi
pal 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$.
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.
If $G$ is a graph and $vec H$ is an oriented graph, we write $Gto vec H$ to say that every orientation of the edges of $G$ contains $vec H$ as a subdigraph. We consider the case in which $G=G(n,p)$, the binomial random graph. We determine the thresho
ld $p_{vec H}=p_{vec H}(n)$ for the property $G(n,p)to vec H$ for the cases in which $vec H$ is an acyclic orientation of a complete graph or of a cycle.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
