U K Bhaskar

D Tierno

G Talmelli

F Ciubotaru

C Adelmann

T Devolder

BPZT HBARs for Magnetoelastic Stress Generation at GHz Frequencies

Keywords: Piezoelectrics, magnetoelectrics, HBAR BPZT HBARs for bias-tunable, stress generation at GHz frequencies

The high frequency performance of strong piezoelectric materials like PZT remains relatively less explored due to the assumption of large dielectric/ferroelectric losses at GHz frequencies. Recently, the advent of magnetoelectric technology as an on-chip route to excite magnetization dynamics has provided the impetus to evaluate the electromechanical performance of PZT at microwave frequencies. In this work, we demonstrate that HBARs fabricated using Barium-doped PZT (BPZT) films can efficiently generate acoustic waves up to 15 GHz. The ferroelectricity of BPZT endows added functionality to the resonator in the form of voltage tunability of the electromechanical performance. We extract the piezoelectric coefficient by numerically comparing the performance of BPZT with the Mason model. The extracted piezoelectric coefficient ~60 pm/V agrees well with reported values on thin film PZT measured at low frequencies (<100 MHz). Our results suggest that with further improvement in device design and material processing, BPZT resonators could operate as large amplitude, tunable stress transducers at GHz frequencies.

I. INTRODUCTION

train engineering has empowered the semiconductor revolution by providing tools to enhance the mobility of transistors [START_REF] Thompson | A logic nanotechnology featuring strained-silicon[END_REF], and control the bandgap of heterostructures [START_REF] Smith | Tuning the optical and electronic properties of colloidal nanocrystals by lattice strain[END_REF]. The role of strain in microelectronics is set to become more significant with recent proposals involving the incorporation of magnetic logic devices [START_REF] Manipatruni | Beyond CMOS computing with spin and polarization[END_REF], [START_REF] Manipatruni | Scalable energy-efficient magnetoelectric spin-orbit logic[END_REF]. Indeed, mechanical deformation is widely considered as a technologically relevant, energy-efficient, non-magnetic field route to controlling the orientation of magnetization in the material [START_REF] Nan | Quantification of strain and charge co-mediated magnetoelectric coupling on ultra-thin Permalloy/PMN-PT interface[END_REF]- [START_REF] Spaldin | Multiferroics: Past, present, and future[END_REF]. In contrast to semiconductor technology, where the deformation is statically induced via lattice mismatch, magnetic logic requires to dynamically switch between magnetization orientations and hence, requires to cycle the mechanical strain. For these applications, strong piezoelectric materials [START_REF] Nan | Quantification of strain and charge co-mediated magnetoelectric coupling on ultra-thin Permalloy/PMN-PT interface[END_REF], [START_REF] Ghidini | Shear-strain-mediated magnetoelectric effects revealed by imaging[END_REF] (PZT/PMN-PT) are required to efficiently provide the large deformations necessary to switch the magnetization of ferromagnetic materials. The combination of piezoelectric/ferromagnetic hybrids are popularly called magnetoelectric (ME) transducers [START_REF] Manipatruni | Scalable energy-efficient magnetoelectric spin-orbit logic[END_REF], [START_REF] Spaldin | Multiferroics: Past, present, and future[END_REF], [START_REF] Spaldin | Advances in magnetoelectric multiferroics[END_REF]. The voltage control of magnetization delivered by ME technology is crucial to perform low power, beyond CMOS logic operations using magnetic materials.

ME transducers are also essential to the realization of spin wave computing [START_REF] Chumak | Magnon spintronics[END_REF]- [START_REF] Fleet | Mux ado about magnons[END_REF], which is a different branch of magnetic logic technologies relying on encoding information in the phase of propagating spin waves. For these application, the role of the ME transducer is to perturb the magnetization order and generate spin waves by delivering lattice vibrations at frequencies above the ferromagnetic resonance (typically 1-30 GHz) [START_REF] Tierno | Strain coupling optimization in magnetoelectric transducers[END_REF], [START_REF] Li | Spin wave generation by surface acoustic waves[END_REF], [START_REF] Cherepov | Electric-field-induced spin wave generation using multiferroic magnetoelectric cells[END_REF]. Typical ME transducers proposed in literature for spin-wave computing applications rely on capacitive tranducers fabricated on strong piezoelectrics like PZT/PMN-PT [START_REF] Tierno | Strain coupling optimization in magnetoelectric transducers[END_REF], [START_REF] Cherepov | Electric-field-induced spin wave generation using multiferroic magnetoelectric cells[END_REF]. However, non-resonant operation of capacitive transducers make them fundamentally ill-equipped to be interfaced with microwave circuits. In contrast, acoustic resonators provide an established route to impedance matching and efficient transduction of energy between the mechanical and microwave domain. However, the weak piezoelectric coefficient of AlN [START_REF] Ruby | Became the Basis of a Multi-Billion Dollar Industry[END_REF] the material conventionally used in acoustic resonatorsimposes fundamental limits on the absolute magnitude of stress delivered and hence, limits the scope of its application as a ME transducer. On the other hand, the high frequency acoustic response of strong piezoelectric materials like PZT is relatively less explored owing to the assumption of large dielectric/ferroelectric losses at GHz frequencies. Thus, the characterization of the high frequency electromechanical response of strong piezoelectric materials like PZT is likely to benefit the development of ME tranducer technology.

In this work we demonstrate that high-overtone bulk acoustic resonantors (HBARs) fabricated on Ba0.1Pb0.9Zr0.52Ti0.48O3 (BPZT) films can generate acoustic modes up to 15 GHz, potentially providing an unique material platform to deliver both large stress at static conditions, and high frequency perturbations. The ferroelectricity of BPZT additionally provides an electric field dependent electromechanical transduction efficiency (K 2 ) and switchability of the acoustic response. The demonstrated BPZT HBARs could also find other applications where large amplitude stress transduction at GHz frequencies is desirable like for the mechanical manipulation of spin qbits and interfacing with superconducting qbits [START_REF] Kervinen | Interfacing planar superconducting qubits with high overtone bulk acoustic phonons[END_REF]. Finally, the test structure and techniques employed in this work can be used as a generic tool to characterize the electrical and electromechanical performance of thin film piezoelectrics at high frequencies.

The paper is organized as follows. Section 2 introduces both the experimental design of the device and its suitability to the dielectric and electromechanical characterization of BPZT at high frequencies. Section 3 discusses the identification of HBAR modes from the measured electrical impedance of the device and comparision with expectations from the Mason model. Finally section 4 comments on the potential usage of our transducers for magneto-electric generation of spin-waves.

II. EXPERIMENTAL DESIGN AND MODELS FOR EXTRACTING THE DIELECTRIC/ELECTROMECHANICAL PERFORMANCE

A. Material system: Barium-doped PZT thin films

Large stress generation requires a material with strong piezoelectric coefficient, free of current leakage and with negligible losses at microwave frequencies. There is a common belief that such materials do not exist: low loss piezoelectric materials like AlN have a modest piezoelectric coefficient, while strong ferroelectric materials like PZT are expected to be lossy at microwave frequencies. In contrast to this common thinking, we will show that when properly implemented, PZT can meet our needs. We deposited Bariumdoped PZT films by pulsed laser deposition in a Solmates SIP-700 system using a 10 nm thick LaNiO3 buffer layer and a Pt bottom electrode. Barium incorporation in PZT reduces the grain size [START_REF] Ramam | Ferroelectric and piezoelectric properties of Ba modified lead zirconium titanate ceramics[END_REF], increasing the dielectric integrity, without degrading the electromechanical performance. The Scherrer grain size, calculated from the XRD patterns, was found to be independent of the thickness and around 20-25 nm. Electron micrographs indicated that the grains were organized in a columnar fashion. The rms surface roughness of the BPZT film was as low as 6 nm. Further details about the material growth and device fabrication can be found elsewhere [START_REF] Tierno | Microwave Characterization of Ba-Substituted PZT and ZnO Thin Films[END_REF].

B. Geometry: concentric capacitor structures

In order to characterize the intrinsic electromechanical properties of BPZT films at microwave frequencies, we have patterned electrodes on top of the films using a one-step photolithography followed by a lift-off of a thick top electrode. Overall, the complete stack of the device is as follows Au (930 nm)/Ti(10nm)/BPZT (400 nm)/ LaNiO3 (10 nm)/Pt (70 nm)/Ti (10 nm)/ SiO2 (400 nm)/Si (750 µm, substrate).

A simple concentric capacitor (CC) geometry (Fig. 1a) was chosen to preserve the rotational invariance of the BPZT material properties. The central signal pad radius, a, of the CC was varied from 10 to 50 µm, while, the outer ground pad radius was fixed at 80 µm. Rather small feature sizes were chosen for two mains reasons that will appear clear later: first, it allows to model the system as a lumped electrical circuit, and second because it allows a better impedance matching thus improving the sensitivity of the measurements.

C. Dielectric permittivity and loss tangent

To check that the design and fabrication were satisfactory, we measured the dielectric permittivity and the loss tangent of the BPZT films using the concentric capacitors. For this we measured the scattering parameters of the capacitor in a calibrated 1-port measurement using a vector network analyser. The scattering parameters are then converted to impedance parameters using the characteristic impedance (50 Ω) of the measurement setup. The measured impedance z =r +jx is separated into real (r) and imaginary (x) part. The permittivity and loss tangent extracted by comparing the impedance parameters measured on two CC with different radius (a1 and a2). The explicit relation is given as [START_REF] Ma | RF measurement technique for characterizing thin dielectric films[END_REF]:

ε r = - ( 1 a 1 2 - 1 a 2 2 ) * t * (x 1 -x 2 ) (ωπε 0 ) [[(r 1 -r 2 - R S 2π ln ( a 2 a 1 ))] 2 + (x 1 -x 2 ) 2 ] , tanδ = (r 1 -r 2 - R S 2π ln ( a 2 a 1 )) (x 1 -x 2 ) ,
where Rs is the series resistanceextracted to be 2.1 Ohms, t is the thickness of BPZT (400 nm), a1 and a2 are the radii of two different CC, while r1, r2, and x1, x2, are respectively the real and imaginary part of the measured impedances.

The extracted permittivity and loss tangent of the 400 nm thick BPZT embodied in a CC is plotted in Fig 1(b). The dielectric permittivity was around 480 and decreased by less than 10% in the frequency range from 1-6 GHz. The dielectric loss increases with frequency as expected and was about 0.1 at 5 GHz. In addition to the monotonous capacitive response, we observed clear anomalies in the dielectric response and the loss tangent at specific frequencies (Fig. 2 and Fig. 3). These anomalies correspond to acoustic resonances in the capacitor structures.

D. Expected electromechanical performance of BPZT at high frequencies

