Katie M Lavigne

Lucile A Rapin

Paul D Metzak

Jennifer C Whitman

Kwanghee Jung

Marion Dohen

Hélène Loevenbruck

Ph.D Todd S Woodward
email: todd.woodward@ubc.ca.

Hallucinations in schizophrenia 1 Running head: HALLUCINATIONS IN SCHIZOPHRENIA Left-dominant temporal-frontal hypercoupling in schizophrenia patients with hallucinations during speech perception

Keywords: SCHIZOPHRENIA, INNER SPEECH, SPEECH PERCEPTION, FUNCTIONAL MAGNETIC RESONANCE IMAGING, FUNCTIONAL CONNECTIVITY

Background: Task-based functional neuroimaging studies of schizophrenia have not yet replicated the increased coordinated hyperactivity in speech-related brain regions that is reported with symptom-capture and resting-state studies of hallucinations. This may be due to suboptimal selection of cognitive tasks. Methods: In the current study we used a task that allowed experimental manipulation of control over verbal material, and compared brain activity between 23 schizophrenia patients (10 hallucinators, 13 non-hallucinators), 22 psychiatric (bipolar) and 27 healthy controls. Two conditions were presented, one involving inner verbal thought (in which control over verbal material was required) and another involving speech perception (in which control verbal material was not required). Results: A functional connectivity analysis resulted in a left-dominant temporal-frontal network that included speech-related auditory and motor regions, and showed hypercoupling in past-week hallucinating schizophrenia patients (relative to non-hallucinating patients) during speech perception only. Conclusions: These findings replicate our previous work showing generalized speech-related functional network hypercoupling in schizophrenia during inner verbal thought and speech perception, but extend them by suggesting that hypercoupling is related to past-week hallucination severity scores during speech perception only, when control over verbal material is not required. This result opens the possibility that practicing control over inner verbal thought processes may decrease the likelihood or severity of hallucinations.

Introduction

Auditory verbal hallucinations (AVHs) are speech perceptions that occur in the absence of an external stimulus. They are a predominant feature of schizophrenia, and typically occur out of the control of the patient. Symptom capture studies investigating the hallucinatory state have reported hyperactivity in a network of speech-related brain regions while patients are actively hallucinating (e.g., primary and secondary auditory cortices, Broca's area, frontal operculum, hippocampus and parahippocampal region) relative to periods of no hallucinations [1][2][3][4][5] . Restingstate studies have also reported increased activation 6 and connectivity 7 in fronto-temporal regions in hallucinating compared to non-hallucinating schizophrenia patients and healthy controls.

Expansion of these symptom-capture and resting-state findings to task-based functional neuroimaging is important for identifying the cognitive functions underlying this increased activity/connectivity, and thereby contributing to cognitive-based theories about the genesis of AVHs. However, task-based functional neuroimaging studies often do not report whether or not activity/connectivity is increased in patients experiencing hallucinations in the past week (e.g., 8,9) . This methodology leads to difficulties in determining whether differences are specifically related to the presence of AVHs, the diagnosis of schizophrenia, or to psychiatric disorders more generally (when comparisons are made to healthy control subjects only). In addition, the seminal work in this area has focused on inclusion of a willful inner speech (or auditory imagery) condition 8,10 , but no hallucination-associated hyperactivity/hypercoupling has emerged under those conditions (although decreased activity has). It has been argued that inclusion of a willful auditory imagery condition diverges somewhat from the experience of hallucinating patients 11 , since when hallucinating patients are asked to imagine speech cast in another person's voice or Hallucinations in schizophrenia 4 one of their previously heard "voices", the patient will not experience the result as a hallucination 12 . This is because only unbidden experiences can be interpreted as hallucinations 11 .

Thus, since AVHs occur out of the control of the patient, experimental manipulation of control over verbal material should be important for understanding the functional biology of hallucinations.

Such an experimental manipulation can be achieved in straightforward fashion through comparison of willful inner speech (i.e., voluntary verbal thought generation; VTG) to speech perception (SP) conditions 13 . Inner speech, also called silent-speech, covert-speech, or verbal thought, can be defined as silent speech production in one's own mind [START_REF] Morin | Possible Links Between Self-Awareness and Inner Speech Theoretical background, underlying mechanisms, and empirical evidence[END_REF][START_REF] Perrone-Bertolotti | What is that little voice inside my head? Inner speech phenomenology, its role in cognitive performance, and its relation to self-monitoring[END_REF] . A subtype of inner speech is the deliberate generation of silent coherent verbal material, or verbal thought, which activates the so-called task-positive brain network 13,[START_REF] Fox | The human brain is intrinsically organized into dynamic, anticorrelated functional networks[END_REF] . This type of voluntary inner speech is to be contrasted with the less willful "mind wandering", in which verbal thoughts are also mentally expressed, but in a less deliberate fashion, and which activates brain regions within the tasknegative (or default mode) network [START_REF] Fox | The human brain is intrinsically organized into dynamic, anticorrelated functional networks[END_REF][START_REF] Mason | Wandering minds: the default network and stimulus-independent thought[END_REF] . In the present study we use the term voluntary verbal thought generation to describe an intended conscious production of inner speech in response to a stimulus. During VTG, participants exert some degree of control over verbal material as they are required to mentally generate definitions of common words. SP, however, does not require control over verbal material, as participants simply listen to pre-recorded definitions. A preliminary study by our group using this comparison revealed coordinated hyperactivity/hypercoupling 1 in a temporal-frontal network of speech-related auditory and motor 1 It is important to note that a clear distinction between coordinated hyperactivity and hypercoupling is not available with functional connectivity analyses. Brain regions with correlated and strong activations over time, which emerge on the same functional network (e.g., as a result of singular value decomposition or component analysis), can be thereby considered coupled, and do so because they increase and reduce activation in synchrony (i.e., in a regions for schizophrenia patients relative to healthy controls during both VTG and SP 13 ; however, it was not possible to examine differences between hallucinating and non-hallucinating schizophrenia patients due to a small sample. The goal of the present study was to extend our previous work by investigating whether this hypercoupling is associated with hallucination ratings in schizophrenia patients, and whether exertion of control over verbal material affects brain activity within this network in hallucinating patients.

In accordance with our past work, we expected that schizophrenia patients, irrespective of hallucination status, would demonstrate hypercoupling in a temporal-frontal network including auditory and motor regions. We further expected that hypercoupling in this functional network would be higher in hallucinating schizophrenia patients for the SP condition (in which there is assumed to be little control over verbal material) relative to non-hallucinating schizophrenia patients, psychiatric, and healthy controls.

Methods and Materials

Participants

Participants were 23 schizophrenia patients (10 hallucinators; H_SZ; 13 nonhallucinators; NH_SZ), 22 non-hallucinating bipolar patients (BP), and 27 healthy controls (HC), all of whom had been using English daily for at least the past 5 years and responded accurately to questions about the consent form designed to confirm their ability to read and understand English. Most were right-handed [START_REF]A classification of hand preference by association analysis[END_REF] (n=65; Left-handed = 2 HCs; Mixed = 1 HC, 1 NH_SZ, 3 BPs). Both in-and outpatients were included in the patient samples. Bipolar patients were coordinated fashion) over time. Highly coordinated and strong increases and decreases in activity lead to higher intercorrelations between regions, and can be interpreted as coordinated hyperactivity and/or hypercoupling. Therefore, we use the two terms interchangeably here.

Hallucinations in schizophrenia 6 selected as a psychiatric control group due to the similarities between people with a diagnosis of bipolar disorder and people with a diagnosis of schizophrenia with regards to cognitive, genetic and environmental susceptibility factors [START_REF] Barrett | Patterns of neurocognitive impairment in first-episode bipolar disorder and schizophrenia[END_REF] . Therefore, any aspect of task performance attributable to these factors (or other overlapping characteristics, such as the stigmatization associated with mental illness) should be present for individuals within both groups. A hearing test was carried out on all but one participant using an audiometer (AMBCO 650AB, www.ambco.com) to ensure absence of hearing impairment. All participants provided written informed consent and met magnetic resonance imaging compatibility criteria. The study was approved by both the University of British Columbia (UBC) and UBC Hospital Clinical Research Ethics Committees and participants received financial compensation of $10 CAD per hour and reimbursement of travel costs for participation. Details regarding demographic variables can be found in the Supplementary Material.

Patients' symptoms were assessed using the Signs and Symptoms of Psychotic Illness scale (SSPI [START_REF] Liddle | Signs and Symptoms of Psychotic Illness (SSPI): a rating scale[END_REF] ; see Table 1 for means and group differences). The SSPI consists of 30 items and is criterion referenced, providing specific examples of behaviour (over the past week) which correspond to severity levels for each item (e.g., Hallucinations: 0 = absent; 1 = vague descriptions of hallucinations; 2 = hallucinations which the patient accepts as arising from within his/her own mind; 3 = definite hallucinations occurring occasionally (e.g. < once/day); 4 = definite hallucinations which are frequent and/or influence observable behaviour). For the following analyses, schizophrenia patients were included in the hallucinating and nonhallucinating subgroups based on their SSPI Hallucinations score (hallucinating: 3 (n = 3) or 4 (n = 7; non-hallucinating: 0 (n = 9), 1 (n = 2) or 2 (n=2)). All hallucinating patients reported auditory hallucinations, and 6 patients reported multimodal hallucinations (tactile = 6; visual = 3;

Hallucinations in schizophrenia 7 olfactory = 1). All schizophrenia patients but one had experienced hallucinations in the past. All bipolar patients scored 0 on hallucinations, with the exception of one who was rated 2 (visual hallucinations only).

Task

