CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Densities and Graph Limits

JACOB COOPER, University of Warwick
Universality of finitely forcible graph limits  [PDF]

The theory of graph limits represents large graphs by an analytic object called a graphon. Graph limits determined by finitely many graph densities, which are represented by finitely forcible graphons, arise in various scenarios, particularly within extremal combinatorics. Lov\'asz and Szegedy conjectured that all such graphons possess a simple structure, e.g., the space of their typical vertices is always finite dimensional; this was disproved by several ad hoc constructions of complex finitely forcible graphons. We prove that any graphon is a subgraphon of a finitely forcible graphon, which completely dismisses any hope for a result showing that finitely forcible graphons possess a simple structure. Moreover, since any finitely forcible graphon represents the unique minimizer of some linear combination of densities of subgraphs, our result also shows that such minimization problems may in fact have unique optimal solutions with arbitrarily complex structure. Joint work with Daniel Kr\'al' and Ta\'isa Martins.

JOHN GOLDWASSER, West Virginia University
Maximum density of a vertex configuration in the n-cube  [PDF]

Let H be a set of vertices, called a configuration, in the d-cube Qd. The d-cube-density of H, denoted f(H,d), is the limit as n goes to infinity of maximum fraction, over all subsets S of the vertices of Qn, of sub-d-cubes whose intersection with S is a copy of H.

Using a “blow-up” of H, it is not hard to show f(H,4) is at least 3/32 for every configuration H in Q4. Let C2d denote a “perfect” 2d-cycle – a cycle where each pair of opposite vertices is distance d apart. We show f(C8,4) = 3/32, and flag algebra evidence says it is the only one of the 238 non-isomorphic configurations in Q4 with this minimum possible 4-cube-density. We conjecture same for C2d in Qd for all d.

We needed to determine which bipartite graph with n vertices induces the most copies of the graph two disjoint edges.

ANTHONY HARRISON, Kent State University
Computing the lattice size of a lattice polygon with respect to the 2-simplex  [PDF]

The lattice size of a lattice polygon $P$, denoted $\mathrm{ls}(P)$, is the smallest number $n$ such that the image of $P$ under an affine unimodular transformation is contained within the $n$-dilate of the standard 2-simplex. An optimal transformation $T$, one such that $TP$ fits in the smallest possible dilate, can be used to find a ``better'' parametrization of a toric surface. Castryck, Cools, and Shicho showed that there is a recursive algorithm to find such a $T$ by relating $\mathrm{ls}(P)$ to the lattice size of the convex hull of the interior lattice points of $P$. We have developed an algorithm that needs only the vertices of $P$ and so avoids the computational expense of determining the interior lattice points. We show that if a fixed, finite set of transformations does not yield a ``smaller'' image of $P$, then a translate of $P$ fits in the smallest possible dilate.

PING HU, University of Warwick
Tilings in Graphons  [PDF]

We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph $F$ to the setting of graphons. The case $F$ be an edge gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings. As an application of our theory, we determine the asymptotically almost surely $F$-tiling number of inhomogeneous random graphs $G(n,W)$. As another application, we give a strengthening of a theorem of Komlos, which gives minimum degree threshold that guarantees a prescribed lower bound on the fractional $F$-cover number of a graphon $W$.

Joint work with Jan Hladky and Diana Piguet.

YINGJIE QIAN, McGill University
Asymptotic density of graphs excluding a disconnected minor  [PDF]

For a graph $H$, let $$c_{\infty}(H) = \lim_{n \to \infty} (\max |E(G)|/n),$$ where the maximum is taken over all graphs $G$ on $n$ vertices not containing $H$ as a minor. Thus $c_{\infty}(H)$ is the asymptotic maximum density of graphs not containing an $H$-minor. Employing a structural result of Eppstein, we prove new upper bounds on $c_{\infty}(H)$ for disconnected graphs $H$.

The case when $H=sK_r$, that is when $H$ is a disjoint union of $s$ copies of the complete graph on $r$ vertices, is of particular interest. Thomason has shown that $$c_{\infty}(sK_r)=s(r-1)-1$$ for $s = \Omega(r \sqrt{\log r})$. We show that the same conclusion holds for $s = \Omega(\log^{3/2}r)$, which is best possible up to the power of the logarithm.

Based on joint work with Sergey Norin.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology