Title	Graph Density Inequalities and Sums of Squares
Creator	Thomas, Rekha
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2019-05-29T09:01
Description	Many results in extremal graph theory can be formulated as inequalities on graph densities. While many inequalities are known, many more are conjectured. A standard tool to establish an inequality is to write the expression whose non-negativity needs to be certified as a sum of squares. This technique has had many successes but also limitations. In this talk I will describe new restrictions that show that several simple inequalities cannot be certified by sums of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovasz and Szegedy. Joint work with Greg Blekherman, Annie Raymond and Mohit Singh.
Extent	58.0 minutes
Subject	Mathematics; Operations research, mathematical programming; Algebraic geometry; Control/Optimization/Operation Research
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: University of Washington
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2019-11-26
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0385894
URI	http://hdl.handle.net/2429/72414
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Faculty
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos

Graph Density Inequalities and Sums of Squares Thomas, Rekha

Description

Item Metadata

Item Media

Item Citations and Data

Rights