Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

A geometric approach to stationary defect solutions in one space dimension

In this manuscript, we consider the impact of a small jump-type spatial heterogeneity on the existence of stationary localized patterns in a system of partial dierential equations in one spatial dimension...

Image Heritage - The Temporal Dimension in Consumers' Corporate Image Constructions

Images and brands have been topics of great interest in both academia and practice for a long time. The company’s image, which in this study is considered equivalent to the actual corporate brand, has become a strategic issue and one of the company’s most valuable assets. In contrast to mainstream corporate branding research focusing on consumerimages as steered and managed by the company, in the present study a genuine consumer-focus is taken. The question is asked: how do consumers perceive the company, and especially, how are their experiences of the company over time reflected in the corporate image? The findings indicate that consumers’ corporate images can be seen as being constructed through dynamic relational processes based on a multifaceted network of earlier images from multiple sources over time. The essential finding is that corporate images have a heritage. In the thesis, the concept of image heritage is introduced, which stands for the consumer’s earlier company-related experiences from multiple sources over time. In other words, consumers construct their images of the company based on earlier recalled images, perhaps dating back many years in time. Therefore, corporate images have roots - an image heritage – on which the images are constructed in the present. For companies, image heritage is a key for understanding consumers, and thereby also a key for consumer-focused branding strategies and activities. As image heritage is the consumer’s interpretation base and context for image constructions here and now, branding strategies and activities that meet this consumer-reality has a potential to become more effective. This thesis is positioned in the tradition of The Nordic School of Marketing Thought and introduces a relational dynamic perspective into branding through consumers’ image heritage. Anne Rindell is associated to CERS, the Center for Relationship Marketing and Service Management at the Swedish School of Economics and Business Administration.

Time Dimension in Consumers’ Image Construction Processes: Introducing Image Heritage and Image-in-use

This paper focuses on the time dimension in consumers’ image construction processes. Two new concepts are introduced to cover past consumer experiences about the company – image heritage, and the present image construction process - image-in-use. Image heritage and image-in-use captures the dynamic, relational, social, and contextual features of corporate image construction processes. Qualitative data from a retailing context were collected and analysed following a grounded theory approach. The study demonstrates that consumers’ corporate images have long roots in past experiences. Understanding consumers’ image heritage provides opportunities for understanding how consumers might interpret management initiatives and branding activities in the present.

Media Education in the Finnish School System : A Conceptual Analysis of the Subject Didactic Dimension of Media Education

The aim of the doctoral dissertation was to further our theoretical and empirical understanding of media education as practised in the context of Finnish basic education. The current era of intensive use of the Internet is recognised too. The doctoral dissertation presents the subject didactic dimension of media education as one of the main results of the conceptual analysis. The theoretical foundation is based on the idea of dividing the concept of media education into media and education (Vesterinen et al., 2006). As two ends of the dimension, these two can be understood didactically as content and pedagogy respectively. In the middle, subject didactics is considered to have one form closer to content matter (Subject Didactics I learning about media) and another closer to general pedagogical questions (Subject Didactics II learning with/through media). The empirical case studies of the dissertation are reported with foci on media literacy in the era of Web 2.0 (Kynäslahti et al., 2008), teacher reasoning in media educational situations (Vesterinen, Kynäslahti - Tella, 2010) and the research methodological implications of the use of information and communication technologies in the school (Vesterinen, Toom - Patrikainen, 2010). As a conclusion, Media-Based Media Education and Cross-Curricular Media Education are presented as two subject didactic modes of media education in the school context. Episodic Media Education is discussed as the third mode of media education where less organised teaching, studying and learning related to media takes place, and situations (i.e. episodes, if you like) without proper planning or thorough reflection are in focus. Based on the theoretical and empirical understanding gained in this dissertation, it is proposed that instead of occupying a corner of its own in the school curriculum, media education should lead the wider change in Finnish schools.

Nonadiabatic charge pumping by oscillating potentials in one dimension: Results for infinite system and finite ring

We study charge pumping when a combination of static potentials and potentials oscillating with a time period T is applied in a one-dimensional system of noninteracting electrons. We consider both an infinite system using the Dirac equation in the continuum approximation and a periodic ring with a finite number of sites using the tight-binding model. The infinite system is taken to be coupled to reservoirs on the two sides which are at the same chemical potential and temperature. We consider a model in which oscillating potentials help the electrons to access a transmission resonance produced by the static potentials and show that nonadiabatic pumping violates the simple sin phi rule which is obeyed by adiabatic two-site pumping. For the ring, we do not introduce any reservoirs, and we present a method for calculating the current averaged over an infinite time using the time evolution operator U(T) assuming a purely Hamiltonian evolution. We analytically show that the averaged current is zero if the Hamiltonian is real and time-reversal invariant. Numerical studies indicate another interesting result, namely, that the integrated current is zero for any time dependence of the potential if it is applied to only one site. Finally we study the effects of pumping at two sites on a ring at resonant and nonresonant frequencies, and show that the pumped current has different dependences on the pumping amplitude in the two cases.

Governmental rationalities and the local dimension of European politics. A study of the Interreg IV programme "Alpenrhein-Bodensee-Hochrhein"

