Algebraic characterization of rainbow connectivity

The use of algebraic techniques to solve combinatorial problems is studied in this paper. We formulate the rainbow connectivity problem as a system of polynomial equations. We first consider the case of two colors for which the problem is known to be hard and we then extend the approach to the general case. We also present a formulation of the rainbow connectivity problem as an ideal membership problem.

Asymptotics of Harish-Chandra expansions, bounded hypergeometric functions associated with root systems, and applications

A series expansion for Heckman-Opdam hypergeometric functions phi(lambda) is obtained for all lambda is an element of alpha(C)*. As a consequence, estimates for phi(lambda) away from the walls of a Weyl chamber are established. We also characterize the bounded hypergeometric functions and thus prove an analogue of the celebrated theorem of Helgason and Johnson on the bounded spherical functions on a Riemannian symmetric space of the noncompact type. The L-P-theory for the hypergeometric Fourier transform is developed for 0 < p < 2. In particular, an inversion formula is proved when 1 <= p < 2. (C) 2013 Elsevier Inc. All rights reserved.

Asymptotic expansions for wavenumbers in orthotropic fluid-filled circular cylindrical shells for intermediate fluid loading

Coupled wavenumbers in infinite fluid-filled isotropic and orthotropic cylindrical shells are considered. Using the Donnell-Mushtari (DM) theory for thin shells, compact and elegant asymptotic expansions for the wavenumbers are found at an intermediate fluid loading for both the coupled rigid-duct modes (''fluid-originated'') and the coupled structural wavenumbers (''structure-originated modes'') over the entire frequency range where DM theory is valid. The coupled rigid-duct expansions are found to be valid for O(1) orthotropy and for all circumferential orders, whereas the coupled structural wavenumber expansions are valid for small orthotropy and for low circumferential orders. These two above results are then used to derive the expansions for a set of multiple complex roots that display a locking behavior at this intermediate fluid-loading. The expansions are matched with the numerical solutions of the coupled dispersion relation and the match is found to be good over most of the frequency range. (C) 2014 Acoustical Society of America.

Wave propagation in a 2D nonlinear structural acoustic waveguide using asymptotic expansions of wavenumbers

Nonlinear acoustic wave propagation in an infinite rectangular waveguide is investigated. The upper boundary of this waveguide is a nonlinear elastic plate, whereas the lower boundary is rigid. The fluid is assumed to be inviscid with zero mean flow. The focus is restricted to non-planar modes having finite amplitudes. The approximate solution to the acoustic velocity potential of an amplitude modulated pulse is found using the method of multiple scales (MMS) involving both space and time. The calculations are presented up to the third order of the small parameter. It is found that at some frequencies the amplitude modulation is governed by the Nonlinear Schrodinger equation (NLSE). The first objective here is to study the nonlinear term in the NLSE. The sign of the nonlinear term in the NLSE plays a role in determining the stability of the amplitude modulation. Secondly, at other frequencies, the primary pulse interacts with its higher harmonics, as do two or more primary pulses with their resultant higher harmonics. This happens when the phase speeds of the waves match and the objective is to identify the frequencies of such interactions. For both the objectives, asymptotic coupled wavenumber expansions for the linear dispersion relation are required for an intermediate fluid loading. The novelty of this work lies in obtaining the asymptotic expansions and using them for predicting the sign change of the nonlinear term at various frequencies. It is found that when the coupled wavenumbers approach the uncoupled pressure-release wavenumbers, the amplitude modulation is stable. On the other hand, near the rigid-duct wavenumbers, the amplitude modulation is unstable. Also, as a further contribution, these wavenumber expansions are used to identify the frequencies of the higher harmonic interactions. And lastly, the solution for the amplitude modulation derived through the MMS is validated using these asymptotic expansions. (C) 2015 Elsevier Ltd. All rights reserved.

epsilon-expansions near three dimensions from conformal field theory

We formally extend the CFT techniques introduced in arXiv: 1505.00963, to phi(2d0/d0-2) theory in d = d(0) dimensions and use it to compute anomalous dimensions near d(0) = 3, 4 in a unified manner. We also do a similar analysis of the O(N) model in three dimensions by developing a recursive combinatorial approach for OPE contractions. Our results match precisely with low loop perturbative computations. Finally, using 3-point correlators in the CFT, we comment on why the phi(3) theory in d(0) = 6 is qualitatively different.