The task design employed here was nearly identical to that used in our previous study 13 , with adjustments in stimulus timing, presentation, and the addition of a post-scan questionnaire to provide evidence that definitions were in fact generated. Briefly, participants were presented with a noun (object) and its corresponding image (e.g., Pillow) and instructed to either mentally generate (VTG) or to listen to (SP) a simple definition of the word (e.g., "Something you rest your head on when sleeping"). The two experimental conditions were presented in blocks consisting of 15 trials each (30 trials total for each condition across two runs), with a 60s rest break in between the two conditions. Stimuli were randomly assigned to each condition for each participant separately. The conditions were cued with the words "something you…" and "listen…" presented under the images in the VTG and SP conditions, respectively (see Figure 1; see Supplementary Material for details on stimulus presentation and timing). Participants were administered a post-scan questionnaire where they were asked, for each trial, whether they generated a definition and, if so, what that definition was. Patients were also asked whether they experienced AVHs during fMRI scanning; one schizophrenia patient reported auditory hallucinations during testing, and this occurred during both conditions. Data Analysis fMRI data analysis was carried out using constrained principal component analysis for fMRI (fMRI-CPCA; www.nitrc.org/projects/fmricpca) with orthogonal rotation [START_REF] Metzak | Constrained principal component analysis reveals functionally connected loaddependent networks involved in multiple stages of working memory[END_REF][START_REF] Metzak | Decreased efficiency of task-positive and task-negative networks during working memory in schizophrenia[END_REF][START_REF] Woodward | Functional connectivity reveals load dependent neural systems underlying encoding and maintenance in verbal working memory[END_REF][START_REF] Woodward | Epoch-specific functional networks involved in working memory[END_REF][START_REF] Takane | Constrained principal component analysis: A comprehensive theory[END_REF][START_REF] Takane | Principal component analysis with external information on both subjects and variables[END_REF] . Details on image acquisition, image preprocessing, and data analysis procedures are presented in the Supplementary Material.

Results

Inspection of the scree plot [START_REF] Cattell | The scree test for the number of factors[END_REF][START_REF] Cattell | A comprehensive trial of the scree and kg criteria for determining the number of factors[END_REF] suggested that two components should be extracted. Both Components 1 and 2 showed a significant effect of Peristimulus Time, F(8,568) = 77.63, p < .001; F(8,568) = 95.78, p < .001, respectively, and visual inspection of the predictor weights confirmed a hemodynamic response (HDR) shape. The percentages of task-related variance accounted for by each rotated component were 17.91%, and 7.97% for components 1 and 2, respectively.

Anatomical Descriptions

The brain regions associated with Component 1 are displayed in Figure 2A (top panel; red/yellow), with anatomical descriptions in Table S2 of the Supplementary Material.

Component 1 was characterized by a network of voxel clusters dominated by activations in regions involved in language production and comprehension including pars opercularis of the left inferior frontal gyrus (BA 44) and bilateral superior temporal gyri (BAs 21, 22), as well as activations within bilateral visual/fusiform regions ( BAs 17, 18, 19, 37), and supplementary motor area (BA 6). The brain regions associated with Component 2 are displayed in Figure 2A (top panel; blue/green), with anatomical descriptions in Table S3. Component 2 was characterized by a functional network involving increased activity in bilateral visual/fusiform regions (BAs 18, 19, 37) overlapping with those from Component 1, and decreased activity in regions overlapping with the default mode or task-negative network [START_REF] Fox | The human brain is intrinsically organized into dynamic, anticorrelated functional networks[END_REF][START_REF] Buckner | The Brain's Default Network[END_REF] , such as posterior cingulate cortex and precuneus (BA 23), medial prefrontal (BAs 9, 10), superior frontal (BA 8), and inferior parietal/lateral occipital cortex (BA 39, 40), as well as decreased activity in other regions such as precentral gyrus (BA 6) and superior parietal cortex (BAs 2, 5, 7).

Relation to Experimental Conditions

A 2 x 9 x 2 x 4 mixed-model ANOVA revealed a significant Condition × Peristimulus Time × Group interaction, F(24, 544) = 2.24, p < .001, η p 2 = 0.09, but no significant 4-way interaction (p > .8). This suggests that, with respect to understanding Group differences, the HDR shape (indexed by peristimulus time) and Condition must be taken into account, but Components 1 and 2 can be combined, as is displayed in Figure 2. In order to interpret this interaction, we examined group differences at each time bin for each condition separately, averaged over both components.

Observation of effect sizes in simple-simple main effects characterizing the significant Condition × Peristimulus Time × Group interaction demonstrated that, as is clear in Figure 2B, the largest effects are observable when comparing hallucinating schizophrenia patients to the other three groups in SP: (1) relative to controls at time bin 2A, and greater activation decreases in blue areas in Figure 2A.

Correlation with Hallucinations

In order to examine associations with hallucinations, correlations were computed between the estimated HDR (i.e., predictor weights) for each condition and the SSPI hallucinations item for schizophrenia patients. The estimated HDR was averaged across time bins 1, 2, and 3 for SP and time bins 3 and 4 for VTG, given that these were the time points on which hallucinating schizophrenia patients were distinguishable from controls, for each condition respectively. The SSPI Hallucinations score was significantly correlated with the estimated HDR in the SP condition, r( 21 S4 of the Supplementary Material for the full list of correlations).

Discussion

Functional neuroimaging studies have reported hyperactivity in speech-related brain networks in hallucinating schizophrenia patients during the experience of hallucinations [1][2][3][4][5] as well as at rest 6,7 . However, task-based functional neuroimaging studies have not yet demonstrated that this increased activity/connectivity is associated with hallucinations in schizophrenia. In the current event-related fMRI study, we examined task-elicited activity during conditions requiring (VTG) or not requiring (SP) control over verbal material in schizophrenia patients with and without hallucinations, bipolar patients, and healthy controls. Functional connectivity analysis revealed a left-dominant temporal-frontal network including speech-related auditory and motor regions, which showed hypercoupling in hallucinating schizophrenia patients relative to all other groups during SP. In addition, this hypercoupling was higher in both hallucinating and non-hallucinating schizophrenia patients relative to controls and bipolar patients during VTG. These findings replicate our previous work showing generalized speechrelated functional network hyperactivity in schizophrenia during inner verbal thought and speech perception 13 , but extend them by suggesting that hypercoupling is related to hallucination scores only during speech perception, when control processes are not required.

The finding of hypercoupling in hallucinating schizophrenia patients when control processes are not required fits with the observation that AVHs occur out of the control of the patient [START_REF] Hoffman | Experiential features used by patients with schizophrenia to differentiate 'voices' from ordinary verbal thought[END_REF] . The involvement of the superior temporal gyrus (STG) provides further evidence that bottom-up cognitive processes contribute to hallucinations, in accordance with a number of Hallucinations in schizophrenia 12 neurocognitive accounts of AVHs 11,[START_REF] Hoffman | Schizophrenia Research Forum[END_REF][START_REF] Hoffman | New methods for studying hallucinated 'voices' in schizophrenia[END_REF][START_REF] David | The neuropsychological origin of auditory hallucinations[END_REF][START_REF] Allen | The hallucinating brain: A review of structural and functional neuroimaging studies of hallucinations[END_REF] . However, the results also suggest that top-down influences may play an important role, because the expectation of control over verbal material in VTG negated the hallucination-specific hypercoupling observed in SP. The nature of the interplay between top-down and bottom-up influences seems fertile ground for future research on AVHs, and have already been considered by other accounts as efference copy 11,[START_REF] Allen | The hallucinating brain: A review of structural and functional neuroimaging studies of hallucinations[END_REF] , or expectations, hypervigilance, imagination/fantasy, and memories/trauma [START_REF] Waters | Auditory hallucinations in schizophrenia and nonschizophrenia populations: A review and integrated model of cognitive mechanisms[END_REF] . Another possible topdown influence on hallucinations is the cognitive biases underlying delusions, such as hypersalience of a match between evidence (increased vividness of perceptual qualities) and a self-selected hypothesis ("I will hear voices") [START_REF] Balzan | Reasoning heuristics across the psychosis continuum: The contribution of hypersalient evidence-hypothesis matches[END_REF][START_REF] Speechley | The contribution of hypersalience to the "jumping to conclusions" bias associated with delusions in schizophrenia[END_REF][START_REF] Whitman | Bias in favour of self-selected hypotheses is associated with delusion severity in schizophrenia[END_REF] .

The hypercoupling observed in both hallucinating and non-hallucinating schizophrenia patients in VTG can be explained by the reduced cognitive efficiency account of schizophrenia as a diagnostic category [START_REF] Callicott | Complexity of prefrontal cortical dysfunction in schizophrenia: more than up or down[END_REF] . Assuming that the requirement for cognitive control in VTG requires more cognitive capacity than in SP, it is important to note that people with schizophrenia are known to demonstrate reduced efficiency in functional networks, whereby, relative to healthy controls, they must devote more cognitive resources to perform a moderately demanding task [START_REF] Metzak | Decreased efficiency of task-positive and task-negative networks during working memory in schizophrenia[END_REF][START_REF] Callicott | Complexity of prefrontal cortical dysfunction in schizophrenia: more than up or down[END_REF][START_REF] Cairo | Decreased encoding efficiency in schizophrenia[END_REF] . Therefore, increased engagement of these functional networks would be expected regardless of hallucination severity, since inefficiency is thought to be diagnosis-based and not symptom-based [START_REF] Metzak | Decreased efficiency of task-positive and task-negative networks during working memory in schizophrenia[END_REF][START_REF] Callicott | Complexity of prefrontal cortical dysfunction in schizophrenia: more than up or down[END_REF][START_REF] Cairo | Decreased encoding efficiency in schizophrenia[END_REF] .

