A következő kombinatorika szemináriumok ideje

május 29. (!!! CSÜTÖRTÖK !!!), !!! 10:00 !!!,

helye

Kalmár Intézet, Árpád tér, szemináriumi szoba (második emelet, a folyosó vége)

és előadásai:

10:00 Székely László (University of South Carolina): Threshold functions for distinct parts: Erdos-Lehner revisited

Abstract: Put n balls randomly into k boxes with the condition that no box is empty. What is the threshold function n=n(k) for the probability that all boxes contain different number of balls? This makes, of course, four problems, as balls and boxes can be distinguishable or indistinguishable. The case of indistinguishable balls is close to the Erdos-Lehner asymptotic formula for partitions. This is joint work with Eva Czabarka and Matteo Marsili.

11:00 Czabarka Éva (University of South Carolina): Partition adjacency matrices

Havel-Hakimi and respectively Ryser showed that the space of graphs and bipartite graphs with a given degree sequence is connected under simple swaps of edges. This operation is useful in an MCMC algorithm that samples the space of graphs with a given degree sequence. Degree sequence alone does not capture the assortativity of the graph, the tendency of nodes to be connected to vertices of similar or different degrees. To overcome this difficulty, the joint degree matrix of a graph was introduced. Partition adjacency matrices (PAMs) are generalizations of joint degree matrices: given a partition {P1,...,PM} of the vertex set the M×M partition adjacency matrics $(aij)$ is defined by $aij=$ the number of edges connecting a vertex in Pi to a vertex in Pj. We will show conditions for a matrix to be the partition adjacency matrix of a graph; prove that under certain condition essentially the same swaps connect the space of all graphs with a given PAM, and give examples that show that these conditions are the best possible in some sense.

Mindenkit szeretettel várunk,

Péter

Supported by TÁMOP-4.2.2.A-11/1/KONV-2012-0073, Telemedicine Oriented Research in the Fields of Mathematics, Informatics and Medical Sciences