Source author record

Huda Chuangpishit

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.MG math.PR

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Conditions on square geometric graphs

For any metric $d$ on $\mathbb{R}^2$ , an ( $\mathbb{R}^2,d$ )-geometric graph is a graph whose vertices are points in $\mathbb{R}^2$ , and two vertices are adjacent if and only if their distance is at most 1. If $d=\|.\|_{\infty}$ , the metric derived from the $L_{\infty}$ norm, then $(\mathbb{R} ^2,\|.\|_{\infty})$ -geometric graphs are precisely those graphs that are the intersection of two unit interval graphs. We refer to $(\mathbb{R}^2,\|.\|_{\infty})$ -geometric graphs as square geometric graphs. We represent a characterization of square geometric graphs. Using this characterization we provide necessary conditions for the class of square geometric $B_{a,b}$ -graphs, a generalization of cobipartite graphs. Then by applying some restrictions on these necessary conditions we obtain sufficient conditions for $B_{a,b}$ -graphs to be square geometric.

preprint2016arXiv

Uniform linear embeddings of graphons

Let $w:[0,1]^2\rightarrow [0,1]$ be a symmetric function, and consider the random process $G(n,w)$ , where vertices are chosen from $[0,1]$ uniformly at random, and $w$ governs the edge formation probability. Such a random graph is said to have a linear embedding, if the probability of linking to a particular vertex $v$ decreases with distance. The rate of decrease, in general, depends on the particular vertex $v$ . A linear embedding is called uniform if the probability of a link between two vertices depends only on the distance between them. In this article, we consider the question whether it is possible to "transform" a linear embedding to a uniform one, through replacing the uniform probability space $[0,1]$ with a suitable probability space on ${\mathbb R}$ . We give necessary and sufficient conditions for the existence of a uniform linear embedding for random graphs where $w$ attains only a finite number of values. Our findings show that for a general $w$ the answer is negative in most cases.

preprint2015arXiv

Linear embeddings of graphs and graph limits

Consider a random graph process where vertices are chosen from the interval $[0,1]$ , and edges are chosen independently at random, but so that, for a given vertex $x$ , the probability that there is an edge to a vertex $y$ decreases as the distance between $x$ and $y$ increases. We call this a random graph with a linear embedding. We define a new graph parameter $Γ^*$ , which aims to measure the similarity of the graph to an instance of a random graph with a linear embedding. For a graph $G$ , $Γ^*(G)=0$ if and only if $G$ is a unit interval graph, and thus a deterministic example of a graph with a linear embedding. We show that the behaviour of $Γ^*$ is consistent with the notion of convergence as defined in the theory of dense graph limits. In this theory, graph sequences converge to a symmetric, measurable function on $[0,1]^2$ . We define an operator $Γ$ which applies to graph limits, and which assumes the value zero precisely for graph limits that have a linear embedding. We show that, if a graph sequence $\{ G_n\}$ converges to a function $w$ , then $\{ Γ^*(G_n)\}$ converges as well. Moreover, there exists a function $w^*$ arbitrarily close to $w$ under the box distance, so that $\lim_{n\rightarrow \infty}Γ^*(G_n)$ is arbitrarily close to $Γ(w^*)$ .

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.