Friday, December 11, 2020

2020-12-18 / 13:00 ~ 15:00

by 손영탁()

In a wide class of random constraint satisfaction problems, ideas from statistical physics predict that there is a rich set of phase transitions governed by one-step replica symmetry breaking (1RSB). In particular, it is conjectured that for models in the 1RSB universality class, the solution space condenses into large clusters, just below the satisfiability threshold. We establish this phenomenon for the first time for random regular NAE-SAT in the condensation regime. That is, most of the solutions lie in a bounded number of clusters and the overlap of two independent solutions concentrates on two points. Central to the proof is to calculate the moments of the number of clusters whose size is in an O(1) window. This is joint work with Danny Nam and Allan Sly.

2020-12-17 / 13:00 ~ 15:00

학과 세미나/콜로퀴엄 - 확률론:

by 남경식()

The exponential random graph model (ERGM) is a version of the Erdos-Renyi graphs, obtained by tilting according to the subgraph counting Hamiltonian. Despite its importance in the theory of random graphs, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In this talk, I will introduce a series of new concentration of measure results for the ERGM in the entire sub-critical phase, including a Poincare inequality, Gaussian concentration, and a central limit theorem. Joint work with Shirshendu Ganguly.

2020-12-17 / 11:00 ~ 12:00

학과 세미나/콜로퀴엄 - Discrete Math:

by 전재웅(뉴욕주립대 뉴팔츠캠퍼스)

Abstract: In combinatorics, Hopf algebras appear naturally when studying various classes of combinatorial objects, such as graphs, matroids, posets or symmetric functions. Given such a class of combinatorial objects, basic information on these objects regarding assembly and disassembly operations are encoded in the algebraic structure of a Hopf algebra. One then hopes to use algebraic identities of a Hopf algebra to return to combinatorial identities of combinatorial objects of interest. In this talk, I introduce a general class of combinatorial objects, which we call multi-complexes, which simultaneously generalizes graphs, hypergraphs and simplicial and delta complexes. I also introduce a combinatorial Hopf algebra obtained from multi-complexes. Then, I describe the structure of the Hopf algebra of multi-complexes by finding an explicit basis of the space of primitives, which is of combinatorial relevance. If time permits, I will illustrate some potential applications. This is joint work with Miodrag Iovanov.

Events for the 취소된 행사 포함