For a graph G, let bc(G) denote the minimum possible number of pairwiseedge disjoint complete bipartite subgraphs of G so that each edge of Gbelongs to (exactly) one of them. The study of this quantity and itsvariants received a considerable amount of attention and is relatedto problems in communication complexity and geometry. After a briefdisc...
Creator:
Alon, Noga (Tel Aviv University)
Created:
2014-09-09
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
Erdos conjectured that a triangle-free graph with chromatic number k contains cycles of almost quadratically manydifferent lengths, as k tends to infinity.We prove a somewhatstronger 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'sconstruction of ...
Creator:
Kostochka, Alexandr (University of Illinois at Urbana-Champaign)
Created:
2014-09-10
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
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 des...
Creator:
Nedich, Angelia (University of Illinois at Urbana-Champaign)
Created:
2015-10-02
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
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 ...
Creator:
Saito, Naoki (University of California, Davis)
Created:
2014-04-28
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
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 ...
Creator:
Guibas, Leonidas (Stanford University)
Created:
2011-10-25
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
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 d...
Created:
2011-10-24
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
I will discuss random walks on simplicial complexes, Cheeger inequalities,and mixing times. The talk will summarize the results of two papers that explorehow 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 le...
Creator:
Mukherjee, Sayan (Duke University)
Created:
2013-11-01
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
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 c...
Creator:
Csikvà¡ri, Péter (Massachusetts Institute of Technology)
Created:
2014-04-28
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
In this talk I will introduce some techniques for topological reasoning within the purview of graph search-based motion planning. Classically, in robotics and artificial intelligence literature, a popular approach to dealing with complexities in configuration spaces (high dimension or topological non-trivialities) is to create a graph by placing...
Creator:
Bhattacharya, Subhrajit (University of Pennsylvania)
Created:
2014-03-03
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.
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 theTuran number of a tree T of k vertices. The difficulty lies in the fact thatthere could be very different extremal families, disjoint cliques of sizes k-1or in some cases a graph with (k-2)/2 v...
Creator:
Furedi, Zoltan (Hungarian Academy of Sciences (MTA))
Created:
2014-09-09
Contributed By:
University of Minnesota, Institute for Mathematics and its Applications.