On the Largest Graph-Lagrangian of 3-Graphs with Fixed Number of Edges

被引:0
作者
Yanping Sun
Qingsong Tang
Cheng Zhao
Yuejian Peng
机构
[1] Hunan University,College of Mathematics
[2] Northeastern University,College of Sciences
[3] Institute of Jilin University,Mathematics School
[4] Indiana State University,Department of Mathematics and Computer Science
[5] Jilin University,School of Mathematics
来源
Journal of Optimization Theory and Applications | 2014年 / 163卷
关键词
Colex ordering; Left-compressed hypergraphs; Graph-Lagrangians of hypergraphs; Polynomial optimization; 05C35; 05C65; 65K10; 90C27; 94C15;
D O I
暂无
中图分类号
学科分类号
摘要
The Graph-Lagrangian of a hypergraph has been a useful tool in hypergraph extremal problems. In most applications, we need an upper bound for the Graph-Lagrangian of a hypergraph. Frankl and Füredi conjectured that the r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r}$$\end{document}-graph with m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m$$\end{document} edges formed by taking the first m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textit{m}$$\end{document} sets in the colex ordering of the collection of all subsets of N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb N}$$\end{document} of size r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${r}$$\end{document} has the largest Graph-Lagrangian of all r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r$$\end{document}-graphs with m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m$$\end{document} edges. In this paper, we show that the largest Graph-Lagrangian of a class of left-compressed 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3$$\end{document}-graphs with m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m$$\end{document} edges is at most the Graph-Lagrangian of the 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathrm 3 $$\end{document}-graph with m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m$$\end{document} edges formed by taking the first m\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m$$\end{document} sets in the colex ordering of the collection of all subsets of N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb N}$$\end{document} of size 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${3}$$\end{document}.
引用
收藏
页码:57 / 79
页数:22
相关论文
共 17 条
[1]  
Bomze IM(1997)Evolution towards the maximum clique J. Glob. Optim. 10 143-164
[2]  
Budinich M(2003)Exact bounds on the order of the maximum clique of a graph Discret. Appl. Math. 127 535-543
[3]  
Busygin S(2006)A new trust region technique for the maximum weight clique problem Discret. Appl. Math. 154 2080-2096
[4]  
Gibbons LE(1997)Continuous characterizations of the maximum clique problem Math. Oper. Res. 22 754-768
[5]  
Hearn DW(1941)On an extremal problem in graph theory (in Hungarian) Mat. Fiz. Lapok. 48 436-452
[6]  
Pardalos PM(1989)Extremal problems whose solutions are the blow-ups of the small Witt-designs J. Comb. Theory A 52 129-147
[7]  
Ramana MV(2013)A Motzkin–Straus type result for 3-uniform hypergraphs Graphs Comb. 29 681-694
[8]  
Turán P(1984)Hypergraphs do not jump Combinatorica 4 149-159
[9]  
Frankl P(2002)Lagrangians of hypergraphs Comb. Probab. Comput. 11 199-216
[10]  
Füredi Z(1965)Maxima for graphs and a new proof of a theorem of Turán Can. J. Math. 17 533-540