BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Bhaswar B. Bhattacharya

Bhaswar B. Bhattacharya appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRmath.STStatistics Theorymath-phmath.MPMethodologyComputational GeometryDiscrete MathematicsInformation TheoryMachine Learningmath.ITApplicationsCryptography and Securitymath.DGmath.MG

Catalog footprint

What is connected

21works
16topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

21 published item(s)

preprint2022arXiv

Fluctuations of Subgraph Counts in Graphon Based Random Graphs

Given a graphon $W$ and a finite simple graph $H$, with vertex set $V(H)$, denote by $X_n(H, W)$ the number of copies of $H$ in a $W$-random graph on $n$ vertices. The asymptotic distribution of $X_n(H, W)$ was recently obtained by Hladký, Pelekis, and Šileikis (2021) in the case where $H$ is a clique. In this paper, we extend this result to any fixed graph $H$. Towards this we introduce a notion of $H$-regularity of graphons and show that if the graphon $W$ is not $H$-regular, then $X_n(H, W)$ has Gaussian fluctuations with scaling $n^{|V(H)|-\frac{1}{2}}$. On the other hand, if $W$ is $H$-regular, then the fluctuations are of order $n^{|V(H)|-1}$ and the limiting distribution of $X_n(H, W)$ can have both Gaussian and non-Gaussian components, where the non-Gaussian component is a (possibly) infinite weighted sum of centered chi-squared random variables with the weights determined by the spectral properties of a graphon derived from $W$. Our proofs use the asymptotic theory of generalized $U$-statistics developed by Janson and Nowicki (1991). We also investigate the structure of $H$-regular graphons for which either the Gaussian or the non-Gaussian component of the limiting distribution (but not both) is degenerate. Interestingly, there are also $H$-regular graphons $W$ for which both the Gaussian or the non-Gaussian components are degenerate, that is, $X_n(H, W)$ has a degenerate limit even under the scaling $n^{|V(H)|-1}$. We give an example of this degeneracy with $H=K_{1, 3}$ (the 3-star) and also establish non-degeneracy in a few examples. This naturally leads to interesting open questions on higher-order degeneracies.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Phase Transitions of the Maximum Likelihood Estimates in the $p$-Spin Curie-Weiss Model

In this paper we consider the problem of parameter estimation in the $p$-spin Curie-Weiss model, for $p \geq 3$. We provide a complete description of the limiting properties of the maximum likelihood (ML) estimates of the inverse temperature and the magnetic field given a single realization from the $p$-spin Curie-Weiss model, complementing the well-known results in the 2-spin case (Comets and Gidas (1991)). Our results unearth various new phase transitions and surprising limit theorems, such as the existence of a 'critical' curve in the parameter space, where the limiting distribution of the ML estimates is a mixture with both continuous and discrete components. The number of mixture components is either two or three, depending on, among other things, the sign of one of the parameters and the parity of $p$. Another interesting revelation is the existence of certain 'special' points in the parameter space where the ML estimates exhibit a superefficiency phenomenon, converging to a non-Gaussian limiting distribution at rate $N^{\frac{3}{4}}$. Using these results we can obtain asymptotically valid confidence intervals for the inverse temperature and the magnetic field at all points in the parameter space where consistent estimation is possible.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sparse Uniformity Testing

In this paper we consider the uniformity testing problem for high-dimensional discrete distributions (multinomials) under sparse alternatives. More precisely, we derive sharp detection thresholds for testing, based on $n$ samples, whether a discrete distribution supported on $d$ elements differs from the uniform distribution only in $s$ (out of the $d$) coordinates and is $\varepsilon$-far (in total variation distance) from uniformity. Our results reveal various interesting phase transitions which depend on the interplay of the sample size $n$ and the signal strength $\varepsilon$ with the dimension $d$ and the sparsity level $s$. For instance, if the sample size is less than a threshold (which depends on $d$ and $s$), then all tests are asymptotically powerless, irrespective of the magnitude of the signal strength. On the other hand, if the sample size is above the threshold, then the detection boundary undergoes a further phase transition depending on the signal strength. Here, a $χ^2$-type test attains the detection boundary in the dense regime, whereas in the sparse regime a Bonferroni correction of two maximum-type tests and a version of the Higher Criticism test is optimal up to sharp constants. These results combined provide a complete description of the phase diagram for the sparse uniformity testing problem across all regimes of the parameters $n$, $d$, and $s$. One of the challenges in dealing with multinomials is that the parameters are always constrained to lie in the simplex. This results in the aforementioned two-layered phase transition, a new phenomenon which does not arise in classical high-dimensional sparse testing problems.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Asymptotic Distribution and Detection Thresholds for Two-Sample Tests Based on Geometric Graphs