Let us model how the acoustic resonances impact the impedance spectrum. The central part of the device under the signal pad can be understood as a High overtone bulk acoustic resonator (HBAR). HBARs are composite resonators in which the acoustical modes encompass both the BPZT film and the thick substrate. The BPZT film is a small fraction of the resonator volume, and hence the quality factor Q of the composite resonator is expected to correspond essentially to the low-loss, high quality silicon substrate. Upon RF excitation, the piezoelectric BPZT pumps mechanical energy in the form of travelling acoustic waves into the substrate. The silicon substrate acts as a Fabry-Perot cavity with two mirror surfaces defined by the large acoustic mismatch at the Si/SiO2 interface and the polished bottom surface respectively. Standing wave modes are created when the thickness of the substrate is an integer multiple of the acoustic wavelength. Thus, the acoustic resonant frequency of the silicon substrate determines the frequency intervals between each resonant mode or the free spectral range (FSR) of the resonator. The large thickness of silicon (𝑡 𝑆𝑖 ) substrate implies a dense spectrum of modes spaced at the substrate resonance determined by its sound velocity (𝑣 𝑆𝑖 ) as 𝑣 𝑆𝑖 /(2 * 𝑡 𝑆𝑖 ). The FSR is expected to be ~5.5 MHz. The amplitude of acoustic energy delivered by the piezoelectric is maximal around the thickness extensional modes of the piezoelectric film. For negligible electrode thickness, the piezoelectric resonance frequencies would be given as 𝑣 𝑝 /(2 * 𝑡 𝑝 ), where 𝑣 𝑝 and 𝑡 𝑝 are the acoustic velocity and thickness of the piezoelectric layer, respectively. However, the simple analytical formulation is not applicable for our device stack, with a thick top electrode and the isolating SiO2 layer underneath. Instead, the Mason model [START_REF] Mason | Electromechanical Transducers and Wave Filters[END_REF] is used for a more reasonable estimate of the impedance spectrum. The Mason model [START_REF] Mason | Electromechanical Transducers and Wave Filters[END_REF], [START_REF] Li | Resonance Spectrum Characteristics of Effective Electromechanical Coupling Coefficient of High-Overtone Bulk Acoustic Resonator[END_REF], [START_REF] Daniel | Elastic waves in solids I: Free and guided propagation[END_REF] is essentially a 1-D transmission line model that accounts for the electrical impedance presented by a mechanical wave propagating in a composite piezoelectric structure like ours. The acoustic impedance and velocity of each layer in the stack (Table I) is input to derive the acoustic resonance frequencies of the entire stack. The transformation from the mechanical to the electrical domain is made by incorporating an equivalent transformer, physically representing the electromechanical performance of the piezoelectric material. Mathematically, the transformer creates a coupling of magnitude √ 𝑑 33 * 𝐴 𝑡 * 𝑌 between the mechanical and electrical domains, where 𝑑 33 is the longitudinal piezoelectric coefficient, A is the area of the capacitor, t is the thickness of the piezoelectric and Y is the Young's modulus of BPZT.

The material parameters (Table I) can be measured from the recursive fitting of the experimental impedance spectra with the Mason model calculation. The fitting is carried out by (i) using the permittivity and loss tangent values extracted from the CC structures to model the frequency response of the capacitor and (ii) optimizing the turns ratio of the electromechanical transformer to reproduce the acoustic response. Thus, by independently measuring the permittivity, and capacitance in CC structures, we can numerically optimize the piezoelectric coefficient and acoustic velocity of BPZT to get good agreement with the measured data.

E. Numerical estimation of stress generation in BPZT HBARs

Let us now quantify the mechanical stress generated at resonance in the device. The computation of the stress is not accessible from purely electrical measurements, so we use a finite element simulation (COMSOL) to perform a numerical simulation of the complete stack and to quantify the mechanical stress generated at acoustic resonances. A frequency sweep is setup and acoustic resonances are identified as dielectric anomalies in the impedance sweep. A terminal voltage of 1V and reference impedance of 50 Ohms are used in the computation. Overtones of the fundamental thickness mode are observed as a function of the frequency. For a given geometry of the device, the frequency and the K 2 of the mode would determine the impedance at resonance. Maximum transduction of acoustic energy happens when the device impedance is close to 50 Ohms. Thus, the mechanical stress generated by an acoustic mode, for a constant voltage drive, would depend on the impedance of the device. As qualitatively expected, standing acoustical waves are observed in the silicon substrate at the HBAR mode frequencies. The frequencies obtained in the finite element simulation match closely those obtained from both the Mason model, and the next section will confirm that they are in line with the experimental measurements. The mechanical stress generated for the first and second thickness extensional modes of the piezoelectric film are shown in Fig 1 (c) and (d), respectively. The mechanical stress along a line cut across the HBAR structure reveals a coherent standing wave pattern across the thickness of the substrate. The oscillating stress pattern generated by the second thickness extensional mode of the BPZT (Fig 1d) has a larger amplitude and frequency than the first mode (Fig 1c) due to the better impedance matching of Mode 2, as we will confirm in the experimental impedance measurement. In order to benchmark the PZT microwave stress generator with state-of-the-art systems, we have also simulated the complete HBAR stack with AlN as piezoelectric material. The stress generated in the BPZT HBAR was found to be about an order of magnitude larger, when compared with the AlN HBAR, and can be related to the larger dielectric permittivity and piezoelectric coefficient of BPZT, as compared to AlN.

III. RESULTS AND DISCUSSION

A. Spectrum of acoustic modes and corresponding electromechanical coupling

The modulus of the complex impedance measured between 1-5.5 GHz on a CC with 50 µm radii defined on 400 nm thick BPZT film for 0 kV/cm and 250 kV/cm is shown in Fig 2 . The response at 0 kV/cm is devoid of any acoustic resonance and shows the expected capacitive (1/jωC) response. The large permittivity of BPZT can be observed to result in a small electrical impedance for the 50-µm radius of CC at GHz frequencies. As discussed, maximum stress generation would require the impedance of the resonator to be as close as possible to the 50 Ω source impedance. Thus, further scaling of the CC geometry is required to ensure 50 Ω impedance matching of BPZT at GHz frequencies.

At an applied dc field of 250 kV/cm, four clear envelopes of HBAR modes corresponding to longitudinal extensional modes of the piezoelectric film, m from 1 to 4, can be identified. In the inset of Fig 2, a zoom in to mode 3 reveals that the peaks are clearly spaced around ~5.5 MHz, as expected from the acoustic velocity and thickness of the substrate. A Lorentzian fit of the peaks is made to extract the Quality factor, yielding a value of ~950, which is similar to reported values in literature for HBARs on silicon substrates [START_REF] Pijolat | High Overtone Bulk Acoustic Resonator (HBAR)[END_REF]. This confirms our expectation that the mechanical losses in ferroelectric BPZT does not have a detrimental effect on the quality factor of the HBAR.

The Mason model estimate for the experimental measured structure is included in Fig 2 , showing good correspondence with the experimental data. The piezoelectric coefficient d33 was found to be 60-70 pm/V. This is the first estimate of the piezoelectric coefficient of BPZT at frequencies above 2 GHz, and the values are consistent with the range of values reported on thin film PZT [START_REF] Bhaskar | Flexoelectric MEMS: towards an electromechanical strain diode[END_REF], [START_REF] Lefki | Measurement of piezoelectric coefficients of ferroelectric thin films[END_REF], [START_REF] Hosseini | Stress-optic modulator in TriPleX platform using a piezoelectric lead zirconate titanate (PZT) thin film[END_REF] at low frequencies (<100 MHz). The acoustic velocity is estimated to be ~ 4800 m/s and a value of K 2 extracted ~12% for the first mode is much larger than AlN [START_REF] Ruby | Became the Basis of a Multi-Billion Dollar Industry[END_REF] and is close to previously measured values on PZT film bulk acoustic resonators (FBARs) [START_REF] Kirby | PZT thin film bulk acoustic wave resonators and filters[END_REF], [START_REF] Larson | PZT material properties at UHF and microwave frequencies derived from FBAR measurements[END_REF].

B. HBAR response versus capacitor size: electrical mismatch and physical clamping

The impedance spectra for different radii of CC were compared (Fig. 3 (a)) to elucidate the perturbation induced in the mechanical modes by the process of physically landing the probes on the measurement pads. A clear decrease in the Quality factor of HBAR modes is observed for decreasing radius of CCs. For these structures, the clamping from the probes mechanically dampens the substrate resonances, resulting in a lossy HBAR structure corresponding to the envelope of piezoelectric thickness modes. For the 50 µm radii (Fig 3(b)), the Quality factor extracted from a Lorentzian fit of experimental data is used for Mason model estimates. However, this method is not applicable to the smaller radii due to the significant mechanical clamping of the substrate modes caused by the landed microwave probes, and the resulting damping. Nevertheless, a good correspondence with the Mason model is achieved, if we assume a lower substrate Quality factor e.g. ~200 for the 15 µm radii [Fig 3(c)].

Note that the clamping from the microwave probe reduces the resonances quality factors but not the electromechanical characteristics of the BPZT film. Thus, even the capacitors with the smallest radii (15 µm) could be used to probe the characteristics of the film. Using a smaller capacitor area allows better impedance matching to 50 Ohms, a higher frequency RC cut-off, and lower leakage current and. Note that 50 Ohm impedance matched BPZT capacitors would require sub-10 µm capacitor surfaces, the artefact induced by the mechanical clamping by the microwave probes can be problematic. To benefit from the best of the ferroelectric material, it is desirable to laterally separate the HBAR mode from its electrical contact. A possible route is the use of an overlap capacitor geometry [START_REF] Rabus | High-overtone bulk-acoustic resonator gravimetric sensitivity: Towards wideband acoustic spectroscopy[END_REF].

C. Switchable HBAR response though ferroelectricity

In addition to its large piezoelectric coefficients, a further advantage of BPZT is that, being a ferroelectric material, exhibits a field-tenable electromechanical coupling the effective electromechanical coupling is field tuneable thanks to the intrinsic ferroelectricity. The field dependence of the piezoelectric modes is shown in Fig. 4a with a frequencyelectric field colour coded map with the value of the real part of the device impedance. Clear regions correspond to the case when the ferroelectric is in unpoled, non-piezoelectric state. For each resonant mode, the amplitude of the real part of the impedance increases with DC bias, indicating an increase in the transduction of acoustic energy. A gradual broadening in frequency space is also observed for increasing electric field, indicating a corresponding increase in the

K 2 = 𝑑 33 2 * Y ε r * ε 0 .
Let us understand the origin of this increased response. The capacitance and piezoelectric coefficient extracted from the Mason model are summarized in Fig. 4b for the same structure. As expected for a ferroelectric film, a large decrease in dielectric permittivity is observed as a function of the applied electric field. The piezoelectric coefficient saturates at larger fields and shows variation only around coercive fields due to the switching of the ferroelectric polarization. Thus, the continuous increase in the K 2 observed in Fig. 4a can be explained as originating from the sole decrease in the dielectric permittivity for a fixed piezoelectric coefficient. This bias induced control of the K 2 provides an elegant route for controlling the electromechanical performance of BPZT HBARs stress generators. In contrast, no such route exists to control the performance of current state-of-the-art HBARs realized with simple non-ferroelectric piezoelectric materials like AlN.

The impedance spectra for different radii of CC were compared (Fig. 3 (a)) to elucidate the perturbation induced in the mechanical modes by the process of physically landing the probes on the measurement pads. A clear decrease in the Quality factor of HBAR modes is observed for decreasing radius of CCs. For these structures, the clamping from the probes mechanically dampens the substrate resonances, resulting in a lossy HBAR structure corresponding to the envelope of piezoelectric thickness modes. For the 50 µm radii (Fig 3(b)), the Quality factor extracted from a Lorentzian fit of experimental data is used for Mason model estimates. However, this method is not applicable to the smaller radii due to the significant mechanical clamping of the substrate modes caused by the landed microwave probes, and the resulting damping. Nevertheless, a good correspondence with the Mason model is achieved, if we assume a lower substrate Quality factor e.g. ~200 for the 15 µm radii [Fig 3(c)].

D. High frequency capability of BPZT HBARs

The excitation of acoustic modes at microwave frequencies in BPZT films is commonly not expected. Indeed, it is generally anticipated that at these frequencies, the large tanδ of BPZT resulting from the large permittivity would fundamentally prohibit acoustic actuation. In our experiments, we found that while the extracted Tanδ >0.1 at 5 GHz, is very large when compared to AlN << 0.01 or LiNbO3 < 0.05, it does not impede the excitation of HBAR modes. This arises from the fact that the quality factor of the resonator is dominated by the substrate response instead of the sole PZT response. To illustrate this point, we plot in Fig. 5 the high frequency impedance spectra measured on 15 µm CC. Clear signatures of acoustic modes can be observed up to 15 GHz. Furthermore, all observed acoustic modes were found to be switchable and controllable with the magnitude of the applied DC bias. Thus, the observation of acoustic modes in BPZT up to 15 GHz, shows promise for using strong electromechanical materials for high frequency stress transduction.

