A következő kombinatorika szemináriumok ideje
helye
és előadásai:
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.
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