Invited Session Thu.1.H 3004

Thursday, 10:30 - 12:00 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Optimization and enumeration


Chair: Jaroslav Nesetril and Martin Loebl



Thursday, 10:30 - 10:55 h, Room: H 3004, Talk 1

Patrice Ossona de Mendez
Large structured induced subgraphs with close homomorphism statistics

Coauthor: Jaroslav Nesetril


A particular attention has been recently devoted to the study of the graph homomorphism statistics. Let hom(F,G) denote the number of homomorphisms of F to G. The problem we address here is whether a graph G contains an induced subgraph G[A] such that:

  • for every small test graph F, hom(F,G[A]) is not "too different'' from hom(F,G):

    |F| ≤ p \Longrightarrow  loghom(F,G[A])>(1-ε)loghom(F,G);

  • the subgraph G[A] is highly structured in the sense that it is obtained from a small graph H (of order at most C(p,ε) by applying some blowup-like operations.
    We prove that classes of graphs which are nowhere dense (meaning that for every integer p there is a p subdivision of a finite complete graph that is isomorphic to no subgraph of a graph in \mathcal C) have the property that for every integer p and every ε>0 every sufficiently large graph in the class has such an induced subgraph.



    Thursday, 11:00 - 11:25 h, Room: H 3004, Talk 2

    Michael Chertkov
    Computing the permanent with belief propagation

    Coauthor: Adam B. Yedidia


    We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the Belief Propagation (BP) approach and its Fractional BP generalization to computing the permanent of a non-negative matrix. Known bounds and conjectures are verified in experiments, and some new theoretical relations, bounds and conjectures are proposed.



    Thursday, 11:30 - 11:55 h, Room: H 3004, Talk 3

    Amin Coja-Oghlan
    Catching the k-NAESAT threshold

    Coauthor: Konstantinos Panagiotou


    The best current estimates of the thresholds for the existence of solutions in random CSPs mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. Here we present an enhanced second moment method that allows us to narrow the gap to an additive 2-(1-ok(1))k in the random k-NAESAT problem, one of the standard benchmarks in the theory or random CSPs. This is joint work with Konstantinos Panagiotou.


  •   The system of instant Virginia Loans Online allows any adult U.S. citizen. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.