The thesis aims at investigating the local dimension of the EU cohesion policy through the utilization of an alternative approach, which aims at the analysis of discourse and structures of power. The concrete case under analysis is the Interreg IV programme “Alpenrhein-Bodensee-Hochrhein”, which is conducted in the border region between Germany, Switzerland, Austria and the principality of Liechtenstein. The main research question is stated as such: What governmental rationalities can be found at work in the field of EU cross-border cooperation programmes? How is directive action and cooperation envisioned? How coherent are the different rationalities, which are found at work? The theoretical framework is based on a Foucaultian understanding of power and discourse and utilizes the notion of governmentalities as a way to de-stabilize the understanding of directive action and in order to highlight the dispersed and heterogeneous nature of governmental activity. The approach is situated within the general field of research on the European Union connected to basic conceptualisations such as the nature of power, the role of discourse and modes of subjectification. An approach termed “analytics of government”, based on the work of researchers like Mitchell Dean is introduced as the basic framework for the analysis. Four dimensions (visiblities, subjectivities, techniques/practices, problematisations) are presented as a set of tools with which governmental regimes of practices can be analysed. The empirical part of the thesis starts out with a discussion of the general framework of the European Union's cohesion policy and places the Interreg IV Alpenrhein-Bodensee-Hochrhein programme in this general context. The main analysis is based on eleven interviews which were conducted with different individuals, participating in the programme on different levels. The selection of interview partners aimed at maximising heterogeneity through including individuals from all parts of the programme region, obtaining different functions within the programme. The analysis reveals interesting aspects pertaining to the implementation and routine aspects of work within initiatives conducted under the heading of the EU cohesion policy. The central aspects of an Interreg IV Alpenrhein-Bodensee-Hochrhein – governmentality are sketched out. This includes a positive perception of the work atmosphere, administrative/professional characterisation of the selves and a de-politicization of the programme. Characteristic is the experience of tensions by interview partners and the use of discoursive strategies to resolve them. Negative perceptions play an important role for the specific governmental rationality. The thesis contributes to a better understanding of the local dimension of the European Union cohesion policy and questions established ways of thinking about governmental activity. It provides an insight into the working of power mechanisms in the constitution of fields of discourse and points out matters of practical importance as well as subsequent research questions.

The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Spin-1 Kitaev model in one dimension

We study a one-dimensional version of the Kitaev model on a ring of size N, in which there is a spin S > 1/2 on each site and the Hamiltonian is J Sigma(nSnSn+1y)-S-x. The cases where S is integer and half-odd integer are qualitatively different. We show that there is a Z(2)-valued conserved quantity W-n for each bond (n, n + 1) of the system. For integer S, the Hilbert space can be decomposed into 2N sectors, of unequal sizes. The number of states in most of the sectors grows as d(N), where d depends on the sector. The largest sector contains the ground state, and for this sector, for S=1, d=(root 5+1)/2. We carry out exact diagonalization for small systems. The extrapolation of our results to large N indicates that the energy gap remains finite in this limit. In the ground-state sector, the system can be mapped to a spin-1/2 model. We develop variational wave functions to study the lowest energy states in the ground state and other sectors. The first excited state of the system is the lowest energy state of a different sector and we estimate its excitation energy. We consider a more general Hamiltonian, adding a term lambda Sigma W-n(n), and show that this has gapless excitations in the range lambda(c)(1)<=lambda <=lambda(c)(2). We use the variational wave functions to study how the ground-state energy and the defect density vary near the two critical points lambda(c)(1) and lambda(c)(2).

Signal characterization using fractal dimension

Fractal Dimensions (FD) are one of the popular measures used for characterizing signals. They have been used as complexity measures of signals in various fields including speech and biomedical applications. However, proper interpretation of such analyses has not been thoroughly addressed. In this paper, we study the effect of various signal properties on FD and interpret results in terms of classical signal processing concepts such as amplitude, frequency, number of harmonics, noise power and signal bandwidth. We have used Higuchi's method for estimating FDs. This study may help in gaining a better understanding of the FD complexity measure itself, and for interpreting changing structural complexity of signals in terms of FD. Our results indicate that FD is a useful measure in quantifying structural changes in signal properties.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

Use of running fractal dimension for the analysis of changing patterns in electroencephalograms

Running fractal dimensions were measured on four channels of an electroencephalogram (EEG) recorded from a normal volunteer. The changes in the background activity due to eye closure were clearly differentiated by the fractal method. The compressed spectral array (CSA) and the running fractal dimensions of the EEG showed corresponding changes with respect to change in the background activity. The fractal method was also successful in detecting low amplitude spikes and the changes in the patterns in the EEG. The effects of different window lengths and shifts on the running fractal dimension have also been studied. The utility of fractal method for EEG data compression is highlighted.

Computing Fractal Dimension of Signals using Multiresolution Box-counting Method

In this paper, we have developed a method to compute fractal dimension (FD) of discrete time signals, in the time domain, by modifying the box-counting method. The size of the box is dependent on the sampling frequency of the signal. The number of boxes required to completely cover the signal are obtained at multiple time resolutions. The time resolutions are made coarse by decimating the signal. The loglog plot of total number of boxes required to cover the curve versus size of the box used appears to be a straight line, whose slope is taken as an estimate of FD of the signal. The results are provided to demonstrate the performance of the proposed method using parametric fractal signals. The estimation accuracy of the method is compared with that of Katz, Sevcik, and Higuchi methods. In ddition, some properties of the FD are discussed.