IV. PROSPECTS FOR SPIN-WAVE MANIPULATION

The motivation of our work is to demonstrate that strong piezoelectric materials like BPZT which are already used as ME transducers for dc functionalities could also simultaneously excite magnetization dynamics at microwave frequencies through inverse magnetostriction in a magnetic film by coupling to the HBAR modes. Magnetoelastic coupling of thickness extensional HBAR modes to in-plane magnetized films has already been demonstrated by canting the piezoelectric polarization of ZnO HBARs [START_REF] Polzikova | Electroacoustic Excitation of Spin Waves and Their Detection due to the Inverse Spin Hall Effect[END_REF]. For the sake of illustration, let us assume a similar canting of the ferroelectric polarization can be realized in BPZT HBARs and compare their prospects as SW transducers. In the case of BPZT HBARS, the mechanical strain upon 1V excitation is estimated to reach values up to zz=10 -3 . Assuming a magnetoelastic coupling coefficient of B1=25.4 T for Ni [START_REF] Weiler | Elastically Driven Ferromagnetic Resonance in Nickel Thin Films[END_REF], the strain would translate to a dynamic effective magnetic field of 25 mT that can be used for a properly chosen misalignment between the magnetization and the strain axis. This applies if the magnetic material is positioned directly under the central pad of the CC and experiences a uniform zz strain field. Alternatively, the magnetic material can be coupled evanescently, by positioning it in lateral proximity to the CC, to harness magnetoelastic coupling to other components of the stress tensors. In any case, the strength of the RF magnetoelastic field can be about two orders of magnitude larger than the Oersted fields generated by inductive microwave antennas based SW transducers for a 1 V drive [START_REF] Demidov | Excitation of microwaveguide modes by a stripe antenna[END_REF]. Furthermore, the large frequency span of operation enabled displayed by the BPZT HBARs implies the generation of mechanical strain with a large bandwidth of wavevectors ranging from 1 radians/um to 20 radians/umvastly exceeding the capabilities of conventional microwave antennas [START_REF] Demidov | Excitation of microwaveguide modes by a stripe antenna[END_REF]. Finally, HBARs are technologically simple to fabricate, and the longitudinal mechanical stress generated could also be conveniently coupled to SW devices fabricated on the other side of the substrate, as demonstrated in [START_REF] Lisenkov | Magnetoelastic parametric instabilities of localized spin waves induced by traveling elastic waves[END_REF].

V. CONCLUSION

In summary, we have reported the first experimental demonstration of switchable, bias controlled HBAR modes excitable up to 15 GHz in BPZT films deposited on silicon. The measured response was fully comparable with a simple 1D Mason model estimate. The robust high frequency electromechanical performance of BPZT suggests a route to using the same material platform for large amplitude stress generation at both DC and GHz frequencies, as desired for magnetoelectric transducers technologies.

Figure 1

 1 Figure 1 (a) Simplified cross-section of the BPZT HBAR structure and illustration of concentric capacitor design; (b) the dielectric permittivity and loss extracted from the concentric capacitor structures; finite element model simulation of stress generated in the first (c) and second (d) longitudinal extensional modes for a 400 nm thick BPZT HBAR. The vertical scale starts at the SiO2/Si interface below the central pad of the concentric capacitor.

Figure 2 :

 2 Figure 2: Spectrum of the modulus of the impedance for a 400 nm thick BPZT HBAR based on a 50 µm concentric capacitor; four mode envelopes corresponding to increasing overtones of the fundamental thickness mode of the PZT film are observed. The inset zooms into one envelope to reveal peaks spaced at the resonant frequency of the substrate~5.5 MHz. Peaks share the same quality factor of 950.

