BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Bhaswar B. Bhattacharya

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

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

Catalog footprint

Research overview

21works
16topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

21 publications

preprint2022arXiv

Fluctuations of Subgraph Counts in Graphon Based Random Graphs

Given a graphon WW and a finite simple graph HH, with vertex set V(H)V(H), denote by Xn(H,W)X_n(H, W) the number of copies of HH in a WW-random graph on nn vertices. The asymptotic distribution of Xn(H,W)X_n(H, W) was recently obtained by Hladký, Pelekis, and Šileikis (2021) in the case where HH is a clique. In this paper, we extend this result to any fixed graph HH. Towards this we introduce a notion of HH-regularity of graphons and show that if the graphon WW is not HH-regular, then Xn(H,W)X_n(H, W) has Gaussian fluctuations with scaling n∣V(H)∣−12n^{|V(H)|-\frac{1}{2}}. On the other hand, if WW is HH-regular, then the fluctuations are of order n∣V(H)∣−1n^{|V(H)|-1} and the limiting distribution of Xn(H,W)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 WW. Our proofs use the asymptotic theory of generalized UU-statistics developed by Janson and Nowicki (1991). We also investigate the structure of HH-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 HH-regular graphons WW for which both the Gaussian or the non-Gaussian components are degenerate, that is, Xn(H,W)X_n(H, W) has a degenerate limit even under the scaling n∣V(H)∣−1n^{|V(H)|-1}. We give an example of this degeneracy with H=K1,3H=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.

Open access
preprint2022arXiv

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

In this paper we consider the problem of parameter estimation in the pp-spin Curie-Weiss model, for p≥3p \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 pp-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 pp. 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 N34N^{\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.

Open 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 nn samples, whether a discrete distribution supported on dd elements differs from the uniform distribution only in ss (out of the dd) 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 nn and the signal strength ε\varepsilon with the dimension dd and the sparsity level ss. For instance, if the sample size is less than a threshold (which depends on dd and ss), 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χ^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 nn, dd, and ss. 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.

Open 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 KK-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 KK-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.

Open access
preprint2021arXiv

Monochromatic Subgraphs in Randomly Colored Graphons

Let T(H,Gn)T(H, G_n) be the number of monochromatic copies of a fixed connected graph HH in a uniformly random coloring of the vertices of the graph GnG_n. In this paper we give a complete characterization of the limiting distribution of T(H,Gn)T(H, G_n), when {Gn}n≥1\{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,Gn)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,Gn)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(Ks,Kn)T(K_s, K_n), the number of monochromatic ss-cliques in a complete graph KnK_n (ss-matching birthdays among a group of nn friends), to general monochromatic subgraphs in a network.

Open 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.

Open 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.

Open access
preprint2020arXiv

Estimation in Tensor Ising Models

The pp-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≥2p \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 pp-tensor Ising model given a single sample from the distribution on NN 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 N\sqrt N-consistent, that is, it converges to the true parameter at rate 1/N1/\sqrt N. In particular, we show the N\sqrt N-consistency of the MPL estimate in the pp-spin Sherrington-Kirkpatrick (SK) model, spin systems on general pp-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 N\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 pp-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.

Open 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)G(n,n, p) and random graphs G(n,p)G(n, p), in various regimes of pp.

Open access
preprint2020arXiv

Geometric Systems of Unbiased Representatives

Let PP be a set of points in Rd\mathbb{R}^d, BB a bicoloring of PP and $\Oo$ a family of geometric objects (that is, intervals, boxes, balls, etc). An object from $\Oo$ is called balanced with respect to BB if it contains the same number of points from each color of BB. For a collection $\B$ of bicolorings of PP, a geometric system of unbiased representatives (G-SUR) is a subset $\Oo'\subseteq\Oo$ such that for any bicoloring BB of $\B$ there is an object in $\Oo'$ that is balanced with respect to BB. 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.

Open access
preprint2020arXiv

Normal Approximation and Fourth Moment Theorems for Monochromatic Triangles