An Algebraic Preservation Theorem for Aleph-Zero Categorical Quantified Constraint Satisfaction

23 p. -- An extended abstract of this work appears in the proceedings of the 2012 ACM/IEEE Symposium on Logic in Computer Science

Valuing Expansions of the Electricity Transmission Network under Uncertainty: The Binodal Case

Transmission investments are currently needed to meet an increasing electricity demand, to address security of supply concerns, and to reach carbon-emissions targets. A key issue when assessing the benefits from an expanded grid concerns the valuation of the uncertain cash flows that result from the expansion. We propose a valuation model that accommodates both physical and economic uncertainties following the Real Options approach. It combines optimization techniques with Monte Carlo simulation. We illustrate the use of our model in a simplified, two-node grid and assess the decision whether to invest or not in a particular upgrade. The generation mix includes coal-and natural gas-fired stations that operate under carbon constraints. The underlying parameters are estimated from observed market data.

Diagonal forms, linear algebraic methods and Ramsey-type problems

This thesis focuses mainly on linear algebraic aspects of combinatorics. Let N_t(H) be an incidence matrix with edges versus all subhypergraphs of a complete hypergraph that are isomorphic to H. Richard M. Wilson and the author find the general formula for the Smith normal form or diagonal form of N_t(H) for all simple graphs H and for a very general class of t-uniform hypergraphs H.

As a continuation, the author determines the formula for diagonal forms of integer matrices obtained from other combinatorial structures, including incidence matrices for subgraphs of a complete bipartite graph and inclusion matrices for multisets.

One major application of diagonal forms is in zero-sum Ramsey theory. For instance, Caro's results in zero-sum Ramsey numbers for graphs and Caro and Yuster's results in zero-sum bipartite Ramsey numbers can be reproduced. These results are further generalized to t-uniform hypergraphs. Other applications include signed bipartite graph designs.

Research results on some other problems are also included in this thesis, such as a Ramsey-type problem on equipartitions, Hartman's conjecture on large sets of designs and a matroid theory problem proposed by Welsh.

Algebraic Techniques in Coding Theory: Entropy Vectors, Frames, and Constrained Coding

The study of codes, classically motivated by the need to communicate information reliably in the presence of error, has found new life in fields as diverse as network communication, distributed storage of data, and even has connections to the design of linear measurements used in compressive sensing. But in all contexts, a code typically involves exploiting the algebraic or geometric structure underlying an application. In this thesis, we examine several problems in coding theory, and try to gain some insight into the algebraic structure behind them.

The first is the study of the entropy region - the space of all possible vectors of joint entropies which can arise from a set of discrete random variables. Understanding this region is essentially the key to optimizing network codes for a given network. To this end, we employ a group-theoretic method of constructing random variables producing so-called "group-characterizable" entropy vectors, which are capable of approximating any point in the entropy region. We show how small groups can be used to produce entropy vectors which violate the Ingleton inequality, a fundamental bound on entropy vectors arising from the random variables involved in linear network codes. We discuss the suitability of these groups to design codes for networks which could potentially outperform linear coding.

The second topic we discuss is the design of frames with low coherence, closely related to finding spherical codes in which the codewords are unit vectors spaced out around the unit sphere so as to minimize the magnitudes of their mutual inner products. We show how to build frames by selecting a cleverly chosen set of representations of a finite group to produce a "group code" as described by Slepian decades ago. We go on to reinterpret our method as selecting a subset of rows of a group Fourier matrix, allowing us to study and bound our frames' coherences using character theory. We discuss the usefulness of our frames in sparse signal recovery using linear measurements.

The final problem we investigate is that of coding with constraints, most recently motivated by the demand for ways to encode large amounts of data using error-correcting codes so that any small loss can be recovered from a small set of surviving data. Most often, this involves using a systematic linear error-correcting code in which each parity symbol is constrained to be a function of some subset of the message symbols. We derive bounds on the minimum distance of such a code based on its constraints, and characterize when these bounds can be achieved using subcodes of Reed-Solomon codes.