% LaTeX class specification.  Any changes will not appear in the final version
\documentclass[12pt,letterpaper, reqno]{aimpl}

% The problem list should be arranged like a research paper, with
% introductory material followed be one or more main sections.
% Do not divide the sections into subsections.
% Each section could have its own introductory material.
% The main part of each section is a "problem block" which has the format
% [[see elsewhere for more documentation]]

% New macros.
% If at all possible, please do not define any new macros.  Each
% macro you introduce has the potential to cause problems with the
% long-term maintenance of the problem list.

% removed \n from join and moved it to MACROS in app.js
\newcommand{\Cat}{{\rm Cat}}
\newcommand{\A}{\mathcal A}
\newcommand{\freestar}{ \framebox[7pt]{$\star$} }

\begin{document}
\title{Geometry of large networks}
\author{Edited by Dan Guralnik}

\urlstub{largenetworks}

\maketitle




\section{Problem session}

This (below) was an attempt to record the problem session (Tuesday, November 1st), the way it proceeded. Your additions and comments are welcome.

- Dan



\begin{problemblock}

\begin{problem}[1.05] How do we measure the curvature of real networks? \end{problem}




\end{problemblock}



\begin{problemblock}

\begin{problem}[1.3] What is the curvature of a network? How to define it? \end{problem}




\end{problemblock}



\begin{problemblock}

\begin{problem}[1.15] Why measure it? (What are the real-world applications?) \end{problem}




\begin{remark}
\by{Weinberger}Wasn't that your result, that the internet has curvature $-1$ and dimension $2$?\end{remark}

\begin{remark}
\by{Krioukov}So, yes, we need more examples like that, showing the significance of curvature.\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.2] Find (different) notions of distance on the space of graphs, or perhaps measures on this space. In particular: how far is a given graph from being a tree? \end{problem}




\begin{remark}
\by{Holmes}perhaps need to look at non-dense graphs; I have the impression that the problem is solved for dense ones.\end{remark}

\begin{remark}
\by{Gao}How about tree-width?\end{remark}

\begin{remark}
\by{Sullivan}Tree-width is not good enough. There is a relation to tree-length.\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.25] Is curvature related to clustering? \end{problem}




\begin{remark}
\by{Baryshnikov}What is meant by clustering?\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.55] Is there a scale at which the structure of a (real) network ``looks like'' a manifold? (e.g., Krioukov's result) \end{problem}




\begin{remark}
\by{Krioukov}This relates to the (previous) questions about how to define hyperbolicity or curvature for a {\it single} finite graph.\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.35] For random graphs, is there an idea for a degree of heterogeneity that could indicate hyperbolicity \end{problem}




\begin{remark}
\by{Weinberger}Similar to the question of frequency of hyperbolic groups among finitely generated/presented groups: could ask --

* What is a set of conditions ensuring hyperbolicity of an ensemble of random graphs (i.e., the set of hyperbolic graphs in the ensemble has probability one)?

* (Mahoney) important to emphasize randomness.
\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.4] What would be meant by a graph having *positive* curvature? (Grids don't have it; trees don't; how about spheres?) \end{problem}




\begin{remark}
\by{Baryshnikov, Weinberger}That depends on a choice of scale.\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.45] What precise notions of negative curvature imply congestion? \end{problem}




\begin{remark}
\by{Weinberger}What price are you willing to pay to avoid congestion?\end{remark}

\begin{remark}
\by{Bonahon/Saniee}*Where* does congestion occur? (something analogous to convex core?)\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.5] What are the data required to define congestion? \end{problem}




\begin{remark}
\by{Holmes}Do weights on the network or some such affect this?\end{remark}

\end{problemblock}



\begin{problemblock}

\begin{problem}[1.1] Need ways to compute geodesics on spaces where curvature is variable (using embedded graphs). \end{problem}




\end{problemblock}





\begin{thebibliography}{99}

\end{thebibliography}


\end{document}