In this paper, we consider the problem of testing the equality of two multivariate distributions based on geometric graphs constructed using the interpoint distances between the observations. These include the tests based on the minimum spanning tree and the $K$-nearest neighbor (NN) graphs, among others. These tests are asymptotically distribution-free, universally consistent and computationally efficient, making them particularly useful in modern applications. However, very little is known about the power properties of these tests. In this paper, using the theory of stabilizing geometric graphs, we derive the asymptotic distribution of these tests under general alternatives, in the Poissonized setting. Using this, the detection threshold and the limiting local power of the test based on the $K$-NN graph are obtained, where interesting exponents depending on dimension emerge. This provides a way to compare and justify the performance of these tests in different examples.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Monochromatic Subgraphs in Randomly Colored Graphons

Let $T(H, G_n)$ be the number of monochromatic copies of a fixed connected graph $H$ in a uniformly random coloring of the vertices of the graph $G_n$. In this paper we give a complete characterization of the limiting distribution of $T(H, G_n)$, when $\{G_n\}_{n \geq 1}$ is a converging sequence of dense graphs. When the number of colors grows to infinity, depending on whether the expected value remains bounded, $T(H, G_n)$ either converges to a finite linear combination of independent Poisson variables or a normal distribution. On the other hand, when the number of colors is fixed, $T(H, G_n)$ converges to a (possibly infinite) linear combination of independent centered chi-squared random variables. This generalizes the classical birthday problem, which involves understanding the asymptotics of $T(K_s, K_n)$, the number of monochromatic $s$-cliques in a complete graph $K_n$ ($s$-matching birthdays among a group of $n$ friends), to general monochromatic subgraphs in a network.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Nearest-Neighbor Based Nonparametric Test for Viral Remodeling in Heterogeneous Single-Cell Proteomic Data

An important problem in contemporary immunology studies based on single-cell protein expression data is to determine whether cellular expressions are remodeled post infection by a pathogen. One natural approach for detecting such changes is to use non-parametric two-sample statistical tests. However, in single-cell studies, direct application of these tests is often inadequate because single-cell level expression data from uninfected populations often contains attributes of several latent sub-populations with highly heterogeneous characteristics. As a result, viruses often infect these different sub-populations at different rates in which case the traditional nonparametric two-sample tests for checking similarity in distributions are no longer conservative. We propose a new nonparametric method for Testing Remodeling Under Heterogeneity (TRUH) that can accurately detect changes in the infected samples compared to possibly heterogeneous uninfected samples. Our testing framework is based on composite nulls and is designed to allow the null model to encompass the possibility that the infected samples, though unaltered by the virus, might be dominantly arising from under-represented sub-populations in the baseline data. The TRUH statistic, which uses nearest neighbor projections of the infected samples into the baseline uninfected population, is calibrated using a novel bootstrap algorithm. We demonstrate the non-asymptotic performance of the test via simulation experiments and derive the large sample limit of the test statistic, which provides theoretical support towards consistent asymptotic calibration of the test. We use the TRUH statistic for studying remodeling in tonsillar T cells under different types of HIV infection and find that unlike traditional tests, TRUH based statistical inference conforms to the biologically validated immunological theories on HIV infection.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Nonparametric Likelihood Approach for Inference in Instrumental Variable Models

Instrumental variable methods allow for inference about the treatment effect by controlling for unmeasured confounding in randomized experiments with noncompliance. However, many studies do not consider the observed compliance behavior in the testing procedure, which can lead to a loss of power. In this paper, we propose a novel nonparametric likelihood approach, referred to as the binomial likelihood (BL) method, that incorporates information on compliance behavior while overcoming several limitations of previous techniques and utilizing the advantages of likelihood methods. Our proposed method produces proper estimates of the counterfactual distribution functions by maximizing the binomial likelihood over the space of distribution functions. Using this we propose two versions of a binomial likelihood ratio test for the null hypothesis of no treatment effect. We show that both versions are more powerful to detect any distributional change than existing methods in finite sample cases, and are asymptotically equivalent to the two-sample Anderson-Darling test. We also develop an efficient algorithm for computing our estimates, and apply the binomial likelihood method to a study of the effect of Medicaid coverage on mental health using the Oregon Health Insurance Experiment.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Estimation in Tensor Ising Models

