Boxicity of Leaf Powers

The boxicity of a graph G, denoted as boxi(G), is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are used in the construction of phylogenetic trees in evolutionary biology and have been studied in many recent papers. We show that for a k-leaf power G, boxi(G) a parts per thousand currency sign k-1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k-1. This result implies that there exist strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.

Bipartite Powers of k-chordal Graphs

Let k be an integer and k >= 3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if G m is chordal then so is G(m+2). Brandst `` adt et al. in Andreas Brandsadt, Van Bang Le, and Thomas Szymczak. Duchet- type theorems for powers of HHD- free graphs. Discrete Mathematics, 177(1- 3): 9- 16, 1997.] showed that if G m is k - chordal, then so is G(m+2). Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. The m - th bipartite power G(m]) of a bipartite graph G is the bipartite graph obtained from G by adding edges (u; v) where d G (u; v) is odd and less than or equal to m. Note that G(m]) = G(m+1]) for each odd m. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G m], where k, m are positive integers with k >= 4

On interference alignment for symmetrically connected interference networks with line of sight channels at finite powers

In this work, interference alignment for a class of Gaussian interference networks with general message demands, having line of sight (LOS) channels, at finite powers is considered. We assume that each transmitter has one independent message to be transmitted and the propagation delays are uniformly distributed between 0 and (L - 1) (L >; 0). If receiver-j, j ∈{1,2,..., J}, requires the message of transmitter-i, i ∈ {1, 2, ..., K}, we say (i, j) belongs to a connection. A class of interference networks called the symmetrically connected interference network is defined as a network where, the number of connections required at each transmitter-i is equal to ct for all i and the number of connections required at each receiver-j is equal to cr for all j, for some fixed positive integers ct and cr. For such networks with a LOS channel between every transmitter and every receiver, we show that an expected sum-spectral efficiency (in bits/sec/Hz) of at least K/(e+c1-1)(ct+1) (ct/ct+1)ct log2 (1+min(i, j)∈c|hi, j|2 P/WN0) can be achieved as the number of transmitters and receivers tend to infinity, i.e., K, J →∞ where, C denotes the set of all connections, hij is the channel gain between transmitter-i and receiver-j, P is the average power constraint at each transmitter, W is the bandwidth and N0 W is the variance of Gaussian noise at each receiver. This means that, for an LOS symmetrically connected interference network, at any finite power, the total spectral efficiency can grow linearly with K as K, J →∞. This is achieved by extending the time domain interference alignment scheme proposed by Grokop et al. for the k-user Gaussian interference channel to interference networks.

Analysis of OSNR Requirements for Higher Modulation Schemes for Various Local Oscillator Powers

To meet the growing demands of data traffic in long haul communication, it is necessary to efficiently use the low-loss region(C-band) of the optical spectrum, by increasing the no. of optical channels and increasing the bit rate on each channel But narrow pulses occupy higher spectral bandwidth. To circumvent this problem, higher order modulation schemes such as QPSK and QAM can be used to modulate the bits, which increases the spectral efficiency without demanding any extra spectral bandwidth. On the receiver side, to meet a satisfy, a given BER, the received optical signal requires to have minimum OSNR. In our study in this paper, we analyses for different modulation schemes, the OSNR required with and without preamplifier. The theoretical limit of OSNR requirement for a modulation scheme is compared for a given link length by varying the local oscillator (LO) power. Our analysis shows that as we increase the local oscillator (LO) power, the OSNR requirement decreases for a given BER. Also a combination of preamplifier and local oscillator (LO) gives the OSNR closest to theoretical limit.

Lower Bounds for Sums of Powers of Low Degree Univariates

We consider the problem of representing a univariate polynomial f(x) as a sum of powers of low degree polynomials. We prove a lower bound of Omega(root d/t) for writing an explicit univariate degree-d polynomial f(x) as a sum of powers of degree-t polynomials.