Jeudi 02 juillet 2015 à 11h, salle 24-25/405
Abstract
We introduce the inhomogeneous hypergraph model. Each edge can contain an
arbitrary number of vertices, the vertices are colored, and each edge
receives a weight which depends on the colors of the vertices it contains.
This model provides a uniform setting to solve problems arising from
various domains of computer science and mathematics. We will focus on
applications to the enumeration of satisfied and satisfiable instances of
Constraint Satisfaction Problems (CSP), and compute the limit probability
for a random graph to be bipartit, the limit probability of satisfiability
of systems of equations, the enumeration of properly k-colored graphs and
investigate some graphs coming from social networks.
We will present results on the asymptotics of inhomogeneous hypergraphs and
their typical structure. Our main tool is analytic combinatorics.