À¶Ý®ÊÓƵ

Title:The first-order logic of graphs

Abstract:Over the last ten years, many wonderful connections have been established between structural graph theory, computational complexity, and finite model theory. We give an overview of this area, focusing on recent progress towards understanding the "stable" case. We do not assume any familiarity with first-order logic

Ìý

Title:Complete bipartite induced minors (and treewidth)

Abstract:I will present a result that describes the unavoidable induced subgraphs of graphs with a large complete bipartite induced minor, and will discuss the connections and applications to bounding the treewidth in hereditary classes of graphs. If time permits, I will also sketch some proofs.

ÌýJoint work with Maria Chudnovsky and Sophie Spirkl.

Ìý

Title:Worst-case instances of the stable set problem of graphs for the Lovász–Schrijver SDP hierarchy

Abstract:(Based on joint work with Levent Tunçel.)

In this talk, we discuss semidefinite relaxations of the stable set problem of graphs generated by the lift-and-project operator LS_+ (due to Lovász and Schrijver), and present some of our recent progress on this front. In particular, we show that for every positive integer k, the smallest graph with LS_+-rank k contains exactly 3k vertices. This result is sharp and settles a conjecture posed by Lipták and Tunçel from 2003.

The talk will be accessible to a general audience, and does not assume any prior knowledge of lift-and-project methods.

Ìý

Title:The omega-Condition Number: Applications to Preconditioning and Low Rank Generalized Jacobian Updating

Abstract:ÌýPreconditioning is essential in iterative methods for solving linear systems. It is also the implicit objective in updating approximations of Jacobians in optimization methods, e.g.,~in quasi-Newton methods. We study a nonclassic matrix condition number, the omega-condition number}, omega for short. omega is the ratio of: the arithmetic and geometric means of the singular values, rather than the largest and smallest for the classical kappa-condition number. The simple functions in omega allow one to exploitÌý first order optimality conditions. We use this fact to derive explicit formulae for (i) omega-optimal low rank updating of generalized Jacobians arising in the context of nonsmooth Newton methods; and (ii) omega-optimal preconditioners of special structure for Ìýiterative methods for linear systems. In the latter context, we analyze the benefits of omega for (a) improving the clustering of eigenvalues; (b) reducing the number of iterations; and (c) estimating the actual condition of a linear system. Moreover we show strong theoretical connections between the omega-optimal preconditioners and incomplete Cholesky factorizations, and highlight the misleading effects arising from the inverse invariance of kappa. Our results confirm the efficacy of using the omega-condition number compared to the kappa-condition number.

(Joint work with: Woosuk L. Jung, David Torregrosa-Belen.)

Ìý

Title:Automated Sequence Asymptotics

Abstract:Computing with any sort of object requires a way of encoding it on a computer, which poses a problem in enumerative combinatorics where the objects of interest are (infinite) combinatorial sequences. Thankfully, the generating function of a combinatorial sequence often satisfies natural algebraic/differential/functional equations, which can then be viewed as data structures for the sequence. In this talk we survey methods to take a sequence encoded by such data structures and automatically determine asymptotic behaviour using techniques from the field of analytic combinatorics. We also discuss methods to automatically characterize the asymptotic behaviour of multivariate sequences using analytic combinatorics in several variables (ACSV). The focus of each topic will be rigorous algorithms that have already been implemented in computer algebra systems and can be easily used by anyone.

Ìý