Interestingly, the current results provide evidence that the hypercoupling for hallucinating schizophrenia patients relative to the other groups in SP was present during task-off periods;

namely, in the period between 0-5 seconds post stimulus, when the HDR should not have had sufficient time to increase in response to task demands. Although brain activity during task-off periods reflects a wide range of cognitive processes [START_REF] Stark | When zero is not zero: The problem of ambiguous baseline conditions pin fMRI[END_REF][START_REF] Miezin | Characterizing the hemodynamic response: effects of presentation rate, sampling procedure, and the possibility of ordering brain activity based on relative timing[END_REF] , this hypercoupling in hallucinating schizophrenia patients in the current study was observed in the same network involved in the task-on period, suggesting that this particular task-off activity engages the same networks as SP.

Note that an HDR shape with a sharp peak would not be expected during task-off periods (as it is for task-on periods) because the cognitive processes occurring during task-off periods do not have consistent timing. This suggests that for hallucinating patients during the off-task period of the SP block (1) a functional network that includes speech-related auditory and motor regions is more active, which has been suggested elsewhere for auditory cortex [START_REF] Northoff | How can the brain's resting state activity generate hallucinations? A 'resting state hypothesis' of auditory verbal hallucinations[END_REF] , and (2) the deactivation of the default-mode network normally associated with task-related activity is already pronounced, as has been suggested for schizophrenia patients [START_REF] Garrity | Aberrant "Default Mode" Functional Connectivity in Schizophrenia[END_REF] . Importantly, this effect was not present during VTG, which differed from the SP condition in that it involved the added expectation of exerting control over verbal material. This suggests that, for schizophrenia patients with hallucinations, the expectation of exerting cognitive control attenuated the abnormalities found during task-off periods; namely, it attenuated both exaggerated activation of temporal-frontal regions, and exaggerated reduction of default-mode regions. From this we can speculate that expecting to control inner verbal thought processes may reduce hypercoupling in the speech-related functional network, and reduce the likelihood of hallucinations. The suggestion that control processes and hallucinations are incompatible has already been proposed by the breakaway speech/unbidden thoughts account of hallucinations 11,[START_REF] Hoffman | Schizophrenia Research Forum[END_REF][START_REF] Hoffman | New methods for studying hallucinated 'voices' in schizophrenia[END_REF][START_REF] David | The neuropsychological origin of auditory hallucinations[END_REF] .

It has been previously stated that AVHs may be attributable to fronto-temporal disconnection 10,[START_REF] Frith | The cognitive neuropsychology of schizophrenia[END_REF][START_REF] Mcguire | The neural correlates of inner speech and auditory verbal imagery in schizophrenia: relationship to auditory verbal hallucinations[END_REF] , possibly resulting from a breakaway speech perception network [START_REF] Hoffman | Schizophrenia Research Forum[END_REF][START_REF] Hoffman | New methods for studying hallucinated 'voices' in schizophrenia[END_REF][START_REF] David | The neuropsychological origin of auditory hallucinations[END_REF] .

However, with the current set of results we provide evidence for hypercoupling in a leftdominant temporal-frontal network associated with AVHs during speech perception. The participants with the highest estimated HDR peaks (suggesting hypercoupling) were the Hallucinations in schizophrenia 14 schizophrenia patients experiencing the most severe hallucinations in the previous week (in SP).

Additional evidence for coordinated hyperactivity/hypercoupling (as well as other connectivity concepts) may be achieved by combining structural measures of connectivity with functional measures, such as measures of white matter integrity (e.g., diffusion tensor imaging; DTI). For example, DTI studies have supported the notion of increased connectivity between language and auditory processing regions in patients with AVHs, but have also provide evidence for frontotemporal disconnection [START_REF] Shergill | A diffusion tensor imaging study of fasciculi in schizophrenia[END_REF][48][49] .

Limitations of this study include an absence of direct quantification of trial-by-trial task engagement. However, given that all group differences involved increased activity for schizophrenia patients relative to controls, it is unlikely that the results were influenced by patients being disengaged from the task. It was also not possible to discount the influence of cognitive processes occurring between the offset of the auditory stimulus and the onset of the ITI in SP, which lasted just over 2 seconds; however, given the similarities between the shape of the estimated HDRs in SP and VTG, it is unlikely that cognitive processes during this period affected the current results. In addition, an alternative interpretation of the absence of an association with hallucinations during VTG is a noisier signal in that condition, since the thought processes in VTG have more variable timing than the perceptual processes in SP. Another limitation is that, to the extent the cognitive processes studied here are affected by antipsychotic medication, the current results could be confounded by medication use, as dosage was not available for all participants. Finally, it was not possible in the current study to determine whether the hypercoupling observed during SP in hallucinating schizophrenia patients is specific to speech, or is a more general effect. If hyperactivity in this network were specific to AVHs, one

Hallucinations in schizophrenia 15

would not expect to see similar hyperactivity during a non-speech auditory task. Further research will be needed in order to investigate these alternative possibilities.

Conclusion

The goal of the present study was to determine whether hallucination-associated taskbased hypercoupling in a speech-related auditory-motor network depends on the engagement of control processes. Schizophrenia patients demonstrated hypercoupling in a left-dominant temporal-frontal network involving auditory-motor brain regions under conditions both requiring (VTG) and not requiring (SP) control over verbal material. Importantly, this effect was associated with hallucination ratings only for speech perception, when control processes were not engaged, suggesting that the expectation of exerting cognitive control led to a correction of hypercoupling in recently hallucinating patients. This result opens the possibility that practicing control over inner verbal thought processes may decrease the likelihood or severity of hallucinations, a finding that may be an important consideration for cognitive behavioural therapy (CBT) for voice-hearing 50-52 .

Lee

Figure 1. Timeline of the experimental procedure. Participants were instructed to either mentally generate (VTG) or to listen to (SP) a simple definition of a word (e.g., "Something you rest your head on when sleeping" for the word "Pillow"). The conditions were cued with the words "something you…" or "listen…" presented under the images for the VTG and SP conditions, respectively. The VTG condition is depicted here. S2 andS3).

Left-dominant temporal-frontal hypercoupling in schizophrenia patients with hallucinations during speech perception

Supplementary Material

Participants

A one-way ANOVA testing for group differences on common demographic variables (see Table S1 for group means) revealed a significant difference in age, F(3,71) = 5.35, p <.005.

Least significant difference (LSD) post-hoc comparisons confirmed that the bipolar group was significantly older than controls and hallucinating schizophrenia patients, with no other group differences reaching significance. IQ was evaluated using the Kaufman Brief Intelligence Test version 2 (K-BIT-2) 1 and the Wechsler Test of Adult Reading (WTAR) 2 . All but three schizophrenia patients (1 never medicated, 1 previously medicated, and 1 missing) were on antipsychotic medication at the time of testing. All but four bipolar patients were taking antidepressants (3 never used, 1 past use) and 11 were taking antipsychotic medication. Although a significantly smaller number of bipolar patients were on antipsychotic medication relative to hallucinating, χ 2 (1, N = 32) = 5.66, p < .05, and non-hallucinating, χ 2 (1, N = 32) = 10.12, p < .05 schizophrenia patients, the two schizophrenia groups did not differ from each other (p > .05).

Although dosage was not available for all participants taking anti-psychotic medication, chlorpromazine equivalent dosage was computed for 7 hallucinating and 5 non-hallucinating schizophrenia patients. Means comparisons indicated no significant differences on dosage between these two groups (p > .05). DSM-IV-TR 3 diagnoses on referral were confirmed using the Mini-International Neuropsychiatric Interview (MINI) 4 . The exclusion criteria for all groups included history of neurological disorder, traumatic brain injury with loss of consciousness for more than 5 minutes and any cognitive sequalae resulting from loss of consciousness, or

Hallucinations in schizophrenia 31

diagnosis of substance abuse/dependence. History of psychiatric disorder (self or immediate family) warranted exclusion for the control group.

Stimuli

Three 30-word lists of nouns were created using the MRC psycholinguistic database 5 . In order to facilitate generation of definitions, only nouns with values greater than 500 on familiarity, concreteness, and imageability criteria ratings were chosen (maximum value = 700).

The three word lists (i.e., list A, B and C) were matched by mean values on these parameters. All nouns were objects of neutral affective content within the categories of food, houseware, furniture, clothing, and transportation devices. Audio stimuli were recorded by a female native speaker of English in a quiet room and lasted on average 2.22 seconds (SD = 0.62). Two out of the three word lists were randomly assigned to the two conditions for each participant separately, leading to six potential combinations of word sets (i.e., AB, BA, AC, CA, CB, and CB), which were counterbalanced across participants.

