BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Dan Suciu (University of Washington)
DTSTART:20240605T150000Z
DTEND:20240605T161500Z
DTSTAMP:20260423T021357Z
UID:AAIT/36
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/AAIT/36/">Ti
 ght upper bounds on the number of homomorphic images of a hypergraph in an
 other.</a>\nby Dan Suciu (University of Washington) as part of Seminar on 
 Algorithmic Aspects of Information Theory\n\n\nAbstract\nGiven two hypergr
 aphs $H$\, $G$\, we are interested in the number of homomorphisms $H \\to 
 G$. The hyperedges are typed\, and homomorphisms need to preserve the type
 . The graph $G$ is unknown\, instead we only know statistics about $G$\, s
 uch as the total number of edges of each type\, or information about their
  degree sequences. The problem is to compute an upper bound on the number 
 of homomorphisms $H \\to G$\, when $G$ satisfies the given statistics. We 
 say that this bound is tight within a constant $c \\le 1$ if there exists 
 a graph $G$ satisfying the given statistics for which the number of homomo
 rphisms is at least c times the bound.\n\nWe start with the AGM bound (by 
 Atserias\, Grohe\, Marx)\, which strengthens a prior result by Friedgut an
 d Kahn. This bound uses only the cardinalities of each type of hyperedge o
 f the hypergraph $G$. We will prove the AGM bound by using a numerical ine
 quality due to Friedgut\, which generalizes Cauchy-Schwartz and Holder's i
 nequalities. The AGM bound can be computed in polynomial time in the size 
 of $H$\, and is tight within a constant $1/2^k$\, where $k$ is the number 
 of vertices in $H$. \n\n\nNext\, we prove a general bound\, which uses bot
 h the cardinalities of each type of hyperedge\, and the norms of their deg
 ree sequences. In particular\, the $\\ell_p$ norms of their degree sequenc
 es. In particular\, the $\\ell_\\infty$ norm is the largest degree of that
  type of hyperedges in $G$. The proof uses information inequalities\, and 
 for that reason we call the bound the "entropic bound". However\, it is an
  open problem whether the entropic bound is computable. \n\nFinally\, we r
 estrict the statistics to "simple" statistics\, where all degrees are from
  a single node\, as opposed to tuples of nodes: in particular\, if $G$ is 
 a graph\, then all statistics are simple. In this case we show that the en
 tropic vector in the entropic bound can be restricted to be one with non-n
 egative $I$-measure. Furthermore\, the entropic bound is computable in pol
 ynomial time in the size of $H$\, and it is tight within a constant $1/2^{
 2^k-1}$.\n
LOCATION:https://researchseminars.org/talk/AAIT/36/
END:VEVENT
END:VCALENDAR