Source author record

Tamás Makai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Degree sequences of sufficiently dense random uniform hypergraphs

We find an asymptotic enumeration formula for the number of simple $r$ -uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$ -uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$ -uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.

preprint2021arXiv

The Size of the Giant Joint Component in a Binomial Random Double Graph

We study the joint components in a random `double graph' that is obtained by superposing red and blue binomial random graphs on $n$ ~vertices. A joint component is a maximal set of vertices, which contains both a red and a blue spanning tree. We show that there are critical pairs of red and blue edge densities at which a joint-giant component appears. In contrast to the standard binomial graph model, the phase transition is first order: the size of the largest joint component jumps from $O(1)$ vertices to $Θ(n)$ at the critical point. We connect this phenomenon to the properties of a certain bicoloured branching process.

preprint2019arXiv

The sharp threshold for jigsaw percolation in random graphs

We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are `jointly connected'. Bollobás, Riordan, Slivken and Smith proved that when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $Θ\left( \frac{1}{n\ln n} \right)$ . We show that this threshold is sharp, and that it lies at $\frac{1}{4n\ln n}$ .

preprint2016arXiv

A simple proof of almost percolation on G(n;p)

We consider bootstrap percolation on the binomial random graph $G(n,p)$ with infection threshold $r\in \mathbb{N}$ , an infection process which starts from a set of initially infected vertices and in each step every vertex with at least $r$ infected neighbours becomes infected. We improve the results of Janson, Łuczak, Turova, and Valier (2012) by strengthening the probability bounds on the number of infected vertices at the end of the process, using simple arguments based on martingales and giant components.

preprint2016arXiv

Bootstrap percolation on G(n,p) revisited

Bootstrap percolation on a graph with infection threshold $r\in \mathbb{N}$ is an infection process, which starts from a set of initially infected vertices and in each step every vertex with at least $r$ infected neighbours becomes infected. We consider bootstrap percolation on the binomial random graph $G(n,p)$ , which was investigated among others by Janson, Łuczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of infected vertices at the end of the process.

preprint2015arXiv

Properties of stochastic Kronecker graphs

The stochastic Kronecker graph model introduced by Leskovec et al. is a random graph with vertex set $\mathbb Z_2^n$ , where two vertices $u$ and $v$ are connected with probability $α^{{u}\cdot{v}}γ^{(1-{u})\cdot(1-{v})}β^{n-{u}\cdot{v}-(1-{u})\cdot(1-{v})}$ independently of the presence or absence of any other edge, for fixed parameters $0<α,β,γ<1$ . They have shown empirically that the degree sequence resembles a power law degree distribution. In this paper we show that the stochastic Kronecker graph a.a.s. does not feature a power law degree distribution for any parameters $0<α,β,γ<1$ . In addition, we analyze the number of subgraphs present in the stochastic Kronecker graph and study the typical neighborhood of any given vertex.

preprint2010arXiv

No Dense Subgraphs Appear in the Triangle-free Graph Process

Consider the triangle-free graph process, which starts from the empty graph on $n$ vertices and a random ordering of the possible ${n \choose 2}$ edges; the edges are added in this ordering provided the graph remains triangle free. We will show that there exists a constant $c$ such that no copy of any fixed finite triangle-free graph on $k$ vertices with at least $ck$ edges asymptotically almost surely appears in the triangle-free graph process.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.