Figure 3 (

 3 Figure 3(a) The real part of the impedance for a 400 nm thick BPZT film is plotted for different radii of concentric capacitors for 50 to 15 µm; (b) The experimental results (blue curve) and Mason model estimate (red curve) show good agreement for (b) 50 µm using a quality factor of 950 and (c) for 15 µm CC using a quality factor of 200.

Figure 4 :

 4 Figure 4: (a) The DC bias dependence of the resonances are shown by plotting the frequency-electric field map with the color representing the magnitude of the real part of the impedance for a 15 µm radius device on a 400 nm thick BPZT; (b) The permittivity extracted from the MBVD model is plotted as a function of the electric field and the extracted piezoelectric coefficient is also plotted for comparison.

Figure 5 :

 5 Figure 5: The real part of the impedance for a 10-µm radius of CC is plotted up to 16 GHz for 400 film for positive, negative and zero electric fields.

Table 1 Material properties used for the Mason model calculations

 1

	Layer	Thickness	Velocity	Acoustic
		(nm)	(m/s)	Impedance
				(M.Ohms)
	Silicon substrate	750*1000	9400	19.68
	Silicon oxide	400	5800	12.85
	Combined Bottom	92	3342	69.41
	electrode (Pt/LNO)
	BPZT	400	4800	30.1
	Top electrode	930	3356	63.8
	(Ti/Au)

ACKNOWLEDGMENT

This work was funded through the FETOPEN-01-2016-2017 -FET-Open research and innovation actions (CHIRON project: Grant agreement ID: 801055).


Julio Aracena

Maximilien Gadouleau

Adrien Richard

Lilian Salinas

Fixing monotone Boolean networks asynchronously

The asynchronous automaton associated with a Boolean network f : {0, 1} n → {0, 1} n is considered in many applications. It is the finite deterministic automaton with set of states {0, 1} n , alphabet {1, . . . , n}, where the action of letter i on a state x consists in either switching the ith component if f i (x) = x i or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word w fixes f if, for all states x, the result of the action of w on x is a fixed point of f . In this paper, we ask for the existence of fixing words, and their minimal length. Firstly, our main results concern the minimal length of words that fix monotone networks. We prove that, for n sufficiently large, there exists a monotone network f with n components such that any word fixing f has length Ω(n 2 ). For this first result we prove, using Baranyai's theorem, a property about shortest supersequences that could be of independent interest: there exists a set of permutations of {1, . . . , n} of size 2 o(n) such that any sequence containing all these permutations as subsequences is of length Ω(n 2 ). Conversely, we construct a word of length O(n 3 ) that fixes all monotone networks with n components. Secondly, we refine and extend our results to different classes of fixable networks, including networks with an acyclic interaction graph, increasing networks, conjunctive networks, monotone networks whose interaction graphs are contained in a given graph, and balanced networks.

Introduction

A Boolean network (network for short) is a finite dynamical system usually defined by a function f : {0, 1} n → {0, 1} n , x = (x 1 , . . . , x n ) → f (x) = (f 1 (x), . . . , f n (x)).

Boolean networks have many applications. In particular, since the seminal papers of McCulloch and Pitts [START_REF] Culloch | A logical calculus of the ideas immanent in nervous activity[END_REF], Hopfield [START_REF] Hopfield | Neural networks and physical systems with emergent collective computational abilities[END_REF], Kauffman [START_REF] Stuart | Metabolic stability and epigenesis in randomly connected nets[END_REF][START_REF] Stuart | Origins of Order Self-Organization and Selection in Evolution[END_REF] and Thomas [START_REF] Thomas | Boolean formalization of genetic control circuits[END_REF][START_REF] Thomas | Biological Feedback[END_REF], they are omnipresent in the modeling of neural and gene networks (see [START_REF] Bornholdt | Boolean network models of cellular regulation: prospects and limitations[END_REF][START_REF] Le | Quantitative and logic modelling of molecular and gene networks[END_REF] for reviews). They are also essential tools in computer science, for the network coding problem in information theory [START_REF] Ahlswede | Network information flow[END_REF][START_REF] Gadouleau | Reduction and fixed points of boolean networks and linear network coding solvability[END_REF] and memoryless computation [START_REF] Burckel | Computation with no memory, and rearrangeable multicast networks[END_REF][START_REF] Cameron | Computing in permutation groups without memory[END_REF][START_REF] Gadouleau | Memoryless computation: new results, constructions, and extensions[END_REF].

The "network" terminology comes from the fact that the interaction graph of f is often considered as the main parameter of f : it is the directed graph with vertex set [n] := {1, . . . , n} and an edge from j to i if f i depends on x j , that is, if there exist x, y ∈ {0, 1} n that only differ in the component j such that f i (x) = f i (y). An illustration is given in Figure 1(a-b).

From a dynamical point of view, the successive iterations of f describe the so called synchronous dynamics: if x t is the state of the system at time t, then x t+1 = f (x t ) is the state of the system at the next time. Hence, all components are updated in parallel at each time step. However, when Boolean networks are used as models of natural systems, such as gene networks,

x f (x) 000 000 001 000 010 001 011 001 100 010 101 000 110 010 111 100 The interaction graph of f . (c) The asynchronous automaton of f . synchronicity can be an issue. This led researchers to consider the (fully) asynchronous dynamics, where one component is updated at each time step (see e.g. [START_REF] Thomas | Regulatory networks seen as asynchronous automata: a logical description[END_REF][START_REF] Thomas | Biological Feedback[END_REF][START_REF] Thomas | Multistationarity, the basis of cell differentiation and memory. II. Logical analysis of regulatory networks in terms of feedback circuits[END_REF][START_REF] Abou-Jaoudé | Logical modeling and dynamical analysis of cellular networks[END_REF] for Boolean networks, and [START_REF] Fates | A guided tour of asynchronous cellular automata[END_REF][START_REF] Dennunzio | Computing issues of asynchronous ca[END_REF][START_REF] Dennunzio | m-asynchronous cellular automata: from fairness to quasi-fairness[END_REF] for the closely related model of cellular automata). In our setting, given an infinite sequence i 1 , i 2 . . . of elements in [n], called updating strategy, and an initial state x 0 , the resulting asynchronous dynamics is given by the recurrence x t+1 = f i t+1 (x t ), where, for each component i ∈ [n] and state x ∈ {0, 1} n , f i (x) := (x 1 , . . . , f i (x), . . . , x n ).

f 1 (x) = x 1 ∧ x 2 ∧ x 3 f 2 (x) = x 1 ∧ ¬x 3 f 3 (x) = x 2 ∧ ¬x 1 .
Functions f 1 , . . . , f n define, in a natural way, a deterministic finite automaton called asynchronous automaton of f : the set of states is {0, 1} n , the alphabet is [n] and f i (x) is the result of the action of a letter i on a state x; see Figure 1(c) for an illustration. This action is extended to words on the alphabet [n] in the natural way: the result of the action of a word w = i 1 i 2 . . . i k on a state x is inductively defined by f w (x) := f i 2 ...i k (f i 1 (x)) or, equivalently,

f w (x) := (f i k • f i k-1 • • • • • f i 1 )
. Hence, given an updating strategy i 1 , i 2 . . . and an initial state x 0 , the state of the system at time t in the resulting asynchronous dynamics is x t = f i 1 i 2 ...it (x 0 ).

In this paper, we introduce and study the following concepts.

Definition 1. A fixed point of f is any state x such that f (x) = x. A word w over the alphabet [n] fixes f if f w (x) is a fixed point of f for every state x. If w fixes f then w is a fixing word for f . If f admits a fixing word then f is fixable. If f is fixable then the fixing length of f , denoted λ(f ), is the length of a shortest word fixing f .

Hence, w fixes f if w sends any state to a fixed point of f . This corresponds to the situation where the start state of the asynchronous automaton of f is undetermined, and the accepting states are exactly the fixed points of f . As such, there is an obvious connection between fixing word and synchronizing words: if f has a unique fixed point, then w is a synchronizing word for the asynchronous automaton of f if and only if w fixes f . For instance, the network in Figure 1 is fixed by w = 1231. Hence it is fixable, and since it has a unique fixed point, its asynchronous automaton is synchronizing.

It is easy to check that f is fixable if and only if, for every state x, there is a word w such that f w (x) is a fixed point. We may then think that fixability is a rather strong property.

However it is not. Indeed, Bollobás, Gotsman and Shamir [START_REF] Bollobás | Connectivity and dynamics for random subgraphs of the directed cube[END_REF] showed that, considering the uniform distribution on the set of n-component networks, the probability for f to be fixable when f has at least one fixed point tends to 1 as n → ∞. Thus almost all networks with a fixed point are fixable. In turn, this shows that, for n large, a positive fraction of all n-component networks are fixable.

Theorem 1 (Bollobás, Gotsman and Shamir [START_REF] Bollobás | Connectivity and dynamics for random subgraphs of the directed cube[END_REF]). Let φ(n) be the number of fixable n-component networks. We have

lim n→∞ φ(n) 2 n2 n = 1 - 1 e .
Thus the family of fixable networks is huge, and it makes sense to study it. In this paper, we focus on the fixing length of fixable networks, introduced above. For instance, we have seen that w = 1231 fixes the network in Figure 1, thus this network has fixing length at most 4, and it is easy to see that no word of length three fixes this network. Thus it has fixing length exactly 4. It is easy to construct a fixable n-component network f such that λ(f ) is exponential in n, as follows. Let x 1 , . . . , x 2 n be a Gray code ordering of {0, 1} n , i.e. x k and x k+1 only differ by one component, say

i k , for 1 ≤ k < 2 n . Then let f (x k ) := x k+1 for 1 ≤ k < 2 n and f (x 2 n ) := x 2 n .
It is clear that i 1 , . . . , i 2 n -1 is the unique shortest word fixing f , and thus λ(f ) = 2 n -1.

We are then interested in networks f which can be fixed in polynomial time, i.e. λ(f ) is bounded by a polynomial in n. More strongly, we extend our concepts to entire families F of n-component networks. We say that F is fixable if there is a word w such that w fixes f for all f ∈ F, which is clearly equivalent to: all the members of F are fixable. The fixing length λ(F) is defined naturally as the length of a shortest word fixing F. We are then interested in families F which can be fixed in polynomial time. We will identify several such families, and for each, we will derive an upper bound on λ(F) and a lower bound on the maximum λ(f ) for f ∈ F. Up to our knowledge, the only result of this kind was given in [START_REF] Fogelman | Transient length in sequential iteration of threshold functions[END_REF], where it is shown that the word 12 . . . n repeated n(3n -1) times fixes any n-component symmetric threshold network with weights in {-1, 0, 1}. This family of threshold networks has thus a cubic fixing length. We could also mention somewhat less connected works concerning the minimal, maximal and average convergence time toward fixed points in the asynchronous setting for some specific fixable networks [4,[START_REF] Melliti | On the convergence of Boolean automata networks without negative cycles[END_REF][START_REF] Melliti | Asynchronous simulation of boolean networks by monotone boolean networks[END_REF][START_REF] Fates | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF][START_REF] Fates | A guided tour of asynchronous cellular automata[END_REF].

Our main results concern the family of monotone networks. We say that f is monotone if x ≤ y implies f (x) ≤ f (y) for all states x, y, where x ≤ y means x i ≤ y i for all i ∈ [n]. The fact that monotone networks are fixable is not obvious and proved in [START_REF] Melliti | On the convergence of Boolean automata networks without negative cycles[END_REF]. Our first main result shows that some monotone networks have a quadratic fixing length.

Theorem 2. For every positive integer n, there exists an n-component monotone network with fixing length Ω(n 2 ).

For the proof, we establish, using Baranyai's theorem, the following property about shortest supersequences that could be of independent interest (permutations of [n] are regarded as ordered arrangements, and any sequence obtained by deleting some elements in a sequence s is a subsequence of s). Theorem 3. For every positive integer n, there exists a set of permutations of [n] of size 2 o(n) such that any sequence containing all these permutations as subsequences is of length Ω(n 2 ).

Theorem 2 trivially shows that the fixing length of the family of n-component monotone networks is at least quadratic, but we have not been able to obtain a super-quadratic lowerbound for this fixing length. Our second main result is that, conversely, the fixing length of the family of n-component monotone networks is at most cubic. Theorem 4. For every positive integer n, there is a word of length O(n 3 ) that fixes every n-component monotone network.

Our last main result refines the previous one using the interaction graph. The transversal number of a directed graph is the minimum number of vertices to delete to make the directed graph acyclic.

Theorem 5. Let G be an n-vertex directed graph with transversal number τ . There is a word of length O(τ 2 n) that fixes every n-component monotone network with an interaction graph isomorphic to a subgraph of G.

Note that Theorem 4 trivially shows that the fixing length of a given monotone network is at most cubic, and we have not been able to obtain a sub-cubic upper-bound for this fixing length. However, Theorem 5 shows that, for bounded transversal number, the fixing length of a given monotone network is only linear. Note also that one obtains Theorem 4 from Theorem 5 when G is the complete directed graph on n vertices (with n 2 edges).

The paper is organized as follows. In Section 2, we give some basic definitions and notations. We also introduce two families of networks, the acyclic and increasing networks, and show that the fixing length of these two families is asymptotically n 2 . For that, we use results concerning n-complete words. The technics introduced are then used, in Section 3, to analyse the fixing length of monotone networks. Quantitative versions of Theorems 2, 3 and 4 are proved there. Section 4 gives some refinements and extensions. We first study the fixing length of conjunctive networks, which are particular monotone networks. Then, we prove a quantitative version of Theorem 5 and we study the fixing length of the family of balanced networks, which generalize monotone networks. Finally, a conclusion and some perspectives are given in Section 5.

Preliminaries

Basic definition and notations

Let w = w 1 . . . w p be a word. The length p of w is denoted |w|. For any word w and any k ≥ 1, the word k • w is obtained by repeating w exactly k times; 0 • w is the empty word. For all i ∈ [n], we denote as e i the i-th unit vector, i.e. e i = (0, . . . , 0, 1, 0, . . . , 0) with the 1 in position i. Given x, y ∈ {0, 1} n , x + y is applied componentwise and computed modulo two. For instance, x and x + e i only differ in the ith position. The state containing only 1s is denoted 1, and the state containing only 0s is denoted 0. We equip {0, 1} n with the partial order ≤ defined as follows: for all x, y ∈ {0, 1} n , x ≤ y if and only if x i ≤ y i for all i ∈ [n]. The Hamming weight of x, denote w H (x), is the number of 1s in x. Let f be an n-component network. We set f ǫ := id and, for any integer i and x ∈ {0, 1} n , we define f i (x) as in the introduction if i ∈ [n], and

If S = {i 1 , i 2 , . . . i q } ⊆ [p] with i 1 < i 2 < • • • < i q , then
f i (x) := x if i ∈ [n]
. This extends the action of letters in [n] to letters in N, and by extension, this also defines the action of a word over the alphabet N.

Graphs are always directed and may contain loops (edges from a vertex to itself). Paths and cycles are always directed and without repeated vertices. Given a graph G with vertex set V (such a graph is a graph on V ) and I ⊆ V , we denote by G[I] the subgraph of G induced by I, and G \ I = G[V \ I]. We refer the reader to the authoritative book on graphs by Bang-Jensen and Gutin [START_REF] Bang | Digraphs: Theory, Algorithms and Applications[END_REF] for some basic concepts, notation and terminology.

We now recall from the introduction the definition of monotone networks.

Definition 2 (Monotone networks). An n-component network f is monotone if, ∀x, y ∈ {0, 1} n , x ≤ y ⇒ f (x) ≤ f (y).
The family of n-component monotone networks is denoted F M (n).

The fixing length of

F M (n) is denoted λ M (n). More generally, if F X (n) is any family of n-component fixable networks, then λ X (n) is the fixing length of F X (n). If G is a graph on [n],
then F (G) denotes the set of n-component networks f such that the interaction graph of f is a subgraph of G. Then, F X (G) := F X (n) ∩ F (G) and λ X (G) is the fixing length of F X (G).

Acyclic networks

Our first results concern acyclic networks. Definition 3 (Acyclic networks). An n-component network f is acyclic if its interaction graph is acyclic. The family of n-component acyclic networks is denoted F A (n).

An important property of acyclic networks is that they have a unique fixed point [START_REF] Robert | Iterations sur des ensembles finis et automates cellulaires contractants[END_REF] and that they have an acyclic asynchronous graph [START_REF] Robert | Les systèmes dynamiques discrets[END_REF] (the asynchronous graph of an n-component network f is the graph on {0, 1} n with an edge from x to y f i (x) = y = x for some i ∈ [n]). This obviously implies that F A (n) is fixable. We show here that the fixing length of acyclic networks are rather easy to understand. The techniques used will be useful later, for analyzing the fixing length of monotone networks.

Lemma 1. Let G be an acyclic graph on [n] and f ∈ F (G). If a word w contains, as subsequence, a topological sort of G, then w fixes f . Furthermore, λ(f ) = n.

Proof. Let y be the unique fixed point of f . Let u = i 1 i 2 . . . i n be topological sort of G, and let w = w 1 w 2 . . . w p be any word containing u as subsequence. Hence, there is a increasing sequence of indices j 1 j 2 . . . j n such that u = w j 1 w j 2 . . . w jn . Let x 0 be any initial state, and for all q ∈ [p], let x q be obtained from x q-1 by updating w q , that is, x q := f wq (x q-1 ). Equivalently,

x q := f w [1,q] (x 0 ). Let us prove, by induction on k ∈ [n], that x q i k = y i k for all j k ≤ q ≤ p. Since i 1 is a source of the interaction graph, f i 1 is a constant. Thus f i 1 (x q ) = f i 1 (y) = y i 1 for all q ∈ [p],
and since w j 1 = i 1 , we deduce that x q i 1 = y i 1 for all j 1 ≤ q ≤ p. Let 1 < k ≤ n. Since f i k only depends on components i l with 1 ≤ l < k, and since, by induction, x q i l = y i l for all 1 ≤ l < k and j k-1 ≤ q ≤ p, we have f i k (x q ) = f i k (y) = y i k for all j k-1 ≤ q ≤ p. Since w j k = i k we deduce that x q i k = y i k for all j k ≤ q ≤ p, completing the induction step. Hence, f w (x 0 ) = x q = y for any initial state x 0 , thus w fixes f . We deduce that, in particular, any topological sort u of G fixes f , thus λ(f ) ≤ n. Conversely, if a word w fixes f , then f w (¬y) = y, and hence at least n asynchronous updates are required, that is, the length of w is at least n. Thus λ(f ) = n.

The converse of the previous proposition is false in general (for instance if f is the 3component network defined by f 1 (x) = 0, f 2 (x) = x 1 and f 3 (x) = x 1 ∧ x 2 , then 132 fixes f while 123 is the unique topological sort of the interaction graph of f ) but it holds for conjunctive networks, which are specific monotone networks.

Definition 4 (Conjunctive networks). An n-component network f is conjunctive if, for all i ∈ [n], there exists J i ⊆ [n] such that, ∀x ∈ {0, 1} n , f i (x) = j∈J i x j , (1)
and

f i (x) = 1 is J i is empty. The family of n-component conjunctive networks is denoted F C (n).
Let G be a graph on [n]. The conjunctive network on G is the unique conjunctive network whose interaction graph is G. Namely, it is the n-component network f such that (1) holds for all i ∈ [n] when J i is the set of in-neighbors of i in G.

Lemma 2. Let G be an acyclic graph on [n] and let f be the conjunctive network on G. A word w fixes f if and only if it contains, as subsequence, a topological sort of G.

Proof. According to Lemma 1, it is sufficient to prove that if w = w 1 w 2 . . . w p fixes f then w contains, as subsequence, a topological sort of G. Let x 0 := 0 and x q = f wq (x q-1 ) for all q ∈ [p]. Since w fixes f and since 1 is the unique fixed point of f , we have f w (x 0 ) = x p = 1. Thus for each i ∈ [n], there exists t i such that x t i i = 1 and x q i = 0 for all 0 ≤ q < t i . We have, obviously, w t i = i. Let i 1 i 2 . . . i n be the enumeration of the vertices of G such that t i 1 t i 2 . . . t in is increasing. In this way i 1 i 2 . . . i n is a subsequence of w, and it follows the topological order. Indeed, suppose that G has an edge from i k to i l . Since

f i l (x t i l -1 ) = x t i l i l = 1, we have x t i l -1 i k = 1, and thus t i k < t i l , that is, i k is before i l in the enumeration.
As an immediate application we get the following characterization.

Proposition 1. Let G be an acyclic graph on [n]. A word w fixes F (G) if and only if it contains, as subsequence, a topological sort of G.

To go further, we need the following concepts.

Definition 5 (Complete word). A word w is complete for a finite set S (or S-complete) if it contains, as subsequence, all the permutations of S. An n-complete word is a [n]-complete word. The length of a shortest n-complete word is denoted λ(n).

Interestingly, λ(n) is unknown. Let w 1 , . . . , w n be n permutations of [n] (not necessarily distinct). Then the concatenation w 1 w 2 . . . w n clearly contains all the permutations of [n]. Thus λ(n) ≤ n 2 . Conversely, if w contains all the permutations of n, then |w| n is at least n! and we deduce that |w| ≥ n 2 /e 2 (this simple counting argument will be reused later). This shows that the magnitude of λ(n) is quadratic. We have however the following tighter bounds. Theorem 6. We have λ(n) ∼ n 2 . More precisely:

λ(n) ≤ n 2 -2n + 4 for all n ≥ 1 [2] λ(n) ≤ n 2 -2n + 3 for all n ≥ 10 [34] λ(n) ≤ n 2 -7 3 n + 19 3 for all n ≥ 7 [26] λ(n) ≥ n 2 -C ε n 7/4+ε [21]
where ε > 0 and C ε is a positive constant that only depends on ε.

We also need another family of networks.

Definition 6 (Path networks). An n-component network f is a path network if its interaction graph if a path. The family of n-component path networks is denoted F P (n).

Note that path networks are both acyclic and conjunctive. Note also that an n-component network f is a path network if and only if there is a permutation i

1 i 2 . . . i n of [n] such that f i 1 (x) = 1 and f i k (x) = x i k-1 for all 1 < k ≤ n and x ∈ {0, 1} n .
There is thus a natural bijection between the permutations of [n] and F P (n). We show below that the family F P (n) has a quadratic fixing length.

Lemma 3. A word w fixes F P (n) if and only if it is n-complete. Hence λ P (n) = λ(n).
Proof. By Lemma 1, any n-complete word fixes F A (n) and thus F P (n) in particular. Conversely, suppose that w fixes F P (n). Since each permutation of n is the unique topological sort of the interaction graph of exactly one network in F P (n), by Lemma 2, w contains, as subsequence, the n! permutations of n. Thus w is n-complete.

As an immediate consequence, we get the following proposition.

Proposition 2. A word w fixes F A (n) if and only if it is n-complete. Hence λ A (n) = λ(n).
Remark 1. By Lemma 3 and Proposition 2, it is as hard to fix F P (n) as to fix F A (n): these two families have the same quadratic fixing length, while F P (n) is much smaller than F A (n) (the former has n! members while the latter has 2 Θ(2 n ) members). We shall use this to our advantage when designing a monotone network with quadratic fixing length in Section 3.1.

Increasing networks

Definition 7 (Increasing networks). An n-component network f is increasing if, ∀x ∈ {0, 1} n , x ≤ f (x).
The family of n-component increasing networks is denoted F I (n).

We prove below that, as for path networks and acyclic networks, the fixing length of increasing networks is λ(n). Increasing networks are thus relatively easy to fix collectively. We shall use this fact when constructing a cubic word fixing all monotone networks in Section 3.2. Lemma 4. Let f be an n-component network and x ∈ {0, 1} n . If f u (x) ≤ f uv (x) for any words u and v, then f w (x) is a fixed point of f for any word w containing all the permutations of {i : x i = 0}. Similarly, if f u (x) ≥ f uv (x) for any words u and v, then f w (x) is a fixed point of f for any word w containing all the permutations of {i :

x i = 1}.
Proof. Suppose that f u (x) ≤ f uv (x) for any words u and v, and that w = w 1 w 2 . . . w p be Scomplete, with S := {i : x i = 0}. Let x 0 := x and x q := f wq (x q-1 ) for all q ∈ [p]. By hypothesis,

x 0 ≤ x 1 ≤ • • • ≤ x q .
Suppose for the sake of contradiction that x p = f w (x) is not a fixed point, i.e. there is j such that f j (x p ) > x p j . Let t 1 , . . . , t m ∈ [p] be the set of positions such that

x t k -1 < x t k , and let i k := w t k for all k ∈ [m]. Clearly, j = i k for every k ∈ [m]. Setting t 0 := 0, we have x t k-1 = x t k -1 , thus f i k (x q ) = f i k (x t k -1 ) = x t k > x t k -1 = x q for all t k-1 ≤ q < t k . We deduce that i k does not appear in w [t k-1 ,t k -1] or, equivalently, t k is the first position of i k in w [t k-1 ,p]
. Similarly, we have x tm = x p , thus f j (x q ) = f j (x p ) > x p j = x q j for all t m ≤ q ≤ p and we deduce that j does not appear in w [tm,p] . Since w is S-complete, the sequence i 1 i 2 . . . i m j appears in w, say at positions w

s 1 w s 2 . . . w sm w s m+1 . Since t k is the first position of i k in w [t k-1 ,p] , we have s k ≥ t k for all k ∈ [m]. In particular, s m ≥ t m , thus j appears in w [tm,p] which is the desired contradiction. If f u (x) ≥ f uv (x)
for any words u and v the proof is similar.

Proposition 3. A word w fixes F I (n) if and only if it is n-complete. Hence λ I (n) = λ(n).
Proof. If w is n-complete, then w fixes f by Lemma 4. Conversely, suppose that w fixes all n-component increasing networks and let i 1 i 2 . . . i n be any permutation of [n]. Let y 0 := 0 and y k := y k-1 + e i k for all k ∈ [n]. Then y 0 y 1 . . . y n is a chain from 0 to 1 in the hypercube Q n . Let f be the n-component increasing network defined by

f (x) := y k+1 if x = y k and 1 ≤ k < n, x otherwise.
Then 1 is the unique fixed point of f reachable from 0 in the asynchronous graph, and it is easy to check that f w (0) = 1 if and only if i 1 i 2 . . . i n is a subsequence of w. Thus w is n-complete.

On the other hand, some increasing networks have quadratic fixing length. The proof requires the machinery developed for monotone networks, and as such we delay its proof until Section 3.1.

Theorem 7. For any ε > 0 and n sufficiently large, there exists f

∈ F I (n) such that λ(f ) ≥ 1 e -ε n 2 .
Remark 2. A simple exercise shows that the number of increasing networks is doubly exponential:

|F I (n)| = 2 n2 n-1 .
It is then remarkable that, while some increasing networks have quadratic fixing length, all the increasing networks can be fixed together in quadratic time still.

Remark 3. The dual f of a network f is defined as f (x) = f (x + 1) + 1. It is easily checked that a word fixes f if and only if it fixes f . Since a network is increasing if and only if its dual is decreasing, i.e. x ≥ f (x) for all x, the above results also holds for decreasing networks.

3 Monotone networks

A monotone network with quadratic fixing length

The aim of this section is to exhibit a monotone network with quadratic fixing length. As we saw in Section 2.2, the family of path networks F P (n) has quadratic fixing length. Therefore, our strategy is to "pack" many of these path networks in the same network f . As an illustration of this strategy, we first describe a monotone network with fixing length of order (n/ log n) 2 .

Let n = m + r where m! ≤ r r/2 , and let us write F P (m) = {h 1 , . . . , h m! }. There is then a surjection φ : X → [m!] where X is the set of states in {0, 1} r with Hamming weight r/2. The n-component network f then views the r last components as controls, that decide, through φ, which network in F P (m) to choose on the first m components. More precisely, by identifying {0, 1} n with {0, 1} m × {0, 1} r , we define f as follows:

f (x, y) :=      (1, y) if w H (y) > r/2, (h φ(y) (x), y) if w H (y) = r/2, (0, y) if w H (y) < r/2.
The first and third cases are there to guarantee that f is indeed monotone. Since any network in F P (m) can appear, a word fixing f must fix F P (m). Thus a word fixing f is m-complete, and hence has length Ω(m 2 ). Choosing m = Ω(n/ log n) then yields Ω(n 2 / log 2 n).

The network above reached a fixing length of Ω(m 2 ) because it packed all possible networks in F P (m). However, it did not reach quadratic fixing length because m had to be o(n) in order to embed all m! networks of F P (m) in X. Thus, we show below that only a subexponential subset of F P (m) is required to guarantee Ω(m 2 ). This is equivalent to prove that there exists a subexponential set of permutations of [m] such that any word containing these permutations as subsequences is of length Ω(m 2 ). In that case, we can use m = (1o(1))n, and hence reach a fixing length of Ω(n 2 ).

The main tool is Baranyai's theorem, see [START_REF] Jacobus | A Course in Combinatorics[END_REF]. Proof. According to Baranyai's theorem, there exists a collection of r := b -1 n a partitions of [n] into b sets of size a, such that each a-subset of [n] appears in exactly one partition. Let A 0 , . . . , A r-1 be these partitions. For each 0 ≤ i < r, we set

A i = {A i 0 , . . . , A i b-1 }.
Then, for all 0 ≤ i < r and 0 ≤ j, k < b we set S i,j k := A i j+k and

S i,j := S i,j 0 S i,j 1 . . . S i,j b-1 = A i j+0 A i j+1 . . . A i j+b-1
where addition is modulo b. So, the S i,j form a set of n a ordered partitions of [n] in b sets of size a. The interesting point is that, for all fixed i and fixed ℓ, the sequence S i,0 ℓ S i,1 ℓ . . . S i,b-1 ℓ is a permutation of A i (namely S i,ℓ ). Since each a-subset of [n] appears in exactly one A i , we deduce that, for any fixed ℓ, the set of S i,j ℓ is exactly the set of a-subsets of [n].

Given an a-subset X of [n] and a permutation σ of [a], we set σ(X) = i σ(1) i σ(2) . . . i σ(a) , where i 1 , i 2 , . . . , i a is an enumeration of the elements of X in the increasing order. Let σ 0 , . . . , σ a!-1 be an enumeration of the permutations of [a]. For all 0 ≤ i < r, 0 ≤ j < b, 0 ≤ k < a!, we set π i,j,k := σ k (S i,j 0 ) . . . σ k (S i,j b-1 ).

The π i,j,k form a collection of a! n a permutations of [n]. The interesting property is that, for ℓ fixed, the set of σ k (S i,j ℓ ) is exactly the set of words in [n] a without repetition, simply because, for ℓ fixed, the set of S i,j ℓ is exactly the set of a-subsets of [n], as mentioned above. In particular, for ℓ fixed, the σ k (S i,j ℓ ) are pairwise distinct. Let w = w 1 w 2 . . . w p be a shortest word containing all the permutations π i,j,k as subsequences. We know that |w| ≤ λ(n) ≤ n 2 . Let γ i,j,k := γ i,j,k 0 γ i,j,k 1 . . . γ i,j,k b be the profile of π i,j,k , defined recursively as follows: γ i,j,k 0 := 0 and, for all 0 ≤ ℓ < b, γ i,j,k ℓ+1 is the smallest integer such that σ k (S i,j ℓ ) is a subsequence of the factor

w [γ i,j,k ℓ +1,γ i,j,k ℓ+1 ] .
Since γ i,j,k 0 = 0 and 1 ≤ γ i,j,k ℓ ≤ n 2 for all 1 ≤ ℓ ≤ b, there are at most n 2b possible profiles. Thus there exist at least s ≥ a! n a n 2b permutations π i,j,k with the same profile. Let π i 1 ,j 1 ,k 1 , . . . , π is,js,ks be these permutations, and let γ = (γ 0 , γ 1 , . . . , γ b ) be their profile. For all 0 ≤ ℓ < b, let

w ℓ := w [γ ℓ +1,γ ℓ+1 ] .
By construction, w ℓ contains, as subsequences, each of σ k 1 (S i 1 ,j 1 ℓ ), . . . , σ ks (S is,js ℓ ). Since these s elements of [n] a are pairwise distinct (because, for fixed ℓ, all the σ k (S i,j ℓ ) are pairwise distinct), this means that w ℓ contains at least s distinct subsequences of length a, and thus

|w ℓ | a ≥ s.
We deduce

|w ℓ | a a! ≥ |w ℓ | a ≥ s ≥ a! n a n 2b ≥ (n -a) a n 2b
and thus

|w ℓ | a ≥ a! (n -a) a n 2b ≥ a e a (n -a) a n 2b ≥ a(n -a) en 2b a a . Consequently, |w| ≥ 0≤ℓ<b |w ℓ | ≥ b • a(n -a) en 2b a = n -2b a n(n -a) e .
We are now in position to prove that there is a subexponential set of permutations that requires a quadratic length to be represented in a supersequence. This is a quantitative version of Theorem 3 stated in the introduction. Theorem 9. For any ε > 0 and n sufficiently large, there is a set of at most n n 1 2 +ε permutations of [n] such that any word containing all these permutations as subsequences is of length at least ( 1 eε)n 2 .

Proof. Let ε > 0 be arbitrarily small. Let n be a positive integer, a := ⌊n First,

n -2ba -1 → 1 as n → ∞. Second, since m = n + o(n), we have m(m -a) = n 2 -o(n 2 ).
From these two observations we deduce that if n is at least some constant n 0 that only depends on ε then

|w| ≥ (1 -ε) n 2 e ≥ ( 1 e -ε)n 2 .
For each i ∈ [ℓ], let πi be a permutation of [n] that contains π i as a subsequence. Then any word w containing all the πi also contains all the π i , so that | w| ≥ ( 1 eε)n 2 if n ≥ n 0 . Implementing the "packing" strategy described above, we obtain a monotone network with quadratic fixing length. This is a quantitative version of Theorem 2 stated in the introduction.

Theorem 10. For any ε > 0 and n sufficiently large, there exists

f ∈ F M (n) such that λ(f ) ≥ 1 e -ε n 2 .
Proof. Let ε > 0, let n be a positive integer, and let m be the largest integer such that

m m 1 2 +δ ≤ n -m ⌊ n-m 2 ⌋ , (2)
with δ = ε/2. Then m = (1o( 1))n and thus if n is large enough, then

m 2 > n 2 (1 -δ)
and, according to Theorem 9, there exists a collection π 1 , . . . , π p of p ≤ m m 1 2 +δ permutations of [m] such that any word containing all these permutations as subsequences is of length at least ( 1 eδ)m 2 . Let us regard these p permutations as m-vertex paths, and let h 1 , . . . , h p be the corresponding path networks. In other words, writing

π k = π k 1 π k 2 . . . π k n , we have, for all x ∈ {0, 1} m , h k π k 1 (x) = 1 and h k π k l (x) = x π k l-1 for all 1 < l ≤ m.
According to Lemma 2, if a word w fixes all the networks h k then it contains all the permutations π k as subsequences, and thus |w| ≥ ( 1 eδ)m 2 . Let r := nm. Then according to (2) there is a surjection φ from the set of states in {0, 1} r with Hamming weight ⌊ r 2 ⌋ to [p]. By identifying {0, 1} n with {0, 1} m × {0, 1} r , we then define the n-component network f as follows:

f (x, y) =      (1, y) if w H (y) > ⌊r/2⌋, (h φ(y) (x), y) if w H (y) = ⌊r/2⌋, (0, y) if w H (y) < ⌊r/2⌋.
Let us check that f is monotone. Suppose (x, y) ≤ (x ′ , y ′ ). If w H (y) < w H (y ′ ) we easily check that f (x, y) ≤ f (x ′ , y ′ ). Otherwise, we have y = y ′ and thus φ(y) = φ(y ′ ) = k for some k ∈ [p], and, since h k is monotone, we obtain f (x, y)

= (h k (x), y) ≤ (h k (x ′ ), y ′ ) = f (x ′ , y ′ ).
Let w be any shortest word fixing f . Then it is clear that fixes

h k for all k ∈ [p]. Thus |w| ≥ ( 1 e -δ)m 2 > ( 1 e -δ)(1 -δ)n 2 > 1 e -ε n 2 .
A similar argument works for increasing networks as well.

Proof of Theorem 7. We use the same setup as the proof of Theorem 10, excepted that the mcomponent networks h k and the n-component network f are defined as follows. Let k ∈ [p]. We set y k,0 := 0 and y k,l := y k,l-1 + e π k l for all l ∈ [m]. We then define the m-component increasing network h k by h k (x) := y k,l+1 if x = y k,l and 1 ≤ l < m, x otherwise.

Then, as already said in the proof of Proposition 3, a word fixes h k if and only if it contains π k as subsequence. Thus if a word w fixes all the networks h k then it contains all the permutations π k as subsequences, and thus |w| ≥ ( 1 eδ)m 2 . Next, we define the n-component network f as follows:

f (x, y) =      (1, y) if w H (y) > ⌊r/2⌋, (h φ(y) (x), y) if w H (y) = ⌊r/2⌋, (1, y) if w H (y) < ⌊r/2⌋.
We easily check that f is increasing and that w fixes f if and only if it fixes h k for all k ∈ [p].

We then deduce as above that any word fixing f is of length at least 1 eε n 2 .

Cubic word fixing all monotone networks

What about the fixing length λ M (n) of the whole family F M (n) of n-component monotone networks? We have shown that some members have quadratic fixing length, namely ( 1 eε)n 2 , and thus, obviously, λ M (n) ≥ ( 1 eε)n 2 . But we can say something slightly better: we have shown that the family of path networks F P (n) has fixing length λ(n), and since

F P (n) ⊆ F M (n) we obtain: λ M (n) ≥ λ(n).
We have no better lower-bound. Maybe the family of n-component conjunctive networks whose interactions graphs are disjoint union of cycles has fixing length greater than λ(n) (this family can be equivalently defined as the set of monotone isometries of the hypercube Q n ).

Concerning upper-bounds, we show below that λ M (n) is at most cubic, and this is the best upper-bound we have on the maximum fixing length of a member of F M (n). For that we construct inductively a word W n of cubic length that fixes F M (n). Definition 8 (Fixing word for monotone networks). Let W 1 := 1 and, for n ≥ 1, let

W n+1 := W n , n + 1, ω n ,
where ω n is a shortest n-complete word (of length λ(n)).

λ M (n) ≤ n + n-1 i=1 λ(i) ≤ n 3 3 - 3n 2 2 + 37n 6 .
This is a quantitative version of Theorem 4 stated in the introduction. The main idea is that, once the components 1 to n -1 have been fixed, a monotone network behaves just like an increasing (or decreasing) network. Therefore, the network can be fixed in quadratic time from that point. Lemma 6. Let f be an n-component monotone network. If x ≤ f (x) then f u (x) ≤ f uv (x) for any words u and v. Similarly, if x ≥ f (x) then f u (x) ≥ f uv (x) for any words u and v.

Proof. Suppose that x ≤ f (x) and let i ∈ [n]. Then x ≤ f i (x) so f i i (x) = f i (x) ≤ f i (f i (x)) and f i j (x) = x j ≤ f j (x) ≤ f j (f i (x)) for all j = i. Thus x ≤ f (x) implies f i (x) ≤ f (f i (x)) for every i ∈ [n]. We deduce that, for any word w = w 1 w 2 . . . w k , x ≤ f w 1 (x) ≤ f w 1 w 2 (x) ≤ • • • ≤ f w 1 w 2 .
..w k (x), and this clearly implies the lemma.

Proof of Theorem 11. The proof is by induction on n. This is clear for n = 1, so suppose it holds for n -1. Fix an initial state x ∈ {0, 1} n and, for every z ∈ {0, 1} n , let z -n := (z 1 , . . . , z n-1 ) and h(z -n ) := f (z -n , x n ) -n . Then h is a monotone network with n -1 components. Let y := f W n-1 (x). Since the letter n does not appear in W n-1 , we have y -n = h W n-1 (x -n ) and thus, by induction hypothesis, y -n is a fixed point of h. Hence,

f (y) = f (y -n , y n ) = (h(y -n ), f n (y)) = (y -n , f n (y)).
We deduce that either y is a fixed point of f , and in that case y = f n,ω n-1 (y) = f W n (x) so we are done, or f (y) = y + e n . Suppose that f (y) = y + e n with y n = 0, and remark that f (y) = f n (y). Setting y ′ := f (y) we have y ≤ y ′ , thus y ′ ≤ f (y ′ ), and since y ′ n = 1, we deduce that ω n-1 contains all the permutations of {i : y ′ i = 0}. Hence, according to Lemma 6 and Lemma 4,

f ω n-1 (y ′ ) = f ω n-1 (f n (y)) = f n,ω n-1 (y) = f W n (x)
is a fixed point of f . If f (y) = y + e n with y n = 1 the proof is similar.

4 Refinements and extensions

Conjunctive networks

We now determine the maximum fixing length over all n-component conjunctive networks.

Clearly the maximum is equal to one if n = 1 and to two if n = 2. To settle the case n ≥ 3 and characterize the extremal networks, we need additional definitions. Let C n denote the n-vertex cycle (there is an edge from i to i + 1 for all 1 ≤ i < n, and an edge from n to 1). We denote by C • n the graph obtained from C n by adding an edge (i, i) for all i ∈ [n]; these additional edges are called loops. A strong component in a graph G is initial if there is no edge from a vertex outside the component to a vertex inside the component.

Theorem 12. For all n ≥ 3 and f ∈ F C (n), λ(f ) ≤ 2n -2,
with equality if and only if the interaction graph of f is isomorphic to C • n . Proof. Suppose that n ≥ 2. Let G be a graph on [n], and let f be the conjunctive network on G. A spanning in-tree S in G rooted at i is a spanning connected subgraph of G such that all vertices j = i have out-degree one in S, and i has out-degree zero in S. A spanning out-tree is defined similarly. It is clear that if G is strong, then for any vertex i there exists a spanning in-tree of G rooted at i (and similarly for out-trees). A vertex l with in-degree zero in a spanning in-tree S is referred to as a leaf of S. We denote the maximum number of leaves of a spanning in-tree of G as φ(G).

We first prove the theorem when G is strong. In that case, f has exactly two fixed points:

0 and 1. Claim 1. If G is strong, then λ(f ) ≤ 2n -φ(G) -1.
Proof of Claim 1. Let S be a spanning in-tree of G with φ := φ(G) leaves. Let i 1 i 2 . . . i n be a topological sort of S. The root of S is thus i n , and its leaves are i 1 . . . i φ . Let T be a spanning out-tree with the same root as S. Let j 1 j 2 . . . j n be a topological sort of T , so that its root is j 1 = i n . We claim that the word w := i φ+1 . . . i n j 2 . . . j n of length 2nφ -1 fixes f . Let u := i φ+1 . . . i n and x ∈ {0, 1} n . We set x φ := x and x k := f i k (x k-1 ) for φ < k ≤ n. We claim that if x n in = 1, then f u (x) = x n = 1. For otherwise, suppose x n in = 1 and x n i k = 0 for some φ ≤ k < n. Let i r 1 i r 2 . . . i rp be the path from i k = i r 1 to i rp = i n in S. This path follows the topological order, that is, r 1 < r 2 < • • • < r p . Clearly, for all 1 ≤ q < p we have

x n ir q = 0 ⇒ x rq ir q = 0 ⇒ x r q+1 -1 ir q = 0 ⇒ x r q+1 ir q+1 = 0 ⇒ x n ir q+1 = 0.
Since x n i k = 0 we deduce that x n in = 0, which is the desired contradiction. Hence, if

x n in = 1 then f u (x) = 1 and thus f w (x) = 1. Otherwise x n in = 0 and it is easily shown by induction on 2 ≤ k ≤ n that f j 2 ...j k j k (x n ) = 0, thus f j 2 ...jn (x n ) = f w (x) = 0.
We say that G is a cycle with loops if G is isomorphic to a graph obtained from C n by adding some loops.

Claim 2. If G is strong and not a cycle with loops, then φ(G) ≥ 2 and hence λ(f ) ≤ 2n -3.

Proof of Claim 2. Since adding loops to a graph maintains the value of φ, without loss, suppose that G has no loops. Since G is strong but not a cycle, there exists a vertex i in G with in-degree d ≥ 2. We can then construct a spanning in-tree rooted at i with at least d leaves as follows. For all 0 ≤ k < n, let U k be the set of vertices j such that d G (j, i) = k (i.e. k is the minimum length of a path from j to i in G). Then U 0 only contains i, U 1 is the set of in-neighbors of i, and

U 0 ∪ U 1 ∪ • • • ∪ U n-1 = [n]
. For any j ∈ U k with 1 ≤ k < n, let j ′ be any out-neighbor of j in U k-1 . Then the edges (j, j ′ ) for all j = i form a spanning in-tree rooted at i with at least

|U 1 | = d ≥ 2 leaves.
Suppose that G is a cycle with loops, and let L be the set of vertices with a loop. Given l, l ′ ∈ L, we say that l ′ is the successor of l if none of the internal vertices on the path from l to l ′ belong to L. The maximum distance in G from a vertex in L to its successor is denoted as d(G). By convention, we let d(G)

:= n if |L| = 0 or |L| = 1. Claim 3. If G is a cycle with loops, then λ(f ) ≤ 2n-d(G)-1. Therefore, if G is not isomorphic to C • n , then λ(f ) ≤ 2n -3.
Proof of Claim 3. Without loss, we assume that G is obtained from C n by adding some loops. Let us first settle the case where |L| ≤ 1. If L is empty, then it is easy to see that 1, 2, . . . , n -1 fixes f . If L is a singleton we may assume, without loss, that n is the only vertex with a loop, and then the same strategy works: 1, 2, . . . , n -1 fixes f . Henceforth, we assume |L| ≥ 2. Without loss, suppose that n and d := d(G) both belong to L and that d is the successor of n. Then we claim that the word w := d + 1, d + 2, . . . , n, 1, . . . , d, d + 1, . . . , n -1 fixes f . Let x ∈ {0, 1} n . Firstly, suppose x l = 0 for some l ∈ L; we note that d ≤ l ≤ n. First of all, the value of x l will remain zero: f d+1,...,l l (x) = 0. Afterwards, the 0 will propagate through the cycle: f d+1,...,l,...,l-1 (x) = 0. Secondly, if x l = 1 for all l ∈ L, then it is easy to show that f w (x) = 1.

The two previous claims show that if G is strong then λ(f ) ≤ 2n -2, with a strict inequality when G is not isomorphic to C • n . The lower bound below thus settles the strong case.

Claim 4. If G is isomorphic to C • n then λ(f ) ≥ 2n -2.
Proof of Claim 4. For all 1 ≤ i ≤ n and 0 ≤ k < n, we denote by i k the vertex at distance k from i in G, and we denote by x i,k the state such that x i,k j = 0 if and only if the distance between i and j is at most k. Thus x i,0 = 1 + e i and x i,n-1 = 0. Furthermore, for all 0 ≤ k < n -1,

f (x i,k ) = x i,k + e i k+1 = x i,k+1 .
We deduce that if w = w 1 w 2 . . . w p fixes f , then f w (x i,0 ) = 0 and, necessarily, i 1 i 2 . . . i n-1 is a subsequence of w for all i. Let i be the last index to appear in w, then i = w q for some q ≥ n; then the word i 1 i 2 . . . i n-1 begins in position q of w and does not end before position q + n -2 ≥ 2n -2. Hence λ(f ) ≥ 2n -2.

It remains to settle the non-strong case. We first establish an upper-bound on λ(f ) that depends on the decomposition of G in strong components. Let ψ 1 (G) be the number of initial strong components containing a single vertex without a loop, let ψ 2 (G) be the number of initial strong components containing a single vertex with a loop, let ψ 3 (G) be the number of initial strong components with at least two vertices, and let ψ 4 (G) be the number of non-initial strong components.

Claim 5. λ(f ) ≤ 2n -ψ 1 (G) -2ψ 2 (G) -2ψ 3 (G) -ψ 4 (G).
Proof of Claim 5. Let I 1 , . . . , I k denote the strong components of G in the topological order, and let n l := |I l |. We then consider a word w l that fixes the conjunctive network on G[I l ].

for any word u we have f n,u (x) = (h u (x 1 , . . . , x n-1 ), 1). Thus, let u be the word of length at most 2(n -1) -2 fixing h from the proof of Claim 1 (if H is not a cycle with loops) or Claim 3 (otherwise). Then w = n, u is a word of length at most 2n -3 fixing f . This completes the proof of the theorem. Remark 4. We can strengthen the upper bound for specific graphs. In particular, if G is undirected and connected, then there are lower bounds on the maximum number of leaves of a spanning tree for G (see [6] for instance).

Monotone networks with a given interaction graph

We now refine Theorem 11 for F M (G), the family of monotone networks whose interaction graph is contained in a graph G. Recall that the transversal number of G is the minimum size of a subset I of vertices in G such that G \ I is acyclic. The main result is that, for fixed transversal number, the fixing length of F M (G) is linear in the number of vertices. The statement needs additional definitions.

Definition 9 ((i, α)-complete words). For i ≥ 0 and α ≥ 0, a word on [α + i] is (i, α)complete if it contains, as subsequences, all the permutations j 1 , . . . , j α+i of [α + i] such that, for all 1 ≤ ℓ < α + i, if j ℓ , j ℓ+1 ∈ [α] then j ℓ < j ℓ+1 . We denote by λ(i, α) the length of a shortest (i, α)-complete word.

Thus λ(0, α) = α. Furthermore, for > 0, we have λ(i, α) ≤ λ(α + i), with equality if and only if α ∈ {0, 1}. In a graph G, a 1-feedback vertex set is a set of vertices I such that all the cycles of G \ I are loops (i.e. cycles of length one). The 1-transversal number of G is the minimum size of a 1-feedback vertex set. Clearly, if G is an n-vertex graph with transversal number τ and 1-transversal number τ 1 , then τ 1 ≤ τ and τ 1 < n.

The following is a quantitative version of Theorem 5 stated in the introduction.

Theorem 13. Let G be a graph on [n] with 1-transversal number τ 1 . We have

λ M (G) ≤ n + τ 1 i=1 λ(i -1, n -τ 1 ) ≤ τ 2 1 2 + 3τ 1 2 + 1 n.
Remark 5. Let K n be the complete directed graph on [n] (with n 2 edges). Since the 1-transversal number of K n is n -1, we have the following, which proves that Theorem 13 indeed contains Theorem 11:

λ M (n) = λ M (K n ) ≤ n + n-1 i=1 λ(i -1, 1) = n + n-1 i=1 λ(i).
Proof of Theorem 13. Let G be a graph on [n] with 1-transversal number τ 1 and let α = nτ 1 . Let ]α, n] = {α + 1, . . . , n}. Without loss, we assume that ]α, n] is a 1-feedback vertex set. We also assume that 12 . . . α is the topological order of G[{1, . . . , α}]; this order exists, since all the cycles of G[{1, . . . , α}] have length one. For all 1 ≤ i ≤ n, let R i be the set of vertices reachable from i in G[{1, . . . , i}]. Thus R i = {i} if i ≤ α, and R i ⊆ [i] otherwise. Let P i be the set of enumerations j 1 j 2 . . . j k of R i \ {i} such that, for all 1 ≤ ℓ < k, if j ℓ , j ℓ+1 ∈ [α] then j ℓ < j ℓ+1 . Let ω i be a shortest word containing, as subsequences, all the enumerations contained in P i . Let w i := i, ω i and

