Source author record

Huseyin Acan

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 Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

7works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

On random trees obtained from permutation graphs

A permutation $\boldsymbol w$ gives rise to a graph $G_{\boldsymbol w}$ ; the vertices of $G_{\boldsymbol w}$ are the letters in the permutation and the edges of $G_{\boldsymbol w}$ are the inversions of $\boldsymbol w$ . We find that the number of trees among permutation graphs with $n$ vertices is $2^{n-2}$ for $n\ge 2$ . We then study $T_n$ , a uniformly random tree from this set of trees. In particular, we study the number of vertices of a given degree in $T_n$ , the maximum degree in $T_n$ , the diameter of $T_n$ , and the domination number of $T_n$ . Denoting the number of degree- $k$ vertices in $T_n$ by $D_k$ , we find that $(D_1,\dots,D_m)$ converges to a normal distribution for any fixed $m$ as $n\to \infty$ . The vertex domination number of $T_n$ is also asymptotically normally distributed as $n\to \infty$ . The diameter of $T_n$ shifted by $-2$ is binomially distributed with parameters $n-3$ and $1/2$ . Finally, we find the asymptotic distribution of the maximum degree in $T_n$ , which is concentrated around $\log_2n$ .

preprint2015arXiv

Forests of chord diagrams with a given number of trees

In this short note, we find the number of forests of chord diagrams with a given number of trees and a given number of chords.

preprint2015arXiv

On a uniformly random chord diagram and its intersection graph

A chord diagram refers to a set of chords with distinct endpoints on a circle. The intersection graph of a chord diagram $\cal C$ is defined by substituting the chords of $\cal C$ with vertices and by adding edges between two vertices whenever the corresponding two chords cross each other. Let $C_n$ and $G_n$ denote the chord diagram chosen uniformly at random from all chord diagrams with $n$ chords and the corresponding intersection graph, respectively. We analyze $C_n$ and $G_n$ as $n$ tends to infinity. In particular, we study the degree of a random vertex in $G_n$ , the $k$ -core of $G_n$ , and the number of strong components of the directed graph obtained from $G_n$ by orienting edges by flipping a fair coin for each edge. We also give two equivalent evolutions of a random chord diagram and show that, with probability approaching $1$ , a chord diagram produced after $m$ steps of these evolutions becomes monolithic as $m$ tends to infinity and stays monolithic afterward forever.

preprint2015arXiv

On the push&pull protocol for rumour spreading

The asynchronous push&pull protocol, a randomized distributed algorithm for spreading a rumour in a graph $G$ , works as follows. Independent Poisson clocks of rate 1 are associated with the vertices of $G$ . Initially, one vertex of $G$ knows the rumour. Whenever the clock of a vertex $x$ rings, it calls a random neighbour $y$ : if $x$ knows the rumour and $y$ does not, then $x$ tells $y$ the rumour (a push operation), and if $x$ does not know the rumour and $y$ knows it, $y$ tells $x$ the rumour (a pull operation). The average spread time of $G$ is the expected time it takes for all vertices to know the rumour, and the guaranteed spread time of $G$ is the smallest time $t$ such that with probability at least $1-1/n$ , after time $t$ all vertices know the rumour. The synchronous variant of this protocol, in which each clock rings precisely at times $1,2,\dots$ , has been studied extensively. We prove the following results for any $n$ -vertex graph: In either version, the average spread time is at most linear even if only the pull operation is used, and the guaranteed spread time is within a logarithmic factor of the average spread time, so it is $O(n\log n)$ . In the asynchronous version, both the average and guaranteed spread times are $Ω(\log n)$ . We give examples of graphs illustrating that these bounds are best possible up to constant factors. We also prove theoretical relationships between the guaranteed spread times in the two versions. Firstly, in all graphs the guaranteed spread time in the asynchronous version is within an $O(\log n)$ factor of that in the synchronous version, and this is tight. Next, we find examples of graphs whose asynchronous spread times are logarithmic, but the synchronous versions are polynomially large. Finally, we show for any graph that the ratio of the synchronous spread time to the asynchronous spread time is $O(n^{2/3})$ .

preprint2014arXiv

Formation of a giant component in the intersection graph of a random chord diagram

We study the number of chords and the number of crossings in the largest component of a random chord diagram when the chords are sparsely crossing. This is equivalent to studying the number of vertices and the number of edges in the largest component of the random intersection graph. Denoting the number of chords by n and the number of crossings by m, when m/nlog(n) tends to a limit in (0,2/π^2), we show that the chord diagram chosen uniformly at random from all the diagrams with given parameters has a component containing almost all the crossings and a positive fraction of chords. On the other hand, when m < n/14, the size of the largest component is of size O(log n). One of the key analytical ingredients is an asymptotic expression for the number of chord diagrams with parameters n and m for m <(2/π^2)n\log(n), based on the Touchard-Riordan formula and the Jacobi identity for Euler partition function.

preprint2014arXiv

On a memory game and preferential attachment graphs

In a recent paper Velleman and Warrington analyzed the expected values of some of the parameters in a memory game, namely, the length of the game, the waiting time for the first match, and the number of lucky moves. In this paper we continue this direction of investigation and obtain the limiting distributions of those parameters. More specifically, we prove that when suitably normalized, these quantities converge in distribution to a normal, Rayleigh, and Poisson random variable, respectively. We also make a connection between the memory game and one of the models of preferential attachment graphs. In particular, as a by--product of our methods we obtain simpler proofs (although without rate of convergence) of some of the results of Peköz, Röllin, and Ross on the joint limiting distributions of the degrees of the first few vertices in preferential attachment graphs. For proving that the length of the game is asymptotically normal, our main technical tool is a limit result for the joint distribution of the number of balls in a multi--type generalized Pólya urn model.

preprint2013arXiv

On the connected components of a random permutation graph with a given number of edges

A permutation of [n] induces a graph on [n] such that the edges of the graph correspond to inversion pairs of the permutation. This graph is connected if and only if the corresponding permutation is indecomposable. Let s(n,m) denote a permutation chosen uniformly at random among all permutations of [n] with exactly m inversions. Let p(n,m) be the common value for the probabilities that s(n,m) is indecomposable or the corresponding graph is connected. We prove that p(n,m) is non-decreasing with m by constructing a Markov process in which s(n,m+1) is obtained from s(n,m) by increasing one of the components of the inversion sequence of s(n,m) by one. We show that, with probability approaching 1, the graph corresponding to s(n,m) becomes connected for m asymptotic to (6/(π^2))nln(n). More precisely, for m=(6n/(π^2)) [ln(n)+ lnln(n)/2+ ln(12)- ln(π)- 12/(π^2)+x_n], where |x_n|=o(lnlnln(n)), the number of components of the random graph is shown to be asymptotically 1+Poisson(e^{-x_n}). When x_n goes to negative infinity, the sizes of the largest and the smallest components, scaled by n, are asymptotic to the lengths of the largest and the smallest subintervals in a partition of [0,1] by [e^{-x_n}] randomly, and independently, scattered points.

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.

Huseyin Acan

Research overview

Is this your work?

7 publications

On random trees obtained from permutation graphs

Forests of chord diagrams with a given number of trees

On a uniformly random chord diagram and its intersection graph

On the push&pull protocol for rumour spreading

Formation of a giant component in the intersection graph of a random chord diagram

On a memory game and preferential attachment graphs

On the connected components of a random permutation graph with a given number of edges

See the researcher in context

Building this map preview