Maxima for Graphs and a New Proof of a Theorem of Turán

DOI10.4153/CJM-1965-053-6zbMath0129.39902WikidataQ90158321 ScholiaQ90158321MaRDI QIDQ5338788

Theodore S. Motzkin, Ernst Gabor Straus

Publication date: 1965

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items

Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems, Existence of Evolutionarily Stable Strategies Remains Hard to Decide for a Wide Range of Payoff Values, A spinorial formulation of the maximum clique problem of a graph, Inequalities in probability theory and turán-type problems for graphs with colored vertices, Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata, A generalization of a Turán’s theorem about maximum clique on graphs, Minimizing the Number of Triangular Edges, On the Aα-spectral radius of connected graphs, A Classifier to Decide on the Linearization of Mixed-Integer Quadratic Problems in CPLEX, Fast Cluster Detection in Networks by First Order Optimization, Rank-1 Tensor Properties with Applications to a Class of Tensor Optimization Problems, An Irrational Lagrangian Density of a Single Hypergraph, Finite Convergence of Sum-of-Squares Hierarchies for the Stability Number of a Graph, Unnamed Item, A global optimization approach for solving the maximum clique problem, Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem, An Analytic Center Cutting Plane Method to Determine Complete Positivity of a Matrix, The inducibility of complete bipartite graphs, Hypergraph Turán densities can have arbitrarily large algebraic degree, Homogenization for polynomial optimization with unbounded sets, A tensor optimization algorithm for computing Lagrangians of hypergraphs, Discrimination between Gaussian process models: active learning and static constructions, Refinement on Spectral Turán’s Theorem, Lagrangian-perfect hypergraphs, A Sum of Squares Characterization of Perfect Graphs, Stability from graph symmetrisation arguments with applications to inducibility, A General Regularized Continuous Formulation for the Maximum Clique Problem, (Global) optimization: historical notes and recent developments, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, On the first two eigenvalues of regular graphs, Remarks on the largest eigenvalue of a signed graph, Localized versions of extremal problems, Spectral norm of a symmetric tensor and its computation, Lagrangian densities of linear forests and Turán numbers of their extensions, Nuclear norm of higher-order tensors, Stability and Turán Numbers of a Class of Hypergraphs via Lagrangians, The Minimum Number of Triangular Edges and a Symmetrization Method for Multiple Graphs, Unnamed Item, Unnamed Item, GENERATING NON-JUMPING NUMBERS OF HYPERGRAPHS, Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques, The number of $4$-cycles and the cyclomatic number of a finite simple graph, A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis, Solving Quadratic Programming by Cutting Planes, Equilibrium Distributions of Populations of Biological Species on Networks of Social Sites, The p-spectral radius of the Laplacian matrix, Neural networks for NP-complete problems, A new branch-and-bound algorithm for standard quadratic programming problems, Constructing test functions for global optimization using continuous formulations of graph problems, Strong Turán stability, Optimisation of quadratic forms associated with graphs, Algorithmic Solution of Extremal Digraph Problems, A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors, Best Nonnegative Rank-One Approximations of Tensors, Some Motzkin-Straus type results for non-uniform hypergraphs, A simplex like approach based on star sets for recognizing convex-\(QP\) adverse graphs, Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs, A characterization of the weighted Lovász number based on convex quadratic programming, A survey on graphs with convex quadratic stability number, Optimality conditions for linear copositive programming problems with isolated immobile indices, Certifying Polynomial Nonnegativity via Hyperbolic Optimization, Approximating the existential theory of the reals, The maximum clique and the signless Laplacian eigenvalues, Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution, Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization, Eigenvalues and triangles in graphs, An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution, Image Segmentation by Dominant Sets, Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of Linear Programming, A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem, New analytical lower bounds on the clique number of a graph, Annealed replication: A new heuristic for the maximum clique problem, Spectral bounds for the clique and independence numbers of graphs, Maximum cliques of hypergraphs and polynomial optimization, On Frankl and Füredi's conjecture for 3-uniform hypergraphs, Connection between the clique number and the Lagrangian of 3-uniform hypergraphs, Maximum weighted induced subgraphs, Computation of sparse and dense equilibrium strategies of evolutionary games, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, Degenerate Turán problems for hereditary properties, Convex envelopes of separable functions over regions defined by separable functions of the same type, On the jumping constant conjecture for multigraphs, On substructure densities of hypergraphs, On graph-Lagrangians and clique numbers of 3-uniform hypergraphs, Walks and the spectral radius of graphs, Optima of dual integer linear programs, The complexity of approximating a nonlinear program, Fixed interval scheduling: models, applications, computational complexity and algorithms, Turán number of generalized triangles, A linear programming reformulation of the standard quadratic optimization problem, Lagrangian densities of some sparse hypergraphs and Turán numbers of their extensions, A characterization of Delsarte's linear programming bound as a ratio bound, On the maximal number of edges in a homogeneous hypergraph not containing prohibited subgraphs, Semidefinite bounds for the stability number of a graph via sums of squares of polynomials, Using Lagrangians of hypergraphs to find non-jumping numbers. II., Self-concordance is NP-hard, Semidefinite approximations for quadratic programs over orthogonal matrices, Dense neighborhoods on affinity graph, Some extremal problems for hereditary properties of graphs, Extremal problems for the \(p\)-spectral radius of graphs, Unconstrained formulation of standard quadratic optimization problems, Lagrangians of hypergraphs: the Frankl-Füredi conjecture holds almost everywhere, Improving an upper bound on the size of \(k\)-regular induced subgraphs, NP-hardness of deciding convexity of quartic polynomials and related problems, Copositive optimization -- recent developments and applications, An improved algorithm to test copositivity, An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications, Two extremal problems related to orders, Extremals of functions on graphs with applications to graphs and hypergraphs, Global optimization problems and domain reduction strategies, Strong forms of stability from flag algebra calculations, On possible Turán densities, The computational complexity of evolutionarily stable strategies, On graph-Lagrangians of hypergraphs containing dense subgraphs, On the largest graph-Lagrangian of 3-graphs with fixed number of edges, New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability, On the complexity of optimization over the standard simplex, Box-constrained quadratic programs with fixed charge variables, Tag SNP selection based on clustering according to dominant sets found using replicator dynamics, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, A note on the structure of Turán densities of hypergraphs, A convex relaxation bound for subgraph isomorphism, A refined error analysis for fixed-degree polynomial optimization over the simplex, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, Analysis of copositive optimization based linear programming bounds on standard quadratic optimization, On Lagrangians of \(r\)-uniform hypergraphs, Generating non-jumping numbers recursively, Dense 3-uniform hypergraphs containing a large clique, Independent sets in graphs, On the quality of first-order approximation of functions with Hölder continuous gradient, Extensions of the standard quadratic optimization problem: strong duality, optimality, hidden convexity and S-lemma, Computing the \(p\)-spectral radii of uniform hypergraphs with applications, A clique algorithm for standard quadratic programming, A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs, A continuous characterization of the maximum vertex-weighted clique in hypergraphs, Dominant-set clustering: a review, A note on generalized Lagrangians of non-uniform hypergraphs, A nonconvex quadratic optimization approach to the maximum edge weight clique problem, The connection between polynomial optimization, maximum cliques and Turán densities, Separable standard quadratic optimization problems, Geometry of the copositive and completely positive cones, On the convergence of a Jacobi-type algorithm for singly linearly-constrained problems subject to simple bounds, A simpler characterization of a spectral lower bound on the clique number, Variable neighborhood search for the maximum clique, Improving an upper bound on the stability number of a graph, An exact bit-parallel algorithm for the maximum clique problem, Some results on the bounds of signless Laplacian eigenvalues, Potential energy principles in networked systems and their connections to optimization problems on graphs, Eigenvalues and chromatic number of a signed graph, Hybrid Riemannian conjugate gradient methods with global convergence properties, Connection between polynomial optimization and maximum cliques of non-uniform hypergraphs, A proximal DC approach for quadratic assignment problem, A continuous characterization of the maximum-edge biclique problem, A trust branching path heuristic for zero-one programming, Exact bounds on the order of the maximum clique of a graph., Matchings and covers in hypergraphs, Complexity results for some global optimization problems, A generalization of the Motzkin-Straus theorem to hypergraphs, On extended connectivity indices, On copositive matrices, More spectral bounds on the clique and independence numbers, A probabilistic variant of Sperner's theorem and of maximal \(r\)-cover free families, A lower bound on the independence number of a graph, Extremal graphs for weights, Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures, Ernst G. Straus (1922-1983), Stable sets and polynomials, Algorithms for the solution of quadratic knapsack problems, Extremal problems whose solutions are the blowups of the small Witt- designs, Asymptotic solution for a new class of forbidden r-graphs, The maximum clique problem, Subgraph extraction and metaheuristics for the maximum clique problem, On characterization of maximal independent sets via quadratic optimization, On the accuracy of uniform polyhedral approximations of the copositive cone, Turán-Ramsey theorems and simple asymptotically extremal structures, On standard quadratic programs with exact and inexact doubly nonnegative relaxations, Matrix Relaxations in Combinatorial Optimization, Continuous quadratic programming formulations of optimization problems on graphs, Using SVM to combine global heuristics for the standard quadratic problem, A review on algorithms for maximum clique problems, A Motzkin-Straus type result for 3-uniform hypergraphs, Tightening a copositive relaxation for standard quadratic optimization problems, A note on a conjecture of bene Watts-Norin-Yepremyan for Lagrangian, Convergence analysis of a Lasserre hierarchy of upper bounds for polynomial minimization on the sphere, Improved convergence analysis of Lasserre's measure-based upper bounds for polynomial minimization on compact sets, Some results on Lagrangians of hypergraphs, Numerical radius and zero pattern of matrices, Computable representations for convex hulls of low-dimensional quadratic forms, The \(\ell^p\)-Gaussian-Grothendieck problem with vector spins, Laplacian spectral bounds for clique and independence numbers of graphs, Cliques and the spectral radius, On the copositive representation of binary and continuous nonconvex quadratic programs, Certifying the global optimality of quartic minimization over the sphere, On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices, On a continuous approach for the maximum weighted clique problem, Maximisers of the hypergraph Lagrangian outside the principal range, Solving the maximum clique problem with symmetric rank-one non-negative matrix approximation, The Hessian matrix of Lagrange function, A homogeneous polynomial associated with general hypergraphs and its applications, Immobile indices and CQ-free optimality criteria for linear copositive programming problems, Generating irreducible copositive matrices using the stable set problem, The stable set problem: clique and nodal inequalities revisited, A survey of hidden convex optimization, On Motzkin-Straus type results for non-uniform hypergraphs, Extremal problems for the \(p\)-spectral radius of Berge hypergraphs, Strong duality and KKT conditions in nonconvex optimization with a single equality constraint and geometric constraint, Approximating the cone of copositive kernels to estimate the stability number of infinite graphs, The maximum Lagrangian of 5-uniform hypergraphs without containing two edges intersecting at a vertex, A computational study on QP problems with general linear constraints, Convex Envelopes of Some Quadratic Functions over the n-Dimensional Unit Simplex, \(\lambda\)-perfect hypergraphs and Lagrangian densities of hypergraph cycles, Non-jumping numbers for 5-uniform hypergraphs, A new branch-and-bound algorithm for the maximum edge-weighted clique problem, Signed spectral Turań-type theorems, Bipartite Hansel results for hypergraphs, A new trust region technique for the maximum weight clique problem, Properties and methods for finding the best rank-one approximation to higher-order tensors, Polytopic uncertainty for linear systems: new and old complexity results, Testing copositivity via mixed-integer linear programming, The fundamental theorem of linear programming: extensions and applications, Bounds on the spectral radius of general hypergraphs in terms of clique number, The extremal \(p\)-spectral radius of Berge hypergraphs, On a polynomial fractional formulation for independence number of a graph, Two methods for the maximization of homogeneous polynomials over the simplex, Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations, Connection between continuous optimization and Turán densities of non-uniform hypergraphs, A convergent decomposition algorithm for support vector machines, Pattern formation in auxin flux, On copositive matrices with -1, 9, 1 entries, A hybrid heuristic for the maximum clique problem, Simple complexity from imitation games, A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming, A PTAS for the minimization of polynomials of fixed degree over the simplex, On Hamiltonian Berge cycles in [3-uniform hypergraphs], A logarithmic descent direction algorithm for the quadratic knapsack problem, Lagrangians of hypergraphs. II: When colex is best, The Laplacian spectral radius of graphs, The Lagrangian density of \(\{123, 234, 456\}\) and the Turán number of its extension, Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems, Lagrangian densities of enlargements of matchings in hypergraphs, Lagrangian densities of short 3-uniform linear paths and Turán numbers of their extensions, Turán's theorem implies Stanley's bound, Quantifying controllability in temporal networks with uncertainty, How to integrate a polynomial over a simplex, Two remarks on copositive matrices, Hypergraph Lagrangians. I: The Frankl-Füredi conjecture is false, A generalization of a theorem of Turán, Global optimization with orthogonality constraints via stochastic diffusion on manifold, Extremal problems for directed graphs, Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere, On LP-based approximation for copositive formulation of stable set problem, An irrational Turán density via hypergraph Lagrangian densities, On the complexity of finding a local minimizer of a quadratic function over a polytope, On the maxima of Motzkin-Straus programs and cliques of graphs, On independent cliques and linear complementarity problems, A study on sequential minimal optimization methods for standard quadratic problems, Quartic formulation of standard quadratic optimization problems, Optimality and stability of symmetric evolutionary games with applications in genetic selection, Improving upper bounds for the clique number by non-valid inequalities, Continuous cubic formulations for cluster detection problems in networks, Large deviations for the largest eigenvalue of Gaussian networks with constant average degree, A hypergraph extension of Turán's theorem, A unified approach to hypergraph stability, Global convergence of Hager-Zhang type Riemannian conjugate gradient method, D.C. versus copositive bounds for standard QP, Improved approximation of maximum vertex cover, The \(p\)-spectral radius of \(k\)-partite and \(k\)-chromatic uniform hypergraphs, An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex, The clique problem for graphs with a few eigenvalues of the same sign, Complete positivity and distance-avoiding sets, Convex graph invariant relaxations for graph edit distance