W := w 1 , . . . , w n . If i ∈ [α], then R i = {i}, thus ω i = ǫ. Furthermore, if i ∈]α, n], then R i ⊆ [i] and we deduce that |ω i | ≤ λ(i -α -1, α). Thus |W | ≤ n + τ 1 i=1 λ(i -1, n -τ 1 ).
and such that, for all 1 ≤ ℓ ≤ d, if s ℓ , s ℓ+1 ∈ [α] then s ℓ < s ℓ+1 . In this way, s 1 = j 1 = i, and s 2 , . . . , s d+1 is in P i . Hence, by definition, s 2 . . . s d+1 is a subsequence of ω i , and thus s 1 s 2 . . . s d+1 is a subsequence of w i . Therefore,

y p j = y p j d+1 = f ω i j d+1 (y) ≥ f s 1 s 2 ...s d s d+1 j d+1 (y) ≥ f j 1 j 2 ...j d j d+1 j d+1
(y) = f j d+1 (y p ) = f j (x p ), a contradiction. Thus W i fixes f , and thus the whole family F M (G i ). Therefore, W fixes F M (G) and it remains to prove that |W | ≤ ( τ 2 1 2 + 3τ 1 2 + 1)n. This follows from the proposition below and an easy computation. Proposition 4. For all i ≥ 0 and α ≥ 0 we have λ(i, α) ≤ i 2 + iα + α.

