skip to main content

Title: On the spectrum problem for some digraphs of order 4 and size 6
Consider the multigraph obtained by adding a double edge to $K_4-e$. Now, let $D$ be a directed graph obtained by orientating the edges of that multigraph. We establish necessary and sufficient conditions on $n$ for the existence of a $(K^{*}_{n},D)$-design for four such orientations.
Authors:
; ; ; ; ; ;
Award ID(s):
1659815
Publication Date:
NSF-PAR ID:
10220712
Journal Name:
Journal of Combinatorial Mathematics and Combinatorial Computing (ISSN: 0835-3026)
Volume:
114
Page Range or eLocation-ID:
293-306
Sponsoring Org:
National Science Foundation
More Like this
  1. Lightness and sparsity are two natural parameters for Euclidean (1+ε)-spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in d-space admits an (1+ε)-spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)-spanner. They gave upper bounds of Õ(ε^{-(d+1)/2}) for the minimum lightness inmore »dimensions d ≥ 3, and Õ(ε^{-(d-1))/2}) for the minimum sparsity in d-space for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)-spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{-d/2}) for the lightness and Ω(ε^{-(d-1)/2}) for the sparsity of such spanners in Euclidean d-space for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)-spanners of lightness O(ε^{-1}log n) for n points in Euclidean plane.« less
  2. We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let f be an m -bit Boolean function and consider an n -bit function F obtained by applying f to conjunctions of possibly overlapping subsets of n variables. If f has quantum query complexity Q ( f ) , we give an algorithm for evaluating F using O ~ ( Q ( f ) ⋅ n ) quantum queries. This improves on the bound of O ( Q ( f ) ⋅ n ) that follows by treating each conjunction independently, and ourmore »bound is tight for worst-case choices of f . Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of f .By recursively applying our composition theorems, we obtain a nearly optimal O ~ ( n 1 − 2 − d ) upper bound on the quantum query complexity and approximate degree of linear-size depth- d AC 0 circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC 0 circuits.As an additional consequence, we show that AC 0 ∘ ⊕ circuits of depth d + 1 require size Ω ~ ( n 1 / ( 1 − 2 − d ) ) ≥ ω ( n 1 + 2 − d ) to compute the Inner Product function even on average. The previous best size lower bound was Ω ( n 1 + 4 − ( d + 1 ) ) and only held in the worst case (Cheraghchi et al., JCSS 2018).« less
  3. Sum frequency generation (SFG) * Equal contributors. spectroscopy was used to deduce the orientation of the terminal methyl (CH 3 ) group of self-assembled monolayers (SAMs) at the air–solid and air–liquid interfaces at surface concentrations as low as 1% protonated molecules in the presence of 99% deuterated molecules. The SFG spectra of octadecanethiol (ODT) and deuterated octadecanethiol (d 37 ODT) SAMs on gold were used for analysis at the air–solid interface. However, the eicosanoic acid (EA) and deuterated EA (d 39 EA) SAMs on the water were analyzed at the air–liquid interface. The tilt angle of the terminal CH 3more »group was estimated to be ∼39 ° for a SAM of 1% ODT : 99% d 37 ODT, whereas the tilt angle of the terminal CH 3 group of the 1% EA : 99% d 39 EA monolayer was estimated to be ∼32 °. The reliability of the orientational analysis at low concentrations was validated by testing the sensitivity of the SFG spectroscopy. A signal-to-noise (S/N) ratio of ∼60 and ∼45 was obtained for the CH 3 symmetric stretch (SS) of 1% ODT : 99% d 37 ODT and 1% EA : 99% d 39 EA, respectively. The estimated increase in S/N ratio values, as a measure of the sensitivity of the SFG spectroscopy, verified the capacity to acquire the SFG spectra at low concentrations of interfacial molecules under ambient conditions. Overall, the orientational analysis of CH 3 SS vibrational mode was feasible at low concentrations of protonated molecules due to increased S/N ratio. In support, the improved S/N ratio on varying incident power density of the visible beam was also experimentally demonstrated.« less
  4. We consider the problem of designing sublinear time algorithms for estimating the cost of minimum] metric traveling salesman (TSP) tour. Specifically, given access to a n × n distance matrix D that specifies pairwise distances between n points, the goal is to estimate the TSP cost by performing only sublinear (in the size of D) queries. For the closely related problem of estimating the weight of a metric minimum spanning tree (MST), it is known that for any epsilon > 0, there exists an O^~(n/epsilon^O(1))-time algorithm that returns a (1+epsilon)-approximate estimate of the MST cost. This result immediately implies anmore »O^~(n/epsilon^O(1)) time algorithm to estimate the TSP cost to within a (2 + epsilon) factor for any epsilon > 0. However, no o(n^2)-time algorithms are known to approximate metric TSP to a factor that is strictly better than 2. On the other hand, there were also no known barriers that rule out existence of (1 + epsilon)-approximate estimation algorithms for metric TSP with O^~ (n) time for any fixed epsilon > 0. In this paper, we make progress on both algorithms and lower bounds for estimating metric TSP cost. On the algorithmic side, we first consider the graphic TSP problem where the metric D corresponds to shortest path distances in a connected unweighted undirected graph. We show that there exists an O^~(n) time algorithm that estimates the cost of graphic TSP to within a factor of (2 − epsilon_0) for some epsilon_0 > 0. This is the first sublinear cost estimation algorithm for graphic TSP that achieves an approximation factor less than 2. We also consider another well-studied special case of metric TSP, namely, (1, 2)-TSP where all distances are either 1 or 2, and give an O^~(n ^ 1.5) time algorithm to estimate optimal cost to within a factor of 1.625. Our estimation algorithms for graphic TSP as well as for (1, 2)-TSP naturally lend themselves to O^~(n) space streaming algorithms that give an 11/6-approximation for graphic TSP and a 1.625-approximation for (1, 2)-TSP. These results motivate the natural question if analogously to metric MST, for any epsilon > 0, (1 + epsilon)-approximate estimates can be obtained for graphic TSP and (1, 2)-TSP using O^~ (n) queries. We answer this question in the negative – there exists an epsilon_0 > 0, such that any algorithm that estimates the cost of graphic TSP ((1, 2)-TSP) to within a (1 + epsilon_0)-factor, necessarily requires (n^2) queries. This lower bound result highlights a sharp separation between the metric MST and metric TSP problems. Similarly to many classical approximation algorithms for TSP, our sublinear time estimation algorithms utilize subroutines for estimating the size of a maximum matching in the underlying graph. We show that this is not merely an artifact of our approach, and that for any epsilon > 0, any algorithm that estimates the cost of graphic TSP or (1, 2)-TSP to within a (1 + epsilon)-factor, can also be used to estimate the size of a maximum matching in a bipartite graph to within an epsilon n additive error. This connection allows us to translate known lower bounds for matching size estimation in various models to similar lower bounds for metric TSP cost estimation.« less
  5. A quantitative understanding of the nanoscale piezoelectric property will unlock many application potentials of the electromechanical coupling phenomenon under quantum confinement. In this work, we present an atomic force microscopy- (AFM-) based approach to the quantification of the nanometer-scale piezoelectric property from single-crystalline zinc oxide nanosheets (NSs) with thicknesses ranging from 1 to 4 nm. By identifying the appropriate driving potential, we minimized the influences from electrostatic interactions and tip-sample coupling, and extrapolated the thickness-dependent piezoelectric coefficient ( d 33 ). By averaging the measured d 33 from NSs with the same number of unit cells in thickness, an intriguing tri-unit-cellmore »relationship was observed. From NSs with 3 n unit cell thickness ( n = 1 , 2, 3), a bulk-like d 33 at a value of ~9 pm/V was obtained, whereas NSs with other thickness showed a ~30% higher d 33 of ~12 pm/V. Quantification of d 33 as a function of ZnO unit cell numbers offers a new experimental discovery toward nanoscale piezoelectricity from nonlayered materials that are piezoelectric in bulk.« less