The $p$-tensor Ising model is a one-parameter discrete exponential family for modeling dependent binary data, where the sufficient statistic is a multi-linear form of degree $p \geq 2$. This is a natural generalization of the matrix Ising model, that provides a convenient mathematical framework for capturing higher-order dependencies in complex relational data. In this paper, we consider the problem of estimating the natural parameter of the $p$-tensor Ising model given a single sample from the distribution on $N$ nodes. Our estimate is based on the maximum pseudo-likelihood (MPL) method, which provides a computationally efficient algorithm for estimating the parameter that avoids computing the intractable partition function. We derive general conditions under which the MPL estimate is $\sqrt N$-consistent, that is, it converges to the true parameter at rate $1/\sqrt N$. In particular, we show the $\sqrt N$-consistency of the MPL estimate in the $p$-spin Sherrington-Kirkpatrick (SK) model, spin systems on general $p$-uniform hypergraphs, and Ising models on the hypergraph stochastic block model (HSBM). In fact, for the HSBM we pin down the exact location of the phase transition threshold, which is determined by the positivity of a certain mean-field variational problem, such that above this threshold the MPL estimate is $\sqrt N$-consistent, while below the threshold no estimator is consistent. Finally, we derive the precise fluctuations of the MPL estimate in the special case of the $p$-tensor Curie-Weiss model. An interesting consequence of our results is that the MPL estimate in the Curie-Weiss model saturates the Cramer-Rao lower bound at all points above the estimation threshold, that is, the MPL estimate incurs no loss in asymptotic efficiency, even though it is obtained by minimizing only an approximation of the true likelihood function for computational tractability.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Exact and Asymptotic Results on Coarse Ricci Curvature of Graphs

Ricci curvature was proposed by Ollivier in a general framework of metric measure spaces, and it has been studied extensively in the context of graphs in recent years. In this paper we prove upper bounds for Ollivier's Ricci curvature for bipartite graphs and for the graphs with girth at least 5. We also prove a general lower bound on the Ricci curvature in terms of the size of the maximum matching in an appropriate subgraph. As a consequence, we characterize the Ricci-flat graphs of girth 5. Moreover, using our general lower bound and the Birkhoff-von Neumann theorem, we give a necessary and sufficient condition for the structure of Ricci-flat regular graphs of girth 4. Finally, we obtain the asymptotic Ricci curvature of random bipartite graphs $G(n,n, p)$ and random graphs $G(n, p)$, in various regimes of $p$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Geometric Systems of Unbiased Representatives

Let $P$ be a set of points in $\mathbb{R}^d$, $B$ a bicoloring of $P$ and $\Oo$ a family of geometric objects (that is, intervals, boxes, balls, etc). An object from $\Oo$ is called balanced with respect to $B$ if it contains the same number of points from each color of $B$. For a collection $\B$ of bicolorings of $P$, a geometric system of unbiased representatives (G-SUR) is a subset $\Oo'\subseteq\Oo$ such that for any bicoloring $B$ of $\B$ there is an object in $\Oo'$ that is balanced with respect to $B$. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Normal Approximation and Fourth Moment Theorems for Monochromatic Triangles

Given a graph sequence $\{G_n\}_{n \geq 1}$ denote by $T_3(G_n)$ the number of monochromatic triangles in a uniformly random coloring of the vertices of $G_n$ with $c \geq 2$ colors. This arises as a generalization of the birthday paradox, where $G_n$ corresponds to a friendship network and $T_3(G_n)$ counts the number of triples of friends with matching birthdays. In this paper we prove a central limit theorem (CLT) for $T_3(G_n)$ with explicit error rates. The proof involves constructing a martingale difference sequence by carefully ordering the vertices of $G_n$, based on a certain combinatorial score function, and using a quantitive version of the martingale CLT. We then relate this error term to the well-known fourth moment phenomenon, which, interestingly, holds only when the number of colors $c \geq 5$. We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any $c \geq 2$, which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of $T_3(G_n)$, whenever $c \geq 5$. Finally, to illustrate the promise of our approach, we include an alternative proof of the CLT for the number of monochromatic edges, which provides quantitative rates for the results obtained in Bhattacharya et al. (2017).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Spectral Edge in Sparse Random Graphs: Upper and Lower Tail Large Deviations