Proof. Let β := α + i and consider the word w := i • (12 . . . β), 12 . . . α, resulting from the concatenation of i copies of 12 . . . β and the addition of the suffix 12 . . . α. Let u = j 1 j 2 . . . j β be a permutation of [β] such that, for all 1 ≤ ℓ < β, if j ℓ , j ℓ+1 ∈ [α] then j ℓ < j ℓ+1 . We will prove that w is (i, α)-complete and, for that, it is sufficient to prove that u is contained in w. Let j k 1 . . . j k i be the longuest subsequence of u with letters in

[β] \ [α]. Then, j 1 . . . j k 1 is a subsequence of (1 . . . β) = w 1 . . . w β j k 1 +1 . . . j k 2 is a subsequence of (1 . . . β) = w β+1 . . . w 2β , . . . j k i-1 +1 . . . j k i is a subsequence of (1 . . . β) = w (i-1)β+1 . . . w iβ , and
j k i +1 . . . j β is a subsequence of (1 . . . α) = w iβ+1 . . . w iβ+α .
Thus u is a subsequence of w. Since |w| = i 2 + iα + α, this proves the proposition.

Balanced networks

We now consider a family of networks (namely, balanced networks) which is more general than monotone networks. Those are defined by their signed interaction graph, hence we review basic definitions and properties of signed graphs first.

