# Graph

Friday, October 2, 2015 - 10:30am - 11:30am

Angelia Nedich (University of Illinois at Urbana-Champaign)

We will consider the problem of distributed cooperative non-Bayesian learning in a network of agents, where the agents are repeatedly gaining partial information about an unknown random variable whose distribution is to be jointly estimated. The joint objective of the agent system is to globally agree on a hypothesis (distribution) that best describes the observed data by all agents in the network. Interactions between agents occur according to an unknown sequence of time-varying graphs.

Monday, April 28, 2014 - 9:00am - 9:50am

Naoki Saito (University of California)

I will start describing some basics of the graph Laplacian eigenvectors of a given graph and their properties. In particular, I will describe the peculiar phase transition/localization phenomena of such eigenvectors observed on a certain type of graphs (e.g., dendritic trees of neurons). Then, I will describe how to construct wavelet packets on a given graph including the Haar-Walsh basis dictionary using the graph Laplacian eigenvectors. As an application of such basis dictionaries, I will discuss efficient approximation of functions given on graphs.

Monday, April 28, 2014 - 2:00pm - 2:50pm

Péter Csikvári (Massachusetts Institute of Technology)

In this talk I will survey some results on statistical properties of matchings of very large and infinite graphs. The main goal of the talk is to describe a few applications of a new concept called matching measure. These applications include new results on the number of (perfect) matchings in large girth graphs as well as simple new proofs of certain statistical physical theorems. This is joint work with various subsets of Miklós Abért, Péter E. Frenkel, Tamás Hubai and Gábor Kun.

Wednesday, September 10, 2014 - 2:00pm - 2:50pm

Alexandr Kostochka (University of Illinois at Urbana-Champaign)

Erdos conjectured that a triangle-free graph with chromatic number

k contains cycles of almost quadratically many

different lengths, as k tends to infinity.

We prove a somewhat

stronger inequality for the number of consecutive lengths of cycles in

k-chromatic graphs.

The bound has the best possible order of magnitude because of Kim's

construction of small triangle-free

graphs with chromatic number k.

We also give new lower bounds on the circumference and the number of

k contains cycles of almost quadratically many

different lengths, as k tends to infinity.

We prove a somewhat

stronger inequality for the number of consecutive lengths of cycles in

k-chromatic graphs.

The bound has the best possible order of magnitude because of Kim's

construction of small triangle-free

graphs with chromatic number k.

We also give new lower bounds on the circumference and the number of

Tuesday, September 9, 2014 - 3:15pm - 4:05pm

The Turan number ex(n,H) of an r-graph H is the largest size of an n-vertex

r-graph that does not contain H. The famous Erdos-Sos conjectrure concerns the

Turan number of a tree T of k vertices. The difficulty lies in the fact that

there could be very different extremal families, disjoint cliques of sizes k-1

or in some cases a graph with (k-2)/2 vertices of degree n-1.

A hypergraph H is a hypergraph forest if its edges can be ordered as

r-graph that does not contain H. The famous Erdos-Sos conjectrure concerns the

Turan number of a tree T of k vertices. The difficulty lies in the fact that

there could be very different extremal families, disjoint cliques of sizes k-1

or in some cases a graph with (k-2)/2 vertices of degree n-1.

A hypergraph H is a hypergraph forest if its edges can be ordered as

Tuesday, September 9, 2014 - 11:30am - 12:20pm

Noga Alon (Tel Aviv University)

For a graph G, let bc(G) denote the minimum possible number of pairwise

edge disjoint complete bipartite subgraphs of G so that each edge of G

belongs to (exactly) one of them. The study of this quantity and its

variants received a considerable amount of attention and is related

to problems in communication complexity and geometry. After a brief

discussion of the background and earlier results on the subject I will

focus on the problem of determining the typical value of bc(G) for the

edge disjoint complete bipartite subgraphs of G so that each edge of G

belongs to (exactly) one of them. The study of this quantity and its

variants received a considerable amount of attention and is related

to problems in communication complexity and geometry. After a brief

discussion of the background and earlier results on the subject I will

focus on the problem of determining the typical value of bc(G) for the

Monday, March 3, 2014 - 3:15pm - 4:05pm

Subhrajit Bhattacharya (University of Pennsylvania)

In this talk I will introduce some techniques for topological reasoning within the purview of graph search-based motion planning.

Friday, November 1, 2013 - 9:00am - 9:50am

Sayan Mukherjee (Duke University)

I will discuss random walks on simplicial complexes, Cheeger inequalities,

and mixing times. The talk will summarize the results of two papers that explore

how random walks on walks graphs extend to simplicial complexes. I will also discus two papers that study higher order Laplacians and expander properties.

Two possible applications in machine learning will be discussed: spectral clustering and label (edge) propogation.

joint work with John Steenbergen

and mixing times. The talk will summarize the results of two papers that explore

how random walks on walks graphs extend to simplicial complexes. I will also discus two papers that study higher order Laplacians and expander properties.

Two possible applications in machine learning will be discussed: spectral clustering and label (edge) propogation.

joint work with John Steenbergen

Monday, October 24, 2011 - 4:15pm - 5:15pm

Preferential attachment is a powerful mechanism explaining the emergence of scaling in growing networks. If new connections are established preferentially to more popular nodes in a network, then the network is scale-free. Here we show that not only popularity but also similarity is a strong force shaping the network structure and dynamics. We develop a framework where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity.

Tuesday, October 25, 2011 - 1:30pm - 2:30pm

Leonidas Guibas (Stanford University)

In this talk we consider certain graphs that arise out of matching shapes or images. We begin by exploring how to define isometrically-invariant descriptors of shape neighborhoods and how these can be used to compute maps between shapes. We then analyze map networks with the goal of improving individual maps connecting the shapes. The fact that maps compose algebraically allows certain novel approaches that are not possible when edges encode only some proximity or similarity of the nodes.