Source author record

Lale Özkahya

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Social and Information Networks

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A Fast Counting Method for 6-motifs with Low Connectivity

A $k$ -motif (or graphlet) is a subgraph on $k$ nodes in a graph or network. Counting of motifs in complex networks has been a well-studied problem in network analysis of various real-word graphs arising from the study of social networks and bioinformatics. In particular, the triangle counting problem has received much attention due to its significance in understanding the behavior of social networks. Similarly, subgraphs with more than 3 nodes have received much attention recently. While there have been successful methods developed on this problem, most of the existing algorithms are not scalable to large networks with millions of nodes and edges. The main contribution of this paper is a preliminary study that genaralizes the exact counting algorithm provided by Pinar, Seshadhri and Vishal to a collection of 6-motifs. This method uses the counts of motifs with smaller size to obtain the counts of 6-motifs with low connecivity, that is, containing a cut-vertex or a cut-edge. Therefore, it circumvents the combinatorial explosion that naturally arises when counting subgraphs in large networks.

preprint2014arXiv

On 3-uniform hypergraphs without a cycle of a given length

We study the maximum number of hyperedges in a 3-uniform hypergraph on $n$ vertices that does not contain a Berge cycle of a given length $\ell$ . In particular we prove that the upper bound for $C_{2k+1}$ -free hypergraphs is of the order $O(k^2n^{1+1/k})$ , improving the upper bound of Györi and Lemons by a factor of $Θ(k^2)$ . Similar bounds are shown for linear hypergraphs.

preprint2012arXiv

On homometric sets in graphs

For a vertex set $S\subseteq V(G)$ in a graph $G$ , the {\em distance multiset}, $D(S)$ , is the multiset of pairwise distances between vertices of $S$ in $G$ . Two vertex sets are called {\em homometric} if their distance multisets are identical. For a graph $G$ , the largest integer $h$ , such that there are two disjoint homometric sets of order $h$ in $G$ , is denoted by $h(G)$ . We slightly improve the general bound on this parameter introduced by Albertson, Pach and Young (2010) and investigate it in more detail for trees and graphs of bounded diameter. In particular, we show that for any tree $T$ on $n$ vertices $h(T) \geq \sqrt[3]{n}$ and for any graph $G$ of fixed diameter $d$ , $h(G) \geq cn^{1/ (2d-2)}$ .

preprint2011arXiv

On a covering problem in the hypercube

In this paper, we address a particular variation of the Turán problem for the hypercube. Alon, Krech and Szabó (2007) asked "In an n-dimensional hypercube, Qn, and for l < d < n, what is the size of a smallest set, S, of Q_l's so that every Q_d contains at least one member of S?" Likewise, they asked a similar Ramsey type question: "What is the largest number of colors that we can use to color the copies of Q_l in Q_n such that each Q_d contains a Q_l of each color?" We give upper and lower bounds for each of these questions and provide constructions of the set S above for some specific cases.

preprint2011arXiv

On the ratio of maximum and minimum degree in maximal intersecting families

To study how balanced or unbalanced a maximal intersecting family $\mathcal{F}\subseteq \binom{[n]}{r}$ is we consider the ratio $\mathcal{R}(\mathcal{F})=\frac{Δ(\mathcal{F})}{δ(\mathcal{F})}$ of its maximum and minimum degree. We determine the order of magnitude of the function $m(n,r)$ , the minimum possible value of $\mathcal{R}(\mathcal{F})$ , and establish some lower and upper bounds on the function $M(n,r)$ , the maximum possible value of $\mathcal{R}(\mathcal{F})$ . To obtain constructions that show the bounds on $m(n,r)$ we use a theorem of Blokhuis on the minimum size of a non-trivial blocking set in projective planes.

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.