IMSc Webinar

Some recent results in finite model theory and the structure theory of classes of hypergraphs

Abhisekh Sankaran

University of Cambridge

In this talk, we present an overview of our recent results in logic for finite structures. In the context of finite model theory, we present our results concerning a generalization of a classical model theoretic result called the Los-Tarski theorem. This generalization syntactically characterizes a parameterized weakening of hereditariness that is satisfied by many natural algorithmic problems. We also present a finitary adaptation of the classical Lowenheim-Skolem property and show this to be satisfied by the class of bounded shrub-depth graphs that are being actively studied given their nice algorithmic and structural properties.

In the context of structure theory of classes of hypergraphs, we consider the special class of hypergraphs that are the order types of point configurations on the plane and present a new notion of clique-width for them. Bounding the clique-width yields linear time fixed parameter tractable algorithms for many otherwise hard geometric problems. We also present our results on the crossing number of graphs and those on an open
problem from structural graph theory, called Seese's conjecture. We conclude with future directions in both of the above mentioned contexts.

Meeting link: meet.google.com/ptd-hxnx-yde