Prior to fMRI scanning, participants were familiarized with the experimental procedure in a computerized practice run, using 10 words (5 VTG, 5 SP) different from those presented in the scanner. In order to facilitate generation of definitions while in the scanner, participants also practiced audibly generating definitions for the 30 words in the VTG condition, with no time limit imposed. No specific training was carried out for the SP material to ensure that familiarity with the material would not increase the likelihood of self-generating definitions during this condition. During fMRI scanning, the two experimental conditions were displayed using Presentation Software 12.1 (http://www.neurobs.com). For each condition, each word, its associated illustration, and the condition cue, were displayed for five seconds. Words were written in white in a 48 point Times New Roman font and presented on a black background. The illustration was placed under the word and the display was centered on screen (see Figure 1 in the main text). In the SP condition, the audio file containing the definition was presented 700 ms after the onset of the word and illustration. The provided definitions always began with the words "Something you" and participants were instructed that mentally generated definitions should also start with "Something you", in order to ensure that at least some words were mentally generated on every trial, and to minimize any interpretational confounds between conditions.

In order to prevent participants from internally reviewing the most recently generated or heard definition, a display of generic circles moving in an orbiting motion was presented during the inter-trial interval (ITI). The distribution of the duration of the ITI was exponential, optimizing the deconvolution of the blood oxygenation level dependent (BOLD) signal (mean=4.46s, range=2s, 4, 6, 8, 16, 20s) 6 . The order of presentation of the ITIs, conditions, and words within each block were randomized.

Image Acquisition and Processing

Imaging was performed at the University of British Columbia MRI Research Centre on a Philips Achieva 3.0 Tesla (T) MRI scanner with quasar dual gradients (maximum gradient amplitude, 80mT/m; maximum slow rate, 200 mT/m/s). The participant's head was firmly secured using a customized head holder. Functional image volumes were collected using a T2*weighted gradient-echo spin pulse sequence with 36 axial slices; thickness/gap, 3/1 mm; matrix, 80×80; repetition time (TR), 2500 ms; echo time (TE), 30 ms; flip angle (FA), 90°, field of view (FOV), 240×240 mm, effectively covering the whole brain. 352 images were acquired over two runs of approximately 7 min and 30 s each.

Hallucinations in schizophrenia 33

Functional images were pre-processed using Statistical Parametric Mapping 8 (SPM8;

Wellcome Trust Centre for Neuroimaging, UK). For each participant, each functional run was realigned, co-registered to their structural (T1) image, and subsequently normalized to the Montreal Neurological Institute (MNI) T1 brain template. All images were spatially smoothed with an 8x8x8 mm full width at half maximum Gaussian filter.

Connectivity Analysis

fMRI data analysis was carried out using constrained principal component analysis for fMRI (fMRI-CPCA) with orthogonal rotation [7][8][9][10][11] . The theory and proofs for CPCA are detailed in previously published work 12,13 . The fMRI-CPCA application is available on-line, free of charge (www.nitrc.org/projects/fmricpca). fMRI-CPCA computes components representing functional brain networks on BOLD signal for which variance has been constrained (using multivariate multiple regression) to be predictable from task timing. This application of CPCA involved preparation of two matrices. The first matrix, Z, contained the BOLD time series of each voxel, with one column per voxel and one row per whole brain scan. Each column contained the realigned, co-registered, normalized and smoothed activations over all scans, for each subject separately. The second matrix, G (design matrix), contained finite impulse response (FIR) models of the expected BOLD response to the timing of stimulus presentations.

Preparation of G

The G (design) matrix consisted of a FIR basis set, which can be used to estimate the increase in BOLD signal at specific peristimulus scans relative to all other scans. The value 1 is placed in rows of G for which BOLD signal amplitude is to be estimated, and the value 0 in all other rows ("mini boxcar" functions). The time bins for which a basis function was specified in the current study were the 1 st to 9 th scans following stimulus presentation. Since the repetition time (TR) for these data was 2.5 s, this resulted in estimating BOLD signal over a 22.5 s window, with the start of the first time bin (time = 0) corresponding to encoding stimulus onset.

In this analysis we created a G matrix that would allow us to estimate subject-and-condition specific effects by inserting a separate FIR basis set for each condition and for each individual subject. The columns in this subject-and-condition based G matrix code 9 peristimulus time bins, 2 conditions (VTG and SP), and 72 subjects, resulting in 1296 columns (9 × 2 × 72 = 1296).

Matrix Equations

The matrix of BOLD time series and design matrices are taken as input, with BOLD in Z being predicted from the FIR model in G. In order to achieve this, multivariate least-squares linear regression was carried out, whereby the BOLD time series (Z) was regressed onto the design matrix (G):

Z = GC + E, ( 1 )
where C = (G'G) -1 G'Z, or least squares multivariate multiple regression. This analysis yielded condition-specific regression weights in the C matrix (i.e., regression weights specific to the experimental conditions as defined by the design matrix). The condition-specific regression weights are often referred to (in conventional fMRI analyses) as beta images. GC contained variability in Z that was predictable from the design matrix G, that is to say, variability in Z that was predictable from the timing of stimulus presentations.

The next step employed singular value decomposition (SVD) to extract components representing networks of functionally interconnected voxel activations from GC. This involved singular value decomposition of the activation variability that was predictable from the design matrix (GC):

UDV' = GC ( 2 )
where U = matrix of left singular vectors; D = diagonal matrix of singular values; V = matrix of right singular vectors. Each column of VD can be overlaid on a structural brain image to allow visualization of the brain regions involved in each functional network. In the current application of CPCA, following dimension reduction, we orthogonally rotated 7 and rescaled the VD matrix prior to display, so that a rotated loading matrix is displayed. The values of the loading matrix contain the correlations between the components in U and the variables in GC. The orthonormal rotation transformation matrix is then used to transform the rescaled left singular vectors U into rotated component scores (with rows corresponding to scans).

Predictor Weights

To interpret the components with respect to the conditions represented in G, we produced predictor weights in matrix P. These are the weights that would be applied to each column of the matrix of predictor variables (G) to create U (U=GP) and can be orthogonally rotated by applying the same transformation matrix 7 as was applied to VD and U. The values in P indicate the importance of each column in the G matrix to the network(s) represented by the component(s) in VD, so are essential for relating the resultant components to the experimental conditions of interest represented in G. This approach estimates a hemodynamic response (HDR) shape for each individual separately, so fully accommodates heterogeneity in HDRs.

Data Analysis

These predictor weights, which provide estimates of the engagement of functional networks at each point in peristimulus time, can be used to statistically test the effect of peristimulus time to determine whether or not these values are reflecting a hemodynamic response (HDR) shape (and not simply varying randomly around zero). A significant effect of peristimulus time combined with a biologically plausible HDR shape provides evidence that the Hallucinations in schizophrenia 36 component is reflecting a reliable BOLD response to the stimuli [7][8][9] . These analyses were carried out as 2 × 9 × 2 × 4 mixed model ANOVAs, with the within-subjects factors of Component (2 components were extracted from the CPCA), Peristimulus Time (9 whole-brain scans after the onset of each stimulus were estimated in the finite impulse response model), Condition (SP vs.

VTG), and the between-subjects factor of Group (hallucinating schizophrenia patients, nonhallucinating schizophrenia patients, bipolar patients, and healthy controls). Any impact of group or condition would typically be reflected by a significant interaction with peristimulus time for the measure of estimated HDR (i.e., the predictor weights), although main effects are also possible. Tests of sphericity were carried out for all ANOVAs, and adjustment in degrees of freedom for violations of sphericity did not affect the results; therefore, the original degrees of freedom are reported.

Hallucinations in schizophrenia 37

Figure 2 A

 2 Figure 2 A-C. A: Dominant 10% of component loadings for Component 1 (red/yellow = positive loadings; threshold = .20, max = .37, no negative loadings passed threshold) and Component 2 (blue/green = negative loadings, negative threshold = -.14, min = -.25). Component 2 positive loadings in the occipital regions overlapped with those from Component 1 (see TablesS2 and S3). Axial slices are located at Montreal Neurological Institute Z-axis coordinates -32, -12, -1, 24, 48. B: Mean finite impulse response (FIR)-based predictor weights for speech perception (SP), averaged over components and plotted as a function of peristimulus time. C: Mean FIRbased predictor weights for voluntary verbal thought generation (VTG), averaged over components and plotted as a function of peristimulus time. Error bars are standard errors. HDR = Estimated Hemodynamic Response; L = Left; R = Right; SZ = Schizophrenia.

  Figure 2 A-C. A: Dominant 10% of component loadings for Component 1 (red/yellow = positive loadings; threshold = .20, max = .37, no negative loadings passed threshold) and Component 2 (blue/green = negative loadings, negative threshold = -.14, min = -.25). Component 2 positive loadings in the occipital regions overlapped with those from Component 1 (see TablesS2 and S3). Axial slices are located at Montreal Neurological Institute Z-axis coordinates -32, -12, -1, 24, 48. B: Mean finite impulse response (FIR)-based predictor weights for speech perception (SP), averaged over components and plotted as a function of peristimulus time. C: Mean FIRbased predictor weights for voluntary verbal thought generation (VTG), averaged over components and plotted as a function of peristimulus time. Error bars are standard errors. HDR = Estimated Hemodynamic Response; L = Left; R = Right; SZ = Schizophrenia.

Figure S2 .

 S2 Figure S2. Scatterplot of the correlation between Signs and Symptoms of Psychotic Illness (SSPI) hallucinations rating and estimated hemodynamic response (HDR) for voluntary verbal thought generation (VTG) averaged across time bins 3 to 4.

  In addition, as is clear in Figure2C, the largest effects are observable when comparing schizophrenia patient groups to healthy and psychiatric controls in VTG: hallucinating schizophrenia patients demonstrated greater intensity relative to healthy controls at time bin 3,

	F(1,68) = 4.48, p < .05, η p	2 = 0.06, and time bin 4, F(1,68) = 6.60, p < .05,η p	2 = 0.09, and non-

1, F(1,68) = 17.84, p < .001, η p 2 = 0.21, time bin 2, F(1,68) = 12.34, p < .005, η p 2 = 0.15, time bin 3, F(1,68) = 6.03, p < .05, η p 2 = 0.08, and time bin 9, F(1,68) = 4.77, p < .05, η p 2 = 0.07; (2) relative to bipolar patients at time bin 1, F(1,68) = 10.14, p < .005, η p 2 = 0.13, time bin 2, (F(1,68) = 7.02, p < .05, η p 2 = 0.09, time bin 3, F(1,68) = 4.04, p < .05, η p 2 = 0.06, time bin 7, F(1,68) = 5.04, p < .05, η p 2 = 0.07, and time bin 8, F(1,68) = 4.93, p < .05, η p 2 = 0.07; and (3) relative to non-hallucinating schizophrenia patients at time bin 1, F(1,68) = 6.54, p < .05, η p 2 = 0.09, time bin 2, F(1,68) = 4.13, p = .05, η p 2 = 0.06, time bin 7, F(1,68) = 4.63, p < .05, η p 2 = 0.06, time bin 8, F(1,68) = 5.23, p < .05, η p 2 = 0.07, and time bin 9, F(1,68) = 6.39, p < .05, η p 2 = 0.09. Non-hallucinating schizophrenia patients showed greater intensity relative to controls for time bin 6, F(1,68) = 6.53, p < .05, η p 2 = 0.09, with no other group contrasts reaching significance for SP. hallucinating schizophrenia patients demonstrated significantly greater intensity relative to controls at time bin 4, F(1, 68) = 8.37, p < .01, η p 2 = 0.11, time bin 5, F(1, 68) = 10.47, p < .005, η p 2 = 0.13, and time bin 6, F(1, 68) = 5.33, p < .05, η p 2 = 0.07, as well as relative to bipolar patients at time bin 5, F(1,68) = 3.92, p = .05, η p 2 = 0.06. All increases in intensity can be interpreted as greater activation increases in red areas in Figure

Table 1 .

 1 K, Yoshida T, Kubicki M, et al. Increased diffusivity in superior temporal gyrus in Signs and Symptoms of Psychotic Illness (SSPI) means and standard deviations (SD; in parentheses) for patient groups.

	patients with schizophrenia: a Diffusion Tensor Imaging study. Schizophrenia Research
	2009;108(1-3):33-40.
	49. Hubl D, Koenig T, Strik W, et al. Pathways that make voices: white matter changes in
	auditory hallucinations. Archives of General Psychiatry 2004;61(7):658-668.
	50. Beck AT, Rector NA. Cognitive therapy of schizophrenia: a new therapy for the new
	millennium. American Journal Of Psychotherapy 2000;54(3):291-300.

51. Chadwick P, Birchwood M. The omnipotence of voices: A cognitive approach to auditory hallucinations. The British Journal of Psychiatry 1994;164:190-201. 52. Morrison AP, Renton JC. Cognitive therapy for auditory hallucinations: A theory-based approach. Cognitive and Behavioral Practice 2001;8(2):147-160. Note. a : H_SZ > NH_SZ & BP, p < .01; b : BP < H_SZ & NH_SZ, p < .01; c : BP < H_SZ, p < .01

Table S1 .

 S1 Group means (standard deviations in parentheses) for demographic variables.

	Variable	Control	Bipolar	Schizophrenia -NonHallucinating	Schizophrenia -Hallucinating
	N	27	22	13	10
	Sex (% female)	40.70	45.50	53.80	40.00
	Age	28.89 (8.98)	40.05 (10.77)	33.23 (9.85)	31.90 (9.62)
	Education	15.57 (1.86)	14.36 (1.89)	14.31 (1.84)	14.20 (3.61)
	K-BIT Vocab	101.04 (11.97)	96.57 (8.95)	103.91 (11.41)	100.20 (17.03)
	K-BIT Matrices	108.81 (12.82)	105.67 (12.82)	113.42 (15.40)	107.30 (12.61)
	K-BIT Composite	105.70 (9.29)	101.24 (9.71)	110.45 (13.49)	104.50 (14.90)
	WTAR	40.44 (5.49)	36.73 (7.41)	40.15 (7.50)	36.00 (12.53)

Note. K-BIT = Kaufman Brief Intelligence Test; WTAR = Wechsler Test of Adult Reading.

Table S2 .

 S2 Cluster volumes for the most extreme 10% of Component 1 loadings, with anatomical descriptions, Montreal Neurological Institute (MNI) coordinates, and Brodmann's area (BA) for the peaks within each cluster.

	Cortical Regions	Cluster Volume voxels (mm 3 )	BAs for Peak Locations	MNI Coordinate for Peak Locations x y z	Loading Value
	Cluster 1: Bilateral	16717 133736
	Temporal Occipital Fusiform Cortex			37	32 -52	-20	0.37
	Temporal Occipital Fusiform Cortex			37	-32 -50	-22	0.37
	Temporal Occipital Fusiform Cortex			19	-30 -62	-18	0.37
	Occipital Fusiform Gyrus			19	-38 -64	-18	0.37
	Lateral Occipital Cortex, Inferior Division			19	40 -76	-14	0.34
	Lateral Occipital Cortex, Inferior Division			18	28 -86	6	0.33
	Lateral Occipital Cortex, Inferior Division			18	-28 -88	4	0.31
	Occipital Pole			18	16 -94	-4	0.29
	Lingual Gyrus			17	0 -84	-14	0.28
	Lingual Gyrus			18	-8 -90	-16	0.27
	Lateral Occipital Cortex, Superior Division			7	-28 -70	44	0.24
	Cluster 2: Left Hemisphere	5628	45024
	STG, Posterior Division			21	-58 -24	0	0.30
	STG, Posterior Division			22	-60 -38	4	0.29
	Inferior Frontal Gyrus, Pars Opercularis			44	-48 14	30	0.28
	Temporal Pole			38	-54 14	-4	0.27
	Precentral Gyrus			6	-48	4	44	0.27
	Cluster 3: Right Hemisphere	1310	10480
	STG, Anterior Division			22	60 -10	-2	0.27
	STG, Anterior Division			38	58	6	-8	0.25
	STG, Posterior Division			21	60 -30	4	0.23
	STG, Posterior Division			22	52 -34	6	0.22
	Cluster 4: Bilateral	308	2464
	Superior Frontal Gyrus			6	-4 12	56	0.25
	Supplementary Motor Area			6	-2	6	62	0.23
	Cluster 5: Left Hemisphere	128	1024
	Thalamus			27	-18 -28	-4	0.23
	Cluster 6: Right Hemisphere	21	168
	Thalamus			27	18 -28	-4	0.21
	Note. STG = Superior Temporal Gyrus

Table S3 .

 S3 Cluster volumes for the most extreme 10% of Component 2 loadings, with anatomical descriptions, Montreal Neurological Institute (MNI) coordinates, and Brodmann's area (BA) for the peaks within each cluster.

	Cortical Regions	Cluster Volume voxels (mm 3 )	BAs for Peak Locations	MNI Coordinate for Peak Locations x y z	Loading Value
	Positive Loadings
	Cluster 1: Right Hemisphere	3378 27024
	Occipital Pole		18	30 -90	4	0.25
	Occipital Fusiform Gyrus		19	34 -68 -16	0.23
	Temporal Occipital Fusiform Cortex		37	34 -50 -20	0.22
	Cluster 2: Left Hemisphere	2914 23312
	Lateral Occipital Cortex, Inferior Division		19	-26 -90	0	0.24
	Occipital Fusiform Gyrus		19	-34 -64 -18	0.22
	Occipital Fusiform Gyrus		18	-26 -78 -16	0.21
	Temporal Occipital Fusiform Cortex		37	-32 -48 -22	0.21
	Negative Loadings
	Cluster 1: Bilateral	8334 66672
	Precuneus Cortex		23	2 -52	52	-0.25
	Cingulate Gyrus, Posterior Division		23

Acknowledgements L.A.R. was supported by an Explora'Doc grant from the Rhône-Alpes region. T.S.W was supported by a scholar award from the Michael Smith Foundation for Health Research (MSFHR) and a New Investigator Award from the Canadian Institutes of Health Research (CIHR). Operating costs were supported by a grant to T.S.W from the Mind Foundation of British Columbia. The authors acknowledge the University of British Columbia MRI Research Centre, and thank John Paiement for assistance with fMRI-CPCA computer programming. Hallucinations in schizophrenia 17 Financial Disclosures The authors have declared that there are no conflicts of interest in relation to the subject of study.


A Jafari

L Petrillo

J Sarrazin

D Lautru

P De Doncker

A Benlarbi-Delai

TDOA Estimation Method Using 60GHz OFDM Spectrum

In the field of high data rate wireless communications, localization issues play a key role in achieving energy efficient communication and geographic routing. TDOA (Time Difference Of Arrival) based localization methods present numerous advantages. In this paper, a new method of TDOA estimation is proposed. With this method, unlike conventional TDOA measurements, it is possible to perform communication and localization at the same time by using a MISO system. By transmitting UWB OFDM signals using spatial diversity, it is possible to extract TDOA from interference patterns in spectral domain. In addition, increasing the precision of localization is also studied using a multi-band approach. This whole study is made within the framework of the WiGig alliance specifications, however it is compatible with other standards.

I INTRODUCTION

In the coming years, home wireless systems are expected to provide multi-gigabyte data rates, thus replacing cables for indoor communications. Wide-band communications using complex modulations such as OFDM (Orthogonal Frequency Division Multiplexing) are used more and more in short-range applications such as video streaming, wireless USB, etc. However, the current commercial wireless systems do not yet reach the necessary data rates for heavy applications such as HD video. Therefore, there is presently an attempt to develop a wireless UWB (Ultra Wide Band) technology at 60 GHz, providing an available bandwidth of 5 GHz everywhere [START_REF] Hansen | Wigig: Multi-gigabit wireless communications in the 60 ghz band[END_REF]. In this context, IEEE 802.15.3c standard has already been proposed, whereas other specifications, for example WiGig, are being elaborated [START_REF] Baykas | IEEE 802.15.3c: the first ieee wireless standard for data rates over 1 gb/s[END_REF][START_REF] Khiong | An overview of multigigabit wireless through millimeter wave technology: Potentials and technical challenges[END_REF]. Energy consumption in wireless networks is an essential factor with respect to its environmental impact as well as autonomy of the system. And this is even more so in the case of 60 GHz communications compared to the conventional wireless networks due to strong millimeter wave attenuation [START_REF] Park | Short-range wireless communications for next-generation networks: Uwb, 60 ghz millimeter-wave wpan, and zigbee[END_REF][START_REF] Patwari | Locating the nodes: cooperative localization in wireless sensor networks[END_REF]. Focalization of energy can lead to a decrease in consumption and to increasing the distance range of the wireless communications. This is why under development 60 GHz standards consider beam-forming. However, to be able to perform spatial focalization, communicating devices should be able to determine their locations. In addition, localization plays an important role in achieving a precise, low consumption wireless communication, since it is the basis of routing algorithms in multi-nodes networks [START_REF] Al-Karaki | Routing techniques in wireless sensor networks: a survey[END_REF]. In this article, a new technique of TDOA (Time Difference Of Arrival) estimation for wide-band wireless networks at 60 GHz in indoor applications is presented. It uses interferences in OFDM signal spectrum at the receiver (RX) in order to estimate the TDOA. This approach, allows to perform localization and data transmission simultaneously. The paper is organized as follows: in section II, concepts and formulations are presented. In section III, a simulation example is given and in section IV, a multi-band approach is explored in order to improve accuracy. Finally, section V concludes the paper.

II CONCEPTS AND FORMULATIONS A) Concept

In this paper, we focus on TDOA estimation because of its high precision in wireless indoor applications and the fact that the synchronization of reference devices (RD) and mobile device (MD) is not required in this positioning method. TDOA estimation is classically computed by using correlation techniques. In addition, DSSS (direct-sequence spread spectrum) signals can be used to extract the TDOA [START_REF] Liu | Survey of wireless indoor positioning techniques and systems[END_REF][START_REF] Li | Comparison of indoor geolocation methods in dsss and ofdm wireless lan systems[END_REF]. As presented in Figure . 1, multiple reference devices receive signal from one transmitter (mobile device) and the relative position of MD is determined by measuring the difference in time-arrival at each RD. By extracting the TDOA, the locus of points with constant range differences between two RD's, a hyperbola, is obtained. The spectrum of the received signal should be observed, and thanks to interferometry techniques in the frequency domain [START_REF] Bocquet | Using enhanced-tdoa measurement for indoor positioning[END_REF], the TDOA can be extracted as explained in the following section. In this approach, the baseline B (the distance between the two RD antennas) is relatively small, and, therefore, a wide-band signal should be used in order to extract small TDOA.

B) Formulation

To implement this technique, a MISO (Multi Input Single Output) structure is used. To do so, a reference device (RD) with two antennas A 1 and A 2 and a mobile device (MD) are placed in an indoor environment. The distance between MD and A 1 is d 1 and between MD and A 2 is d 2 . In the case of LOS (Line Of Sight) between RD and MD, the delays of propagation are τ 1 = d 1 /c and τ 2 = d 2 /c, with c the speed of light. A 1 and A 2 transmit the same OFDM 60 GHz signals with a sample rate frequency F s , N sub-carriers and M data sub-carriers, but with a delay of τ p . τ p is applied as suggested in [START_REF] Panta | Indoor localisation using white leds[END_REF], in order to vary the delay of the signal in a predetermined manner. If we call, x(t), the baseband complex envelope (CE) signal and, x RF (t), the RF representation of the transmitted signal, following equations are obtained:

x(t) = N/2-1 k=-N/2 c k e i2πkFst/N = M/2-1 k=-M/2 c k e i2πkFst/N (1)
and

x RF (t) = ℜ x(t)e i2πF RF t (2)
where ℜ is real part operator, c k are complex coefficients, with k the carrier index and F RF the RF frequency. Calling channel gains between A 1 and MD, and A 2 and MD, h 1 and h 2 , respectively, the time invariant channel impulse responses in the CE domain for the two different delays of propagation,τ 1 and τ 2 , are:

h 1 (t) = h 1 e -i2πF RF τ 1 δ(t -τ 1 ) (3)
and

h 2 (t) = h 2 e -i2πF RF (τ 2 +τp) δ(t -τ 2 -τ p ) ( 4
)
where δ is the Dirac function. Then, the received signal at MD, y(t) = x(t) ⊗ h(t) in CE domain is equal to:

y(t) = h 1 x(t -τ 1 )e -i2πF RF τ 1 + h 2 x(t -τ 2 -τ p )e -i2πF RF (τ 2 +τp) (5)
The two antennas at RD being relatively close to each other, we can assume in a LOS scenario, that h 2 = h 1 . Assuming that τ = τ p + τ 2 -τ 1 , the received signal in the frequency domain can be presented as follows:

Y (f ) = h 1 M/2 k=-M/2 c k δ(f -kF s /N )e -i2π(kFs/N +F RF )(τ 2 +τp-τ ) 1 + e -i2π(kFs/N +F RF )τ (6)
From equation ( 6), it can be shown that in the received spectrum, carriers k are canceled for values of τ given by:

τ = (2n + 1) 2( kFs N + F RF ) n = 0, 1, 2, ... (7)
Equation ( 7) can also be presented as follows:

kF s N = (2n + 1) 2τ -F RF n = 0, 1, 2, ... (8)
where kFs N is the k th sub-carrier. The frequency difference between two consecutive null sub-carriers (or minimum power sub-carriers in practice), F n = knFs N + F RF and F n+1 = k n+1 Fs N + F RF , is written as:

F n+1 -F n = ∆kF s N = 1 τ n = 0, 1, 2, ... (9)
where ∆k = k n+1 -k n and we supposed τ ≥ 0. Equation [START_REF] Bocquet | Using enhanced-tdoa measurement for indoor positioning[END_REF] shows that τ can be obtained on the received signal spectrum by measuring the frequency difference between two minimum power points or the difference between indexes of two consecutive minimum sub-carriers. Therefore, the value of TDOA= τ 2 -τ 1 = ττ p is also obtained. The limit values of τ that guarantee the cancellation of two sub-carriers are τ min = 2N M Fs and τ max = 3N M Fs . These values ensure the cancellation of at least two and at most three sub-carriers. Indeed, although the cancellation of more than two sub-carriers within the received spectrum does not affect the localization of an MD, it translates in a larger loss of the information carried by the OFDM symbols. Remembering that τ = τ p + τ 2 -τ 1 = τ p +TDOA, the value of τ p can be chosen to measure τ 2 -τ 1 with the maximum of dynamic range. The value of τ p , is consequently chosen as (τ max + τ min )/2.

III SIMULATION AND SYSTEM DESCRIPTION

Knowing the range of TDOA values that can be measured with the OFDM signal used, a possible configuration is proposed to perform the localization of an MD in a room. In Fig. 2, this configuration is presented with B the baseline distance and θ the angle of MD from baseline center. A 1 transmits the same signal as A 2 with a delay of τ p . The OFDM parameters are fixed according to the IEEE 802.15.3c standard. We thus consider F s = 2,64 GHz, N = 512 and M = 354. Therefore, the value of τ p is fixed at 1.37 ns. As an example, with a baseline B=8 cm and an MD located at d=2 m from RD with an angle of θ = 60 • , the theoretical value of τ = τ p +TDOA is τ = 1.14 ns, considering a LOS propagation. Therefore, according to equation ( 9), ∆k = 170 is expected. It should be noticed that the distance between RD antennas is chosen in such a way that the condition τ min ≤ τ ≤ τ max is satisfied. It should also be emphasized that if the delay τ p was not considered (τ p = 0), then the baseline should have been chosen equal to B=40 cm in order to obtain the same value of τ = 1.14 ns. To demonstrate the feasibility of our approach, a 60 GHz communication system is simulated using SystemVue software. As shown in Fig. 3, two direct paths with different path losses are considered, a delay block is used to define τ and a noise block and gain blocks are added in a manner to obtain at the receiver, an SNR of about 30 dB. Fig. 4a, Fig. 4b and Fig. 4c present respectively the constellation, the spectrum and the EVM (Error vector magnitude) of the received signal. As shown in Fig. 4a, the constellation at the RX presents a high quality communication in the LOS case. However, as shown in Fig. 4b, the spectrum of the signal is totally deformed and the positions of minimum power points lead us to extracting TDOA. A precise estimation of TDOA can be performed by looking at the EVM of received signal. As shown in Fig. 4c, the average EVM of received signal is about 2.5 percent but at the minimum power sub-carriers the EVM is about 15 percent. Therefore, the position of minimum power sub-carriers can be easily distinguished among the other sub-carriers. Fig. 4c confirms the value of 170 for ∆k, as predicted by the theory. This technique is a promising one as the localization data are carried by the minimum power sub-carriers, and therefore readily available from base-band processing.

IV Multi-band approach

As mentioned previously, the new proposed TDOA principle is based on the spectrum of the received interfered signal. Obviously, when a larger bandwidth is provided, a more precise TDOA can be achieved and hence a better localization. In the previous section, we considered an effective bandwidth of 2 GHz. Transmission of a wider bandwidth is not possible due to technology, standards and components' limitations. So a multi-band approach is proposed to encounter this problem. In this case, the localization and communication can not be achieved at the same time. Nevertheless, by using a multiband system and a signal post processing, the total available bandwidth when using 60 GHz bands, which is 7 GHz, can be used. To experimentally prove the multi-band approach, a wire-line communication and signals at the lower frequency bandwidths are chosen. To introduce the delay, two coaxial cables with different lengths were connected to the two channels of AWG (arbitrary waveform generator) where the same OFDM signals were generated (τ p = 0). As shown in Fig. 5, the two cables are then connected to a power combiner working in the 1-4 GHz band. The output signal is then connected to the VSA (vector signal analyzer) for detection and demodulation. For the multi-band approach, 6 OFDM signals with 500 MHz bandwidth each but with different center frequencies are generated in a manner that the whole 3 GHz bandwidth available between 1 to 4 GHz can be utilized. In each experiment one of these 6 OFDM signals is transmitted. At the end, the saved results are concatenated to cover the whole spectrum as shown in Fig. 6. Depending on the different delays, the positions of minimum power points change in the spectrum as expected. Three different delays are studied by changing the relative lengths of the two coaxial cables. To extract the highest TDOA value, TDOA= 2.2 ns, only one window of 500 MHz is sufficient since two consecutive minimum power points can be visualized in this bandwidth. But for TDOA= 0.95 ns and TDOA= 0.65 ns, respectively, three and four windows of 500 MHz are required. The frequency difference between two minimum power points is equal to 1/TDOA. To extract lower values of TDOA, wider bandwidths are required, thereby involving more windows.

V CONCLUSION

In this paper, a new method to estimate the TDOA is presented. This method is particularly well-suited for 60 GHz communication systems that use UWB OFDM signals. It was shown that, in the hypothesis of LOS scenario and the use of two antennas at reference device (RD), it is possible to extract TDOA on which localization algorithms are based. Besides, this technique, contrary to classical measurements of TDOA, has the advantage of performing localization and communication simultaneously. In addition, only one reference device with two antennas is used instead of two reference devices. A multi-band approach is also proposed to increase the localization precision. This approach has been experimentally verified at lower frequencies.

List of figures

Figure 1 :

 1 Figure 1: Classical TDOA positioning method.

Figure 2 :

 2 Figure 2: New proposed TDOA extraction method.

Figure 3 :

 3 Figure 3: Scheme of the simulated bench.

Figure 4 :

 4 Figure 4: Constellation, spectrum and EVM received signal in LOS scenario.

Figure 5 :

 5 Figure 5: Multi band experimental schematic.

Figure 6 :

 6 Figure 6: Concatenated multi-band received signals for three different TDOA values.

Fig. 1 .

 1 Classical TDOA positioning method. Fig. 2. New proposed TDOA extraction method. Fig. 3. Scheme of the simulated bench. Fig. 4. Constellation, spectrum and EVM of received signal in LOS scenario. Fig. 5. Multi band experimental schematic. Fig. 6. Concatenated multi-band received signals for three different TDOA values.


Rok Erman
email: rok.erman@gmail.com

František Kardoš
email: frantisek.kardos@upjs.sk

Jozef Miškuf
email: jozef.miskuf@upjs.sk

Long cycles in fullerene graphs

It is conjectured that every fullerene graph is hamiltonian. Jendrol' and Owens proved [J. Math. Chem. 18 (1995), pp. 83-90] that every fullerene graph on n vertices has a cycle of length at least 4n/5. Recently, Král' et al. improved it to 5n/6 -2/3.

In this paper, we study 2-factors of fullerene graphs. As a by-product, we get an improvement of a lower bound on the length of the longest cycle in a fullerene graph. We present a constructive proof of the bound 6n/7 + 2/7.

Introduction

Since the discovery of the first fullerene molecule [START_REF] Kroto | C 60 Buckminsterfullerene[END_REF] in 1985, the fullerenes have been objects of interest to scientists all over the world. The name fullerenes was given to cubic carbon molecules in which the atoms are arranged on a sphere in pentagons and hexagons. Fullerene graphs were defined as cubic (i.e. 3-regular) planar 3-connected graphs with pentagonal and hexagonal faces.

Various structural properties of fullerene graphs have been studied. See the papers [START_REF] Došlić | On lower bounds of number of perfect matchings in fullerene graphs[END_REF][START_REF] Došlić | On some structural properties of fullerene graphs[END_REF][START_REF] Došlić | Saturation number of fullerene graphs[END_REF][START_REF] Zhang | New lower bound on the number of perfect matchings in fullerene graphs[END_REF] for results on perfect matchings i.e. Kekulé structures of fullerenes. In [START_REF] Graver | The Independence Numbers of Fullerenes and Benzenoids[END_REF] the independence number of fullerenes is studied. See [START_REF] Malkevitch | Geometrical and Combinatorial Questions About Fullerenes[END_REF] for a list of open problems on fullerene graphs. One of the central questions remains to see whether this class of graphs is hamiltonian.

The hamiltonicity of various subclasses of 3-connected planar cubic graphs has been investigated. Grünbaum and Zaks [START_REF] Grünbaum | The existence of certain planar maps[END_REF] asked whether the graphs in the family G 3 (p, q) of 3-connected cubic planar graphs whose faces are of size p and q with p < q are hamiltonian for any p, q. Note that p ∈ {3, 4, 5} by Euler's formula. For recent results see [START_REF] Goodey | A class of hamiltonian polytopes[END_REF][START_REF] Goodey | Hamiltonian circuits in polytopes with even sided faces Israel[END_REF][START_REF] Owens | Non-hamiltonian simple 3-polytopes with only one type of face besides triangles[END_REF][START_REF] Zaks | Non-hamiltonian simple 3-polytopes having just two types of faces[END_REF].

Let us restrict our attention to fullerene graphs. For every fullerene graph, the leapfrog fullerene (graph obtained by replacing each vertex by a hexagon, see e.g. [START_REF] Fowler | An Atlas of Fullerenes[END_REF] for details) contains a hamiltonian path [START_REF] Marušič | Hamilton Cycles and Paths in Fullerenes[END_REF]. In general, Ewald [START_REF] Ewald | On shortness exponents of families of graphs[END_REF] proved that every cubic planar graph graph with faces of size at most 6 contains a cycle which meets every face of G. This implies that there is a cycle through at least n/3 of the vertices of any fullerene graph on n vertices. Jendrol' and Owens [START_REF] Jendrol | Longest cycles in generalized Buckminsterfullerene graphs[END_REF] gave a better bound of 4n/5. Recently, Král' et al. [START_REF] Král | Long cycles in fullerene graphs[END_REF] improved it to 5n/6 -2/3.

Results

The main result can be stated in the following way.

Theorem 1 Let G be a fullerene graph on n > 380 vertices. The length of the longest cycle in G is at least 6n+2 7 . We will prove the following propositions, from which the statement of Theorem 1 immediately follows.

Proposition 1 Let G be a fullerene graph on n > 380 vertices. There is a 2-factor of G consisting of at most n+12 14 cycles.

Proposition 2 Let G be a fullerene graph on n vertices. If there is a 2-factor G ′ consisting of c cycles, then there is a cycle in G of length at least n -2(c -1).

Proof of Proposition 1

Let us start with several definitions. A perfect matching in a graph G is a set of edges such that every vertex of G is incident with precisely one of them. A k-factor in a graph G is a k-regular spanning subgraph of G. A 1-factor is just a perfect matching. Note that if M is a perfect matching of a cubic graph G, then E(G) \ M forms a 2-factor of G.

Let G be a fullerene graph and M be a perfect matching in G. A hexagonal face f is called resonant in M , if precisely three edges incident with f are in M . Let G be a fullerene graph and G ′ be a 2-factor in G. A hexagonal face f is called a shift, if precisely three non-adjacent edges incident with f are in

G ′ . It is easy to see that f is resonant in M if and only if f is a shift in E(G) \ M .
The idea of the proof is as follows: First, we find a 2-factor in G. We proceed to delete some edges and after that add some other edges, in such a way that we get a collection of long cycles.

Search for a good start

Lemma 1 Let G be a fullerene graph on n > 380 vertices. Then there is a 2-factor G ′ of G such that at least one hexagon is a shift.

Proof. In [START_REF] Kardoš | Fullerene graphs have exponentially many perfect matchings[END_REF], it was proven that for every fullerene graph G on n vertices there is a decomposition of its edges into three perfect matchings M 1 , M 2 , M 3 , such that at least one of them, say M 1 , has at least n-380 61 resonant hexagons. Then G ′ = M 2 ∪ M 3 is a 2-factor of the graph G having at least n-380 61 shifts.

Let the edges of G ′ be black and the rest be white.

Lemma 2 There are no three shifts f 1 , f 2 , f 3 incident with a common vertex v.

Proof. Let v be a vertex of G. Then precisely two of the three edges incident with v are black and one of them is white. Thus, the face incident with the two black edges can not be a shift.

Let us transform all shifts as follows: For each shift f , recolor all three black edges incident with f white. Insert a new vertex v f in the center of f and join v f with the six vertices incident with f by six new black edges. Let the configuration of six triangles obtained this way be called a hole. Repeat the procedure until there are no shifts left. Let the resulting plane graph be G 1 (see Figure 1).

If we delete all the white edges in G 1 , we get the graph G 2 . Each vertex has degree 2 or 6 in it. We introduce a plane pseudograph (a graph with multiple edges and loops) H derived from G 2 by the following operation:

Contract every non-loop edge with at least one end-vertex of degree 2. Repeat this step until there are no more edges of this type. Note that the resulting pseudograph H does not depend on the order of the contractions. Its components are either loops, or 6-regular connected plane pseudographs. Vertices of degree 6 in H correspond to holes in G 1 . Proof. Assume there is at least one blue cycle in G. Since there is at least one shift in G, there is at least one black cycle in G. Therefore, there must be a face f incident with a blue edge and a black edge. Let C be the blue cycle incident with f and C ′ be the * *

f * f * f * * f * * f g Figure 2:
The list of all possible positions of black and blue edges incident with a face f . Blue edges are doubled.

black cycle incident with f . There are five possibilities (up to symmetry) of the position of blue and black edges incident with f , see Figure 2. Since C is not adjacent to a hole in G 1 , faces marked with an asterisk can not become holes, for they are incident with two consecutive black edges. If the face g were to become a hole in the process of obtaining G 1 , it forces the face f to become a hole (see Figure 3). A contradiction with C not being adjacent to a hole in G 1 . Therefore C ′ is a cycle not adjacent to any hole in G 1 thus it is blue, which is a contradiction. After this step there are no isolated loops in the graph H. There still can be some loops incident with a vertex of degree six (corresponding to a hole of G 1 ).

Lemma 4 If there are loops in H, then there are only two black cycles in G.

Proof. Lemma 3 insures that there are no blue cycles in G 1 . Therefore, the graph H is 6-regular. Let the six edge ends incident with a vertex f in H be denoted by 1,. . . ,6. Let us suppose that there is a loop l at f . It is obvious that it can connect two adjacent edge ends or two opposite ones. Without loss of generality it can either connect 1 and 2 or 3 and 6. If it connects 1 and 2 as in Figure 5, since there are no other holes incident with any edge of the black cycle in G 1 corresponding to the loop l, we apply the same reasoning as in Lemma 3 to come to the conclusion that there is a loop connecting 3 and 6 and after one more step a loop connecting 4 and 5.

If it connects 3 and 6 as in Figure 4, we simply apply the reasoning from Lemma 3 to the loop connecting 3 and 6 to get a loop connecting 1 and 2 and a loop connecting 4 and 5 (see Figure 5).

Therefore the only configuration of a hole with a loop is the rightmost one in Figure 5.

In this case there are no other holes adjacent to the loops, which means that the three loops contain all vertices of G 1 . This means that f was the only shift in G and therefore there are only two black cycles in G.

In the following we deal only with the case where there are no loops in H.

Deciding the holes

Now, we have the graph G in which black edges form a 2-factor, and the graph G 1 in which shifts were changed into holes. In G 1 , the black edges form a set of paths going from one hole to another. Let us call these paths tracks.

We introduce an algorithm for deciding the holes in such a way that all resulting black cycles are long enough. By deciding a hole f we mean recoloring three non-adjacent edges incident with f black and removing the vertex v f -this way the hole is changed back to a shift. There are always two possible decisions for each hole.

At the beginning, all black edges are on tracks. During the process, some black cycles and closed tracks will be created. By closed track we mean track that emerge and end in the same hole. Let us define the inside of a closed track ℓ: Let C be the component of G \ ℓ that has less vertices. Then the inside of ℓ is the graph induced on C ∪ ℓ. If we create a closed track such that there are less than three faces inside it, we color it red. We show that it is possible to find a sequence of hole decisions such that the number of red closed tracks does not exceed one.

If there is a red closed track ℓ, we decide the hole f incident with it in the way that prevents us from creating a short cycle, see Figure 6. We show that there is at most one new red closed track.

Let us assume there are two new red closed tracks. Then the two tracks incident with f are parts of two distinct red closed tracks. The closed track containing the edges -→ * * of ℓ contains at least the two faces adjacent to f (marked with an asterisk in Figure 6). The track can only be red if these are the only faces inside it. But that is not possible, since the two faces can not be adjacent in a fullerene graph.

Let there be no red closed tracks.

Let us define three special types of holes. A hole f is of type a, if all tracks starting in f end in the same hole f ′ . A hole f is of type b, if precisely 5 of the tracks starting in f end in the same hole f ′ . A hole f is of type c, if three tracks starting in f end in f ′ and the other three end in

f ′′ = f ′ .
The holes of the type a appear only in pairs. We can always decide those pairs in such a way that we get a single cycle, and the length of such cycle is at least 24, see Figure 7.

-→ Figure 7: Deciding the pair of holes of the type a; the shortest cycle that can be obtained this way.

The holes of the type b appear only in pairs, too. We can always decide those pairs in such a way that we get a long track. If the obtained track is closed its length is at least 19 edges (see Figure 8) and it is never red.

-→ Figure 8: Deciding the pair of holes of the type b; the shortest track that can be obtained this way.

Let there be no holes of the types a or b. Let f be a hole. There are two possible decisions for it. We claim that if f is not of type c, it can be decided in such a way that we get at most one red closed track.

For sake of a contradiction, assume that both decisions lead to at least two red closed tracks. Mark the tracks ending in f as p 1 up to p 6 in cyclic order. One decisions joins p 1 with p 2 , p 3 with p 4 and p 5 with p 6 . Without loss on generality suppose that p 1 with p 2 and p 3 with p 4 form two closed tracks. It means that p 1 and p 2 end in the same hole f 12 and p 3 and p 4 end in f 34 . If f 12 = f 34 , then since f is not of type a or b, p 5 and p 6 do not end in that hole. Then the other decision can make only one closed track, hence only one red closed track indeed, a contradiction (see Figure 9 for illustration). If f 12 = f 34 , then we can only get two closed tracks for the other decision if f is of type c, a contradiction again. If there are no red closed tracks and all holes are of the type c, the graph H consists of cycles with tripled edges. Consider one of them. If the number of holes on the cycle is even, we can decide them in such a way that we get only one long black cycle, see Figure 10. If their number is odd, we can decide them in such a way that we get two cycles of big average length, see Figure 11.

-→ Altogether, at the end of this process all the holes have been decided and black edges form a 2-factor again.

There are cycles of length at least 24 formed by pairs of holes of type a, pairs of cycles of average length at least 15 formed by holes of type c, or cycles with at least three faces inside. If there are three hexagons, the cycle has length 14. If there are k pentagons and 3 -k hexagons, the cycle has length 14 -k. Let the number of cycles of length 11 be c 11 , the number of cycles of length 12 be c 12 , the number of cycles of length 13 be c 13 , the number of all other cycles be c 14 and let c = c 11 + c 12 + c 13 + c 14 . Then since there are exactly 12 pentagons in a fullerene graph, 3c 11 + 2c 12 + c 13 ≤ 12.

On the other hand, 11c 11 + 12c 12 + 13c 13 + 14c 14 ≤ n.

Adding the two equations yields 14c ≤ n + 12. This is the bound needed.

Proof of Proposition 2

Proof. Let G ′ be a 2-factor. We color the edges of G ′ black, the other edges white. Initially, we color all the vertices black and then we recolor the vertices not on any black cycle to white.

If there are at least two cycles in the graph G ′ , there must be a face f incident with two different cycles C 1 and C 2 . If the face f is a pentagon, then we recolor the black edges incident with f white and vice-versa. This way the number of white vertices increases or decreases by 1 (see Figure 12 for illustration).

-→ -→

Figure 12: If a pentagon is incident with two cycles, we can change them to one cycle in such a way that the number of white vertices increases or decreases by 1.

←→ ←→ ←→

Figure 13: If a hexagon is incident with two cycles, we can change them to one cycle in such a way that the number of white vertices increases by at most 2.

If the face f is a hexagon which is not a shift, then the black edges incident with f induce 2 paths. We recolor the black edges incident with f white and vice-versa. This way the number of white vertices changes by -2, 0, or 2 (see Figure 13 for illustration).

If the face f is a shift, then two of its black edges are on one cycle, say C 1 , and one on the other cycle, C 2 . If any of the two faces adjacent to f and incident both with C 1 and C 2 is not a shift, we use that face to join C 1 and C 2 . If both those faces are shifts, then we change the color of the edges incident with the shift f . The number of cycles does not change, and the two faces that shared a black C 1 edge with f can now be used to join C 1 and C 2 , see Figure 14. This way we can always decrease the number of cycles by introducing at most 2 white vertices per cycle. Hence, the number of white vertices w is at most 2(c -1).

Figure 1 :Lemma 3

 13 Figure 1: A shift in G, a hole in G 1 and a corresponding structure of H.

Figure 3 :

 3 Figure 3: Left to right: the face f incident with a blue cycle and a black cycle, adjacent to a shift g in G; the face f incident with a blue cycle adjacent to a hole, f is now a shift; the face f becomes a new hole. Blue edges are doubled.

Figure 4 :

 4 Figure 4: The two possible types of loops incident with a vertex of H.

Figure 5 :

 5 Figure 5: One loop forces other two.

Figure 6 :

 6 Figure 6: Deciding the hole incident with a red closed track. Edges of the red closed track are doubled.

Figure 9 :

 9 Figure 9: If the pairs of tracks p 1 , p 2 and p 3 , p 4 lead to closed tracks, the other decision of the hole leads to at most one red closed track.

Figure 10 :

 10 Figure 10: Deciding the cycle of holes of the type c.

Figure 11 :

 11 Figure 11: If the holes of the type c form an odd cycle, we always get two cycles (left); the shortest possible pair of cycles that can be obtained this way have lengths 5 and 25 (right).

Figure 14 :

 14 Figure 14: If a shift f is incident with two cycles and g and h are shifts too, we can first switch the shift f and then change any of the faces marked with an asterisk to change the cycles to one cycle.

* Supported in part by bilateral project BI-SK/05-07-001 between Slovenia and Slovakia. † Supported in part by bilateral project SK-SI-00806 between Slovakia and Slovenia. ‡ Supported in part by Slovak Research and Development Agency under the contract No. APVV-0007-07.