In this paper we consider the problem of estimating the joint upper and lower tail large deviations of the edge eigenvalues of an Erdős-Rényi random graph $\mathcal{G}_{n,p}$, in the regime of $p$ where the edge of the spectrum is no longer governed by global observables, such as the number of edges, but rather by localized statistics, such as high degree vertices. Going beyond the recent developments in mean-field approximations of related problems, this paper provides a comprehensive treatment of the large deviations of the spectral edge in this entire regime, which notably includes the well studied case of constant average degree. In particular, for $r \geq 1$ fixed, we pin down the asymptotic probability that the top $r$ eigenvalues are jointly greater/less than their typical values by multiplicative factors bigger/smaller than $1$, in the regime mentioned above. The proof for the upper tail relies on a novel structure theorem, obtained by building on estimates of Krivelevich and Sudakov (2003), followed by an iterative cycle removal process, which shows, conditional on the upper tail large deviation event, with high probability the graph admits a decomposition in to a disjoint union of stars and a spectrally negligible part. On the other hand, the key ingredient in the proof of the lower tail is a Ramsey-type result which shows that if the $K$-th largest degree of a graph is not atypically small (for some large $K$ depending on $r$), then either the top eigenvalue or the $r$-th largest eigenvalue is larger than that allowed by the lower tail event on the top $r$ eigenvalues, thus forcing a contradiction. The above arguments reduce the problems to developing a large deviation theory for the extremal degrees which could be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Second Moment Phenomenon for Monochromatic Subgraphs

What is the chance that among a group of $n$ friends, there are $s$ friends all of whom have the same birthday? This is the celebrated birthday problem which can be formulated as the existence of a monochromatic $s$-clique $K_s$ ($s$-matching birthdays) in the complete graph $K_n$, where every vertex of $K_n$ is uniformly colored with $365$ colors (corresponding to birthdays). More generally, for a general connected graph $H$, let $T(H, G_n)$ be the number of monochromatic copies of $H$ in a uniformly random coloring of the vertices of the graph $G_n$ with $c_n$ colors. In this paper we show that $T(H, G_n)$ converges to $\mathrm{Pois}(λ)$ whenever $\mathbb E T(H, G_n) \rightarrow λ$ and $\mathrm{Var} T(H, G_n) \rightarrow λ$, that is, the asymptotic Poisson distribution of $T(H, G_n)$ is determined just by the convergence of its mean and variance. Moreover, this condition is necessary if and only if $H$ is a star-graph. In fact, the second-moment phenomenon is a consequence of a more general theorem about the convergence of $T(H,G_n)$ to a finite linear combination of independent Poisson random variables. As an application, we derive the limiting distribution of $T(H, G_n)$, when $G_n\sim G(n, p)$ is the Erd\H os-Rényi random graph. Multiple phase-transitions emerge as $p$ varies from 0 to 1, depending on whether the graph $H$ is balanced or unbalanced.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Collision Times in Multicolor Urn Models and Sequential Graph Coloring With Applications to Discrete Logarithms

Consider an urn model where at each step one of $q$ colors is sampled according to some probability distribution and a ball of that color is placed in an urn. The distribution of assigning balls to urns may depend on the color of the ball. Collisions occur when a ball is placed in an urn which already contains a ball of different color. Equivalently, this can be viewed as sequentially coloring a complete $q$-partite graph wherein a collision corresponds to the appearance of a monochromatic edge. Using a Poisson embedding technique, the limiting distribution of the first collision time is determined and the possible limits are explicitly described. Joint distribution of successive collision times and multi-fold collision times are also derived. The results can be used to obtain the limiting distributions of running times in various birthday problem based algorithms for solving the discrete logarithm problem, generalizing previous results which only consider expected running times. Asymptotic distributions of the time of appearance of a monochromatic edge are also obtained for other graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Almost Empty Monochromatic Triangles in Planar Point Sets

