Tue, 08 May 2018
14:30
L6

The Junta Method for Hypergraphs

Noam Lifshitz
(Bar Ilan University)
Abstract

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an 'enlarged' copy H^+ of a fixed hypergraph H. These include well-known  problems such as the Erdős-Sós 'forbidding one intersection' problem and the Frankl-Füredi 'special simplex' problem.


In this talk we present a general approach to such problems, using a 'junta approximation method' that originates from analysis of Boolean functions. We prove that any (H^+)-free hypergraph is essentially contained in a 'junta' -- a hypergraph determined by a small number of vertices -- that is also (H^+)-free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all C<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes  the aforementioned problems, and solves them for a large new set of parameters.


Based on joint works with David Ellis and Nathan Keller
 

Tue, 01 May 2018
14:30
L6

Better Bounds for Poset Dimension and Boxicity

David Wood
(Monash University)
Abstract

We prove that the dimension of every poset whose comparability graph has maximum degree $\Delta$ is at most $\Delta\log^{1+o(1)} \Delta$. This result improves on a 30-year old bound of F\"uredi and Kahn, and is within a $\log^{o(1)}\Delta$ factor of optimal. We prove this result via the notion of boxicity. The boxicity of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $\Delta$ has boxicity at most $\Delta\log^{1+o(1)} \Delta$, which is also within a $\log^{o(1)}\Delta$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $\Theta(\sqrt{g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor. This is joint work with Alex Scott (arXiv:1804.03271).

Knots are widespread, universal physical structures, from shoelaces to Celtic decoration to the many variants familiar to sailors. They are often simple to construct and aesthetically appealing, yet remain topologically and mechanically quite complex.

Knots are also common in biopolymers such as DNA and proteins, with significant and often detrimental effects, and biological mechanisms also exist for 'unknotting'.

Reachability computation for switching diffusions: Finite abstractions with certifiable and tuneable precision
Laurenti, L Abate, A Bortolussi, L Cardelli, L Ceska, M Kwiatkowska, M 20th ACM International Conference on Hybrid Systems: Computation and Control (HSCC 2017) (13 Apr 2017)
Experimental biological protocols with formal semantics
Abate, A Cardelli, L Kwiatkowska, M Laurenti, L Yordanov, B 16th International Conference on Computational Methods in Systems Biology (CMSB), 12th-14th September 2018, Faculty of Informatics, Masaryk University, Brno (CZ) volume 11095 165-182 (24 Aug 2018)
Mon, 30 Apr 2018

14:15 - 15:15
L4

C^infinity Schemes, and Manifolds with Corners

Kelli Francis-Staite
(Oxford)
Abstract

A C^infinity scheme is a version of a scheme that uses a maximal spectrum. The category of C^infinity schemes contains the category of Manifolds as a full subcategory, as well as being closed under fibre products. In other words, this category is equipped to handle intersection singularities of smooth spaces.

While originally defined in the set up of Synthetic Differential Geometry, C^infinity schemes have more recently been used to describe derived manifolds, for example, the d-manifolds of Joyce. There are applications of this in Symplectic Geometry, such as the describing the moduli space of J-holomorphic forms.

In this talk, I will describe the category of C^infinity schemes, and how this idea can be extended to manifolds with corners. If time, I will mention the applications of this in derived geometry.

Tue, 01 May 2018

12:00 - 13:15
L4

The double copy: from BRST ghosts to black hole solutions

Dr Sylvia Nagy
(Nottingham)
Abstract

I will present a procedure for perturbatively constructing the field content of gravitational theories from a convolutive product of two Yang-Mills theories. A dictionary "gravity=YM * YM" is developed, reproducing the symmetries and dynamics of the gravity theory from those of the YM theories. I will explain the unexpected, yet crucial role played by the BRST ghosts of the YM system in the construction of gravitational fields. The dictionary is expected to develop into a solution-generating technique for gravity.
 

How can reasoners simplify database querying (and why haven’t they done it yet)?
Benedikt, M Symposium on Principles of Database Systems (PODS 2018) (27 May 2018)
Subscribe to