Given a graph sequence {Gn}n≥1\{G_n\}_{n \geq 1} denote by T3(Gn)T_3(G_n) the number of monochromatic triangles in a uniformly random coloring of the vertices of GnG_n with c≥2c \geq 2 colors. This arises as a generalization of the birthday paradox, where GnG_n corresponds to a friendship network and T3(Gn)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 T3(Gn)T_3(G_n) with explicit error rates. The proof involves constructing a martingale difference sequence by carefully ordering the vertices of GnG_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≥5c \geq 5. We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any c≥2c \geq 2, which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of T3(Gn)T_3(G_n), whenever c≥5c \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).

Open 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 Gn,p\mathcal{G}_{n,p}, in the regime of pp 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≥1r \geq 1 fixed, we pin down the asymptotic probability that the top rr eigenvalues are jointly greater/less than their typical values by multiplicative factors bigger/smaller than 11, 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 KK-th largest degree of a graph is not atypically small (for some large KK depending on rr), then either the top eigenvalue or the rr-th largest eigenvalue is larger than that allowed by the lower tail event on the top rr 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.

Open access
preprint2020arXiv

The Second Moment Phenomenon for Monochromatic Subgraphs

What is the chance that among a group of nn friends, there are ss friends all of whom have the same birthday? This is the celebrated birthday problem which can be formulated as the existence of a monochromatic ss-clique KsK_s (ss-matching birthdays) in the complete graph KnK_n, where every vertex of KnK_n is uniformly colored with 365365 colors (corresponding to birthdays). More generally, for a general connected graph HH, let T(H,Gn)T(H, G_n) be the number of monochromatic copies of HH in a uniformly random coloring of the vertices of the graph GnG_n with cnc_n colors. In this paper we show that T(H,Gn)T(H, G_n) converges to Pois(λ)\mathrm{Pois}(λ) whenever ET(H,Gn)→λ\mathbb E T(H, G_n) \rightarrow λ and VarT(H,Gn)→λ\mathrm{Var} T(H, G_n) \rightarrow λ, that is, the asymptotic Poisson distribution of T(H,Gn)T(H, G_n) is determined just by the convergence of its mean and variance. Moreover, this condition is necessary if and only if HH is a star-graph. In fact, the second-moment phenomenon is a consequence of a more general theorem about the convergence of T(H,Gn)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,Gn)T(H, G_n), when Gn∼G(n,p)G_n\sim G(n, p) is the Erd\H os-Rényi random graph. Multiple phase-transitions emerge as pp varies from 0 to 1, depending on whether the graph HH is balanced or unbalanced.

Open 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 qq 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 qq-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.

Open access
preprint2015arXiv

Almost Empty Monochromatic Triangles in Planar Point Sets

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

Open 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 HN(σ)=σTJσH_N(σ) = σ^T J σ, where the coupling matrix JJ 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 JJ. 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.

Open 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 ε>0\varepsilon > 0, m1m_1 independent draws from an unknown distribution p,p, and m2m_2 draws from an unknown distribution qq, we describe a test for distinguishing the case that p=qp=q from the case that ∣∣p−q∣∣1≥ε||p-q||_1 \geq \varepsilon. If pp and qq are supported on at most nn elements, then our test is successful with high probability provided m1≥n2/3/ε4/3m_1\geq n^{2/3}/\varepsilon^{4/3} and m2=Ω(max⁡{nm1ε2,nε2});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 nn and ε\varepsilon. As a consequence, we obtain an algorithm for estimating the mixing time of a Markov chain on nn states up to a log⁡n\log n factor that uses O~(n3/2τmix)\tilde{O}(n^{3/2} τ_{mix}) queries to a "next node" oracle, improving upon the O~(n5/3τmix)\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.

Open 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)ψ(n) satisfies, 34⌊n4⌋≤ψ(n)≤⌈n4⌉\frac{3}{4}\lfloor\frac{n}{4}\rfloor\leq ψ(n)\leq\lceil\frac{n}{4}\rceil. In this paper we prove that ψ(13)=3ψ(13)=3, which immediately improves the upper bound on ψ(n)ψ(n) to ⌈3n13⌉\lceil\frac{3n}{13}\rceil, thus answering a question posed by Aichholzer et al. in the same paper.

