Georgia Institute of Technology College of Sciences

The clique chromatic number of a graph is the smallest number of colors in a vertex coloring so that no inclusion-maximal clique is monochromatic (ignoring isolated vertices). For the binomial random graph G_{n,p} the clique chromatic number has been studied in a number of works since 2016, but for sparse edge-probabilities in the range n^{-2/5} \ll p \ll 1 even the order of magnitude remained a technical challenge.

Resolving open problems of Alon and Krivelevich as well as Lichev, Mitsche and Warnke, we determine the clique chromatic number of the binomial random graph G_{n,p} in most of the missing regime: we show that it is of order (\log n)/p for edge-probabilities n^{-2/5+\eps} \ll p \ll n^{-1/3} and n^{-1/3+\eps} \ll p \ll 1, for any constant \eps > 0. Perhaps surprisingly for a result about random graphs, a key ingredient in the proof is an application of the probabilistic method (that hinges on careful counting and density arguments).

This talk is based on joint work with Lutz Warnke.

We study the problem of estimating the left and right singular subspaces for a collection of heterogeneous random graphs with a shared common structure. We analyze an algorithm that first estimates the orthogonal projection matrices corresponding to these subspaces for each individual graph, then computes the average of the projection matrices, and finally finds the matrices whose columns are the eigenvectors corresponding to the d largest eigenvalues of the sample averages. We show that the algorithm yields an estimate of the left and right singular vectors whose row-wise fluctuations are normally distributed around the rows of the true singular vectors. We then consider a two-sample hypothesis test for the null hypothesis that two graphs have the same edge probabilities matrices against the alternative hypothesis that their edge probabilities matrices are different. Using the limiting distributions for the singular subspaces, we present a test statistic whose limiting distribution converges to a central chi-square (resp. non-central chi-square) under the null (resp. alternative) hypothesis. Finally, we adapt the theoretical analysis for multiple networks to the setting of distributed PCA; in particular, we derive normal approximations for the rows of the estimated eigenvectors using distributed PCA when the data exhibit a spiked covariance matrix structure.

We consider the Ising Curie-Weiss model on the complete graph constrained under a given $\ell_{p}$ norm. For $p=\infty$, it reduces to the classical Ising Curie-Weiss model. We prove that for all $p\ge 2$, there exists a critical inverse temperature $\beta_{c}(p)$ such that for $\beta<\beta_{c}(p)$, the magnetization is concentrated at zero and satisfies an appropriate Gaussian CLT. On the other hand, for $\beta>\beta_{c}(p)$, the magnetization is not concentrated at zero similar to the classical case. We further generalize the model for general symmetric spin distributions and prove similar phase transition. In this talk, we discuss a brief overview of classical Curie-Weiss model, a generalized Hubbard-Stratonovich transforms, and how we apply the transform to Curie-Weiss model under $\ell^p$ constraint. This is based on joint work with Partha Dey.

In this talk, we present recent results on the geometry of centrally-symmetric random polytopes generated by N independent copies of a random vector X. We show that under minimal assumptions on X, for N>Cn, and with high probability, the polytope contains a deterministic set that is naturally associated with the random vector - namely, the polar of a certain floating body. This solves the long-standing question on whether such a random polytope contains a canonical body. Moreover, by identifying the floating bodies associated with various random vectors we recover the estimates that have been obtained previously, and thanks to the minimal assumptions on X we derive estimates in cases that had been out of reach, involving random polytopes generated by heavy-tailed random vectors (e.g., when X is q-stable or when X has an unconditional structure). Finally, the structural results are used for the study of a fundamental question in compressive sensing - noise blind sparse recovery. This is joint work with Olivier Guédon (University of Paris-Est Marne La Vallée), Christian Kümmerle (UNC Charlotte), Shahar Mendelson (Sorbonne University Paris), and Holger Rauhut (LMU Munich).

Bio: Felix Krahmer received his PhD in Mathematics in 2009 from New York University under the supervision of Percy Deift and Sinan Güntürk. He was a Hausdorff postdoctoral fellow in the group of Holger Rauhut at the University of Bonn, Germany from 2009-2012. In 2012 he joined the University of Göttingen as an assistant professor for mathematical data analysis, where he has been awarded an Emmy Noether Junior Research Group. From 2015-2021 he was assistant professor for optimization and data analysis in the department of mathematics at the Technical University of Munich, before he was tenured and promoted to associate professor in 2021. His research interests span various areas at the interface of probability, analysis, machine learning, and signal processing including randomized sensing and reconstruction, fast random embeddings, quantization, and the computational sensing paradigm.