A signed graph is a couple (G, σ) where G is a graph, and σ : E → {-1, 0, 1} is an edge labelling function, that gives a (positive, negative or null) sign to each edge of G. The sign of a cycle in (G, σ) is the product of the signs of its edges, and (G, σ) is balanced if all the cycles are positive. The signed interaction graph of an n-component network f is the signed graph (G, σ) where G is the interaction graph of f and where σ is defined for each edge of G from j to i as follows: σ(ji) :=    1 if f i (x) ≤ f i (x + e j ) for all x ∈ {0, 1} n with x j = 0, -1 if f i (x) ≥ f i (x + e j ) for all x ∈ {0, 1} n with x j = 0, 0 otherwise.

Definition 10 (Balanced networks). An network is balanced if its signed interaction graph is balanced. The family of n-component balanced networks is denoted F B (n).

Clearly, a network is monotone if and only if all the edges of its signed interaction graph are positive. Thus every monotone network is balanced. Conversely, a balanced network can be "decomposed" into monotone networks by considering the decomposition of its interaction graph into strong components, as formally described below.

Given z ∈ {0, 1} n , the z-switch of f is the n-component network f ′ defined by f ′ (x) = f (x + z) + z for all x ∈ {0, 1} n . For instance, the 1-switch of f is the dual of f . If f ′ is the z-switch of f , then f and f ′ have the same interaction graph G, but their signed interaction graph (G, σ) and (G, σ ′ ) may differ, since σ ′ (ji) = σ(ji) for all edge ji with z j = z i but σ ′ (ji) = -σ(ji) for all edge ji with z j = z i . Clearly, if f ′ is the z-switch of f , then f is the z-switch of f ′ , and we then say that f and f ′ are switch-equivalent.