For positive integers $c, s \geq 1$, let $M_3(c, s)$ be the least integer such that any set of at least $M_3(c, s)$ points in the plane, no three on a line and colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. The case $s=0$, which corresponds to empty monochromatic triangles, has been studied extensively over the last few years. In particular, it is known that $M_3(1, 0)=3$, $M_3(2, 0)=9$ and $M_3(c, 0)=\infty$, for $c\geq 3$. In this paper we extend these results when $c \geq 2$ and $s \geq 1$. We prove that the least integer $λ_3(c)$ such that $M_3(c, λ_3(c))< \infty$ satisfies: $$\left\lfloor\frac{c-1}{2}\right\rfloor \leqλ_3(c)\leq c-2,$$ where $c \geq 2$. Moreover, the exact values of $M_3(c, s)$ are determined for small values of $c$ and $s$. We also conjecture that $λ_3(4)=1$, and verify it for sufficiently large Horton sets.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

High Temperature Asymptotics of Orthogonal Mean-Field Spin Glasses

We evaluate the high temperature limit of the free energy of spin glasses on the hypercube with Hamiltonian $H_N(σ) = σ^T J σ$, where the coupling matrix $J$ is drawn from certain symmetric orthogonally invariant ensembles. Our derivation relates the annealed free energy of these models to a spherical integral, and expresses the limit of the free energy in terms of the limiting spectral measure of the coupling matrix $J$. As an application, we derive the limiting free energy of the Random Orthogonal Model (ROM) at high temperatures, which confirms non-rigorous calculations of Marinari et al. (1994). Our methods also apply to other well-known models of disordered systems, including the SK and Gaussian Hopfield models.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Testing Closeness With Unequal Sized Samples

We consider the problem of closeness testing for two discrete distributions in the practically relevant setting of \emph{unequal} sized samples drawn from each of them. Specifically, given a target error parameter $\varepsilon > 0$, $m_1$ independent draws from an unknown distribution $p,$ and $m_2$ draws from an unknown distribution $q$, we describe a test for distinguishing the case that $p=q$ from the case that $||p-q||_1 \geq \varepsilon$. If $p$ and $q$ are supported on at most $n$ elements, then our test is successful with high probability provided $m_1\geq n^{2/3}/\varepsilon^{4/3}$ and $m_2 = Ω(\max\{\frac{n}{\sqrt m_1\varepsilon^2}, \frac{\sqrt n}{\varepsilon^2}\});$ we show that this tradeoff is optimal throughout this range, to constant factors. These results extend the recent work of Chan et al. who established the sample complexity when the two samples have equal sizes, and tightens the results of Acharya et al. by polynomials factors in both $n$ and $\varepsilon$. As a consequence, we obtain an algorithm for estimating the mixing time of a Markov chain on $n$ states up to a $\log n$ factor that uses $\tilde{O}(n^{3/2} τ_{mix})$ queries to a "next node" oracle, improving upon the $\tilde{O}(n^{5/3}τ_{mix})$ query algorithm of Batu et al. Finally, we note that the core of our testing algorithm is a relatively simple statistic that seems to perform well in practice, both on synthetic data and on natural language data.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Pseudo-Convex Partitions of a Planar Point Set

Aichholzer et al. [{\it Graphs and Combinatorics}, Vol. 23, 481-507, 2007] introduced the notion of pseudo-convex partitioning of planar point sets and proved that the pseudo-convex partition number $ψ(n)$ satisfies, $\frac{3}{4}\lfloor\frac{n}{4}\rfloor\leq ψ(n)\leq\lceil\frac{n}{4}\rceil$. In this paper we prove that $ψ(13)=3$, which immediately improves the upper bound on $ψ(n)$ to $\lceil\frac{3n}{13}\rceil$, thus answering a question posed by Aichholzer et al. in the same paper.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Holes or Empty Pseudo-Triangles in Planar Point Sets