Open access
preprint2012arXiv

Holes or Empty Pseudo-Triangles in Planar Point Sets

Let E(k,ℓ)E(k, \ell) denote the smallest integer such that any set of at least E(k,ℓ)E(k, \ell) points in the plane, no three on a line, contains either an empty convex polygon with kk vertices or an empty pseudo-triangle with ℓ\ell vertices. The existence of E(k,ℓ)E(k, \ell) for positive integers k,ℓ≥3k, \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)E(k, 5) and E(5,ℓ)E(5, \ell), and prove bounds on E(k,6)E(k, 6) and E(6,ℓ)E(6, \ell), for k,ℓ≥3k, \ell\geq 3. By dropping the emptiness condition, we define another related quantity F(k,ℓ)F(k, \ell), which is the smallest integer such that any set of at least F(k,ℓ)F(k, \ell) points in the plane, no three on a line, contains a convex polygon with kk 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)F(k, 5) and F(k,6)F(k, 6), and obtain non-trivial bounds on F(k,7)F(k, 7).

Open 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 H=(V,E)\mathcal H=(\mathcal V, \mathcal E), a function λ:V→Z+∪{0}λ: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\} is said to be an {\it edge-discriminator} on H\mathcal H if ∑v∈Eiλ(v)>0\sum_{v\in E_i}{λ(v)}>0, for all hyperedges Ei∈EE_i\in \mathcal E, and ∑v∈Eiλ(v)≠∑v∈Ejλ(v)\sum_{v\in E_i}{λ(v)}\ne \sum_{v\in E_j}{λ(v)}, for every two distinct hyperedges Ei,Ej∈EE_i, E_j \in \mathcal E. An {\it optimal edge-discriminator} on H\mathcal H, to be denoted by λHλ_\mathcal H, is an edge-discriminator on H\mathcal H satisfying ∑v∈VλH(v)=min⁡λ∑v∈Vλ(v)\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 H\mathcal H. We prove that any hypergraph H=(V,E)\mathcal H=(\mathcal V, \mathcal E), with ∣E∣=n|\mathcal E|=n, satisfies ∑v∈VλH(v)≤n(n+1)/2\sum_{v\in \mathcal V} λ_\mathcal H(v)\leq n(n+1)/2, and equality holds if and only if the elements of E\mathcal E are mutually disjoint. For rr-uniform hypergraphs H=(V,E)\mathcal H=(\mathcal V, \mathcal E), it follows from results on Sidon sequences that ∑v∈VλH(v)≤∣V∣r+1+o(∣V∣r+1)\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 rr-uniform hypergraph. Next, we construct optimal edge-discriminators for some special hypergraphs, which include paths, cycles, and complete rr-partite hypergraphs. Finally, we show that no optimal edge-discriminator on any hypergraph H=(V,E)\mathcal H=(\mathcal V, \mathcal E), with ∣E∣=n(≥3)|\mathcal E|=n (\geq 3), satisfies ∑v∈VλH(v)=n(n+1)/2−1\sum_{v\in \mathcal V} λ_\mathcal H (v)=n(n+1)/2-1, which, in turn, raises many other interesting combinatorial questions.

Open 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 kk-chain of a regular nn-gon is the segment of the boundary of the regular nn-gon formed by a set of k(≤n)k(\leq n) consecutive vertices of the regular nn-gon. We show that for every odd positive integer kk, there exists an integer N(k)N(k), such that the Fermat-Weber point of a set of kk fixed points lying on the vertices a kk-chain of a nn-gon coincides with a vertex of the chain whenever n≥N(k)n\geq N(k). We also show that ⌈πm(m+1)−π2/4⌉≤N(k)≤⌊πm(m+1)+1⌋\lceilπm(m+1)-π^2/4\rceil \leq N(k) \leq \lfloorπm(m+1)+1\rfloor, where k(=2m+1)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(hklog⁡k)O(hk\log k) time algorithm for determining whether a given set of kk points, having hh points on the convex hull, belongs to such a family.

Open access

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.