A simple solution to the $k$-core problem

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=8TAEQI43ymY


Duration: 1:05:35
602 views
2

We study the $k$-core of a random (multi) graph on $n$ vertices with a given degree sequence. We let $n$ tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the $k$-core is empty, and other conditions that imply that with high probability the $k$-core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer and Wormald \cite{psw96} on the existence and size of a $k$-core in $G(n,p)$ and $G(n,m)$, see also Molloy~\cite{Molloy05} and Cooper~\cite{c04}. Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs. This is joint work with Svante Janson.



Other Videos By Microsoft Research


2016-09-07Simple practical methods for estimating distances in large and sparse datasets like the web
2016-09-07Breaking Development Barriers with Better [1/2]
2016-09-07Conference XP - Access Grid Update
2016-09-07Paying Attention to Interruption: A Human-Centered Approach to Intelligent Interruption Management
2016-09-07Studies of Programmers: How can they inform training and instruction?
2016-09-07Computers versus Common Sense [1/5]
2016-09-07Doing a Mao and the Xray Paradox: How Can Humanity Overcome Organization?           
2016-09-07THE CREATION: AN APPEAL TO SAVE LIVE ON EARTH
2016-09-07MobileASL: Making Cell Phones Accessible to the Deaf Community
2016-09-07Using Architecture and Code Optimization Techniques to Create Fast and Effective Data Compressors
2016-09-07A simple solution to the $k$-core problem
2016-09-07The Challenges of Development-through-Entrepreneurship: Research on Rural Computer Kiosks in India
2016-09-07The Elegant Solution: Toyota's Formula for Mastering Innovation
2016-09-07Lattice-Based Discriminative Training: Theory and Practice
2016-09-07Conference XP - Tutored Video Instruction With Conference XP and Classroom Presenter
2016-09-07Faster Decoding with Synchronous Grammars and n-gram Language Models
2016-09-07Locality and Phases: Dynamic Structures in Large-Scale Program Behavior
2016-09-07Inversion Transduction Grammar with Linguistic Constraints
2016-09-07How scheduling theory, scenarios, model checking and slicing can help in the verification of RTS
2016-09-07Innovention - the process of innovation and invention
2016-09-07Security and Privacy in Radio Frequency Identification


Tags:
microsoft research