Networks

F max f ∈F λ(f ) λ(F) Acyclic F A (n) = n = λ(n) ∼ n 2 Path F P (n) = n = λ(n) ∼ n 2 Increasing F I (n) ≥ ( 1 e -ε)n 2 = λ(n) ∼ n 2 Monotone F M (n) ≥ ( 1 e -ε)n 2 ≤ 1 3 n 3 Conjunctive F C (n) = 2n -2 - G-monotone F M (G) - ≤ 2τ 2 n + n Balanced F B (n) - ≤ 1 9 n 4
Table 1: Summary of results

Thus, in any case, there exists a subset I of three vertices fixed by w. Suppose, without loss, that I = {n -2, n -1, n}. Then, let h be the (n -3)-component network defined by h(y) := (f 1 (y, z)), . . . , f n-3 (y, z)) with z := (f w n-2 (x), f w n-1 (x), f w n (x))

for all y ∈ {0, 1} n-3 . Then h is balanced, and thus, by induction, Xn-3 fixes h. Consequently, w fixes I, and then Xn-3 fixes [n] \ I. Since Xn = w, Xn-3 , we deduce that Xn fixes f .

Conclusion

In this paper, we have considered the asynchronous automaton associated with a Boolean network and used it to introduce the family of fixable networks (which is huge by Theorem 1). We have then introduced the fixing length λ(f ) of a fixable network f and the fixing length λ(F) of a family F of fixable networks. We have then identified several families with polynomial fixing lengths, using properties concerning complete words. Our results are summarised in Table 1. A dash means that we did not find any nontrivial result for the given entry.

Our main results concern the family F M (n) of n-component monotone networks. In particular, we have proved that the fixing length of F M (n) is at most cubic and that the maximum fixing length of network in F M (n) is at least quadratic. The main open question raised by these results is the following: is there an asymptotic gap between the fixing length of F M (n) and the maximum fixing length of network in F M (n)? A positive answer is not obvious since, for instance, for the family F I (n) of n-component increasing networks, which is doubly exponential in n, we have proved the following: both the fixing length of F I (n) and the maximum fixing length of network in F I (n) are quadratic.

There are some connections between fixability and synchronization, since a network with a unique fixed point is fixable if and only if its asynchronous automaton is synchronizing. It would be interesting to study synchronization in Boolean networks more specifically. In particular, it would be interesting to study the famous Černý conjecture, stated in the general framework of deterministic finite automata, in the specific setting of Boolean networks, that is, for the class of asynchronous automata associated with Boolean networks.

Figure 1 :

 1 Figure 1: (a) A network f given under two different forms (a table and logical formulas). (b) The interaction graph of f . (c) The asynchronous automaton of f .

  we shall sometimes use the notation w S = w i 1 w i 2 . . . w iq ; if S = ∅, then w S := ǫ, where ǫ is the empty word. Any such w S is a subsequence of w. Moreover, for any integers a, b ∈ [p] we set [a, b] = {a, a + 1, . . . , b} and hence w [a,b] := w a , . . . , w b if a ≤ b and w [a,b] := ǫ if a > b. Any such w [a,b] is a factor of w.

Theorem 8 (Lemma 5 .

 85 Baranyai). If a divides n, then there exists a collection of n a a n partitions of [n] into n a sets of size a such that each a-subset of [n] appears in exactly one partition. Let a and b be positive integers, and n = ab. There exists a set of a! n a ≤ n a permutations of [n] such any word containing all these permutations as subsequences is of length at least n -2b a n(na) e .

1 2 +ε ⌋, b := ⌊n 1 2

 11 -ε ⌋ and m := ab. By the preceding lemma, there exist s := a! m a ≤ m a ≤ n n 1 2 +ε permutations π 1 , . . . , π s of [m] such that if w is any word containing all the π i as subsequences then |w| ≥ m -2b a m(ma) e ≥ n -2b a m(ma) e .

Theorem 11 .

 11 The word W n fixes F M (n) for every n ≥ 1. Therefore,

Acknowledgment This work is partially supported by: FONDECYT project 1151265, Chile; CONICYT / PIA project AFB 170001, Chile; Labex UCN@Sophia, Université Côte d'Azur, France; CNRS project PICS06718; project STIC AmSud CoDANet 19-STIC-03 (Campus France 43478PD), France; and Young Researcher project ANR-18-CE40-0002-01 "FANs", France.

Let us now prove that W fixes F M (G). For all i ∈ [n], let W i := w 1 , . . . , w i and G i := G[{1, . . . , i}].

We prove, by induction on i, that W i fixes F M (G i ). This is obvious for i = 1. Assume that i ≥ 2. Let f ∈ F M (G i ) and x ∈ {0, 1} i . We write x = (x -i , x i ) and set

In this way, f ′ ∈ F M (G i-1 ). Let y := f W i (x).

Since y -i = f ′W i-1 (x -i ), by induction hypothesis, y -i is a fixed point of f ′ . We deduce that either y is a fixed point of f , and in that case

is a fixed point of f , and we are done, or f (y) = y + e i .

So it remains to suppose that f (y) = y + e i and to prove that f w i (y) is a fixed point. We consider the case where y ≤ f (y), the other case being similar. Let

for all 1 ≤ k ≤ p, with p = |w i |. According to Lemma 6 we have

Let us prove that y p = f w i (y) is a fixed point of f . Let j 1 j 2 . . . j d be the ordered sequence of coordinates that turned from 0 to 1 during the sequence y 0 , y 1 , . . . , y p . In this way, d is the Hamming distance between y 0 and y p , and j 1 = i = w i 1 . Furthermore,

Suppose, for the sake of contradiction, that f j (y p ) = y p j for some 1 ≤ j ≤ i. Since y p ≤ f (y p ), we must have y p j < f j (y p ). Thus y k j = 0 for all 0 ≤ k ≤ p. Hence, j does not appear in the sequence j 1 j 2 . . . j d . Let

and let us prove that {j 1 , . . . , j d , j d+1 } ⊆ R i .

Since j 1 = i we have j 1 ∈ R i . We now prove j k ∈ R i with k = 1. Let y q be the smallest index 0 ≤ q ≤ p such that y q j k < f j k (y q ). Since k = 1, j k = i, and since f (y) = y + e i , we deduce that q > 1. Then, by the choice of q, we have y q-1 j k = f j k (y q-1 ) and thus y q-1 j k = y q j k . Hence, f j k (y q-1 ) < f j k (y q ). Thus G has an edge from w q-1 to j k , since w q-1 is the unique component that differs between y q-1 and y q . Clearly, w q-1 = j ℓ for some 1 ≤ ℓ < k. Thus, we have proved that for all j k with 1 < k ≤ d + 1, there exists 1 ≤ ℓ < k such that j ℓ j k is an edge of G. We deduce that all the j k with 1 < k ≤ d + 1 are reachable from j 1 = i. This proves [START_REF] Ahlswede | Network information flow[END_REF].

Furthermore, for all 1 ≤ ℓ ≤ d, if j ℓ , j ℓ+1 ∈ [α] and j ℓ > j ℓ+1 , then f j 1 j 2 ...j ℓ j ℓ+1 ...j d+1 (y) ≤ f j 1 j 2 ...j ℓ+1 j ℓ ...j d+1 (y) since G has no edge from j ℓ to j ℓ+1 . Thus, by applying such switches several times, we can reorder the sequence j 1 j 2 . . . j d+1 into a sequence s 1 s 2 . . . s d+1 such that

Proposition 5 ([24]). Let f be a network with a strong interaction graph. Then f is balanced if and only if f is switch-equivalent to a monotone network.

The proposition above have immediate consequences on the existence of short words fixing the family of balanced networks. Clearly, if f and f ′ are switch-equivalent, then any word fixing f fixes f ′ as well. Therefore, let W n be a word fixing F M (n) and consider n • W n (the word W n repeated n times). Let f ∈ F B (n) and denote the strong components of its interaction graph as I 1 , . . . , I k (k ≤ n). Since f restricted to each strong component is switch-equivalent to a monotone network, W n fixes each strong component individually, and thus l • W n fixes the first l strong components. In particular, n • W n fixes f . Thus, by Theorem 11, there exists (for sufficiently large n) a word of length at most n 4 /3 fixing F B (n).

The following theorem refines (and gives a formal proof of) the result above. More precisely, let n = 3q + r with 0 ≤ r < 3, let s be the word s := 12 . . . n and let W n be any word fixing F M (n) of minimal length. Then define the word

Theorem 14. The word W n fixes F B (n) for every n ≥ 1. Therefore,

Proof. Let n = 3q + r, with 0 ≤ r < 3, and let X n be a word fixing F M (n). We prove, more generally, that Xn := (q

and let G be the interaction graph of f . The main idea of the proof is that each factor w := ssX n of Xn fixes at least three new vertices of G. Therefore, q • w fixes at least 3q = nr vertices, and finally r • s fixes the last r vertices if need be.

We formally proceed by induction on n. If n = 1 then s = 1 fixes f , and if n = 2, it is easy to check that ss = 1212 fixes f . So we assume that n ≥ 3. We say that a prefix u of W n fixes a set of vertices I ⊆ [n] if, for any other prefix v longer than u, we have f u i (x) = f v i (x) for all i ∈ I. We consider three cases, and in each case, we select a subset I of vertices of size at least three fixed by w.

1. G has an initial strong component I with at least three vertices. Then let I be this initial strong component, and let g be the restriction of f on I. Since g is switch-equivalent to a monotone network, X n fixes g, and thus w fixes I.

2. G has an initial strong component with two vertices, say I 1 = {i, j} with i < j. Again, let g be the restriction of f on I 1 . The occurrences of i and j in ss = 12 . . . n12 . . . , n are ijij, in that order; this contains iji, which fixes g. Therefore, ss fixes I 1 . Suppose, without loss, that i = n -1 and j = n, and let h be the (n -2)-component network defined by h(y) := (f 1 (y, z)), . . . , f n-2 (y, z)) with z := (f ss n-1 (x), f ss n (x)) for all y ∈ {0, 1} n-2 . Then h is balanced and, by a reasoning similar to the first case, X n fixes an initial strong component I 2 of the interaction graph of h. Thus, w fixes I := I 1 ∪I 2 .