Let $E(k, \ell)$ denote the smallest integer such that any set of at least $E(k, \ell)$ points in the plane, no three on a line, contains either an empty convex polygon with $k$ vertices or an empty pseudo-triangle with $\ell$ vertices. The existence of $E(k, \ell)$ for positive integers $k, \ell\geq 3$, is the consequence of a result proved by Valtr [Discrete and Computational Geometry, Vol. 37, 565--576, 2007]. In this paper, following a series of new results about the existence of empty pseudo-triangles in point sets with triangular convex hulls, we determine the exact values of $E(k, 5)$ and $E(5, \ell)$, and prove bounds on $E(k, 6)$ and $E(6, \ell)$, for $k, \ell\geq 3$. By dropping the emptiness condition, we define another related quantity $F(k, \ell)$, which is the smallest integer such that any set of at least $F(k, \ell)$ points in the plane, no three on a line, contains a convex polygon with $k$ vertices or a pseudo-triangle with $\ell$ vertices. Extending a result of Bisztriczky and Tóth [Discrete Geometry, Marcel Dekker, 49--58, 2003], we obtain the exact values of $F(k, 5)$ and $F(k, 6)$, and obtain non-trivial bounds on $F(k, 7)$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Minimum-Weight Edge Discriminator in Hypergraphs

In this paper we introduce the concept of minimum-weight edge-discriminators in hypergraphs, and study its various properties. For a hypergraph $\mathcal H=(\mathcal V, \mathcal E)$, a function $λ: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\}$ is said to be an {\it edge-discriminator} on $\mathcal H$ if $\sum_{v\in E_i}{λ(v)}>0$, for all hyperedges $E_i\in \mathcal E$, and $\sum_{v\in E_i}{λ(v)}\ne \sum_{v\in E_j}{λ(v)}$, for every two distinct hyperedges $E_i, E_j \in \mathcal E$. An {\it optimal edge-discriminator} on $\mathcal H$, to be denoted by $λ_\mathcal H$, is an edge-discriminator on $\mathcal H$ satisfying $\sum_{v\in \mathcal V}λ_\mathcal H (v)=\min_λ\sum_{v\in \mathcal V}{λ(v)}$, where the minimum is taken over all edge-discriminators on $\mathcal H$. We prove that any hypergraph $\mathcal H=(\mathcal V, \mathcal E)$, with $|\mathcal E|=n$, satisfies $\sum_{v\in \mathcal V} λ_\mathcal H(v)\leq n(n+1)/2$, and equality holds if and only if the elements of $\mathcal E$ are mutually disjoint. For $r$-uniform hypergraphs $\mathcal H=(\mathcal V, \mathcal E)$, it follows from results on Sidon sequences that $\sum_{v\in \mathcal V}λ_{\mathcal H}(v)\leq |\mathcal V|^{r+1}+o(|\mathcal V|^{r+1})$, and the bound is attained up to a constant factor by the complete $r$-uniform hypergraph. Next, we construct optimal edge-discriminators for some special hypergraphs, which include paths, cycles, and complete $r$-partite hypergraphs. Finally, we show that no optimal edge-discriminator on any hypergraph $\mathcal H=(\mathcal V, \mathcal E)$, with $|\mathcal E|=n (\geq 3)$, satisfies $\sum_{v\in \mathcal V} λ_\mathcal H (v)=n(n+1)/2-1$, which, in turn, raises many other interesting combinatorial questions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Fermat-Weber Point of a Polygonal Chain

In this paper, we study the properties of the Fermat-Weber point for a set of fixed points, whose arrangement coincides with the vertices of a regular polygonal chain. A $k$-chain of a regular $n$-gon is the segment of the boundary of the regular $n$-gon formed by a set of $k(\leq n)$ consecutive vertices of the regular $n$-gon. We show that for every odd positive integer $k$, there exists an integer $N(k)$, such that the Fermat-Weber point of a set of $k$ fixed points lying on the vertices a $k$-chain of a $n$-gon coincides with a vertex of the chain whenever $n\geq N(k)$. We also show that $\lceilπm(m+1)-π^2/4\rceil \leq N(k) \leq \lfloorπm(m+1)+1\rfloor$, where $k (=2m+1)$ is any odd positive integer. We then extend this result to a more general family of point set, and give an $O(hk\log k)$ time algorithm for determining whether a given set of $k$ points, having $h$ points on the convex hull, belongs to such a family.

0 citations0 reviewsNo code linkedOpen access