Lower bounds for testing triangle-freeness in Boolean functions

Given a Boolean function , we say a triple (x, y, x + y) is a triangle in f if . A triangle-free function contains no triangle. If f differs from every triangle-free function on at least points, then f is said to be -far from triangle-free. In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those -far from triangle-free. Let the canonical tester for triangle-freeness denotes the algorithm that repeatedly picks x and y uniformly and independently at random from , queries f(x), f(y) and f(x + y), and checks whether f(x) = f(y) = f(x + y) = 1. Green showed that the canonical tester rejects functions -far from triangle-free with constant probability if its query complexity is a tower of 2's whose height is polynomial in . Fox later improved the height of the tower in Green's upper bound to . A trivial lower bound of on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough , there exists an integer such that for all there exists a function depending on all n variables which is -far from being triangle-free and requires queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least queries.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

Effect of Channel Confinement on Mixed Convective Flow Past an Equilateral Triangular Cylinder

The present work investigates the mixed convective flow and heat transfer characteristics past a triangular cylinder placed symmetrically in a vertical channel. At a representative Reynolds number, Re = 100, simulations are carried out for the blockage ratios beta = 1/3; 1/4; and 1/6. Effect of aiding and opposing buoyancy is brought about by varying the Richardson number in the range -1.0 <= Ri <= 1.0. At a blockage ratio of 1/3, suppression of vortex shedding is found at Ri = 1, whereas von Karman vortex street is seen both at beta = 1/4 and 1/6, respectively. This is the first time that such behavior of blockage ratio past a triangular cylinder in the present flow configuration is reported. Drag coefficient increases progressively with increasing Ri and a slightly higher value is noticed at beta = 1/3. For all b, heat transfer increases with increasing Ri. Flattening of Nu(avg)-Ri curve beyond Ri > 0: 75 is observed at beta = 1/3.

Analysis of sine-triangle and zero-sequence injection modulation schemes for split-phase induction motor drive

A split-phase induction motor is fed from two three-phase voltage source inverters for speed control. This study analyses carrier-comparison based pulse width modulation (PWM) schemes for a split-phase motor drive, from a space-vector perspective. Sine-triangle PWM, one zero-sequence injection PWM where the same zero-sequence signal is used for both the inverters, and another zero-sequence injection PWM where different zero-sequence signals are employed for the two inverters are considered. The set of voltage vectors applied, the sequence in which the voltage vectors are applied, and the resulting current ripple vector are analysed for all the PWM methods. Besides all the PWM methods are compared in terms of dc bus utilisation. For the same three-phase sine reference, the PWM method with different zero-sequence signals for the two inverters is found to employ a set of vectors different from the other methods. Both analysis and experimental results show that this method results in lower total harmonic distortion and higher dc bus utilisation than the other two PWM methods.

Triangle Evolution-A Hybrid Heuristic for Global Optimization

Abstract This paper presents a hybrid heuristic{triangle evolution (TE) for global optimization. It is a real coded evolutionary algorithm. As in di®erential evolution (DE), TE targets each individual in current population and attempts to replace it by a new better individual. However, the way of generating new individuals is di®erent. TE generates new individuals in a Nelder- Mead way, while the simplices used in TE is 1 or 2 dimensional. The proposed algorithm is very easy to use and e±cient for global optimization problems with continuous variables. Moreover, it requires only one (explicit) control parameter. Numerical results show that the new algorithm is comparable with DE for low dimensional problems but it outperforms DE for high dimensional problems.

Report on third FIDAWOG Workshop held at the Triangle Hotel, Jinja, 29 March to 1 April 1999: summary of proceedings

The FIDAWOG workshop held from 29 March to 1 April 1999 in Jinja was the third major stock assessment workshop attended by most of the participants during the project. It followed two workshops, each of which lasted three weeks, held in 1998.

Binding Energy and Spin-Orbit Splitting of a Hydrogenic Donor Impurity in AlGaN/GaN Triangle-Shaped Potential Quantum Well

In the framework of effective-mass envelope function theory, including the effect of Rashba spin-orbit coupling, the binding energy E-b and spin-orbit split energy Gamma of the ground state of a hydrogenic donor impurity in AlGaN/GaN triangle-shaped potential heterointerface are calculated. We find that with the electric field of the heterojunction increasing, (1) the effective width of quantum well (W) over bar decreases and (2) the binding energy increases monotonously, and in the mean time, (3) the spin-orbit split energy Gamma decreases drastically. (4) The maximum of Gamma is 1.22 meV when the electric field of heterointerface is 1 MV/cm.

Synthesis of GaN nanotip triangle pyramids on 3C-SiC epilayer/Si substrates via an in situ In-doping technique

GaN nanotip triangle pyramids were synthesized on 3C-SiC epilayer via an isoelectronic In-doping technique. The synthesis was carried out in a specially designed two-hot-boat chemical vapor deposition system. In (99.999%) and molten Ga (99.99%) with a mass ratio of about 1:4 were used as the source, and pieces of Si (111) wafer covered with 400-500 nm 3C-SiC epilayer were used as the substrates. The products were analyzed by x-ray diffraction, field emission scanning electron microscopy, high-resolution transmission electron microscopy, selected area electron diffraction, Raman spectroscopy, and photoluminescence measurements. Our results show that the as-synthesized GaN pyramids are perfect single crystal with wurtzite structure, which may have potential applications in electronic/photonic devices.

Symmetry analysis and numerical simulation of mode characteristics for equilateral-polygonal optical microresonators

Mode characteristics for two-dimensional equilateral-polygonal microresonators are investigated based on symmetry analysis and finite-difference time-domain numerical simulation. The symmetries of the resonators can be described by the point group C-Nv, accordingly, the confined modes in these resonators can be classified into irreducible representations of the point group C-Nv. Compared with circular resonators, the modes in equilateral-polygonal resonators have different characteristics due to the break of symmetries, such as the split of double-degenerate modes, high field intensity in the center region, and anomalous traveling-wave modes, which should be considered in the designs of the polygonal resonator microlasers or optical add-drop filters.

Analysis of output coupling efficiencies for directional emission triangle and square microlasers

Output coupling efficiencies are analyzed for triangular and square microlasers connected with an output waveguide by FDTD simulation. The results show that square resonator with an output waveguide connected to the midpoint of one side can have high output coupling efficiency and a good mode selection.

InGaAsP/InP Bistability Triangle Microlasers

Submitted by 阎军 (yanj@red.semi.ac.cn) on 2010-06-04T08:12:07Z No. of bitstreams: 1 InGaAsP-InP Bistability Triangle Microlasers.pdf: 305729 bytes, checksum: 9bfb7f71e2d39dc99bcee91b9a48de3c (MD5)

Solving MIN UR problem by triangle evolution algorithm with archiving and niche techniques

In this paper, as an extension of minimum unsatisfied linear relations problem (MIN ULR), the minimum unsatisfied relations (MIN UR) problem is investigated. A triangle evolution algorithm with archiving and niche techniques is proposed for MIN UR problem. Different with algorithms in literature, it solves MIN problem directly, rather than transforming it into many sub-problems. The proposed algorithm is also applicable for the special case of MIN UR, in which it involves some mandatory relations. Numerical results show that the algorithm is effective for MIN UR problem and it outperforms Sadegh's algorithm in sense of the resulted minimum inconsistency number, even though the test problems are linear.