Campuses:

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
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
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
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
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.

Pages

Subscribe to RSS - Graph