Mustapha Hamdi

Gaurav Sharma

Antoine Ferreira
email: antoine.ferreira@ensi-bourges.fr

Constantinos Mavroidis

PROTOTYPING BIO-NANOROBOTS USING MOLECULAR DYNAMIC SIMULATION

This paper presents a molecular mechanics study using a molecular dynamics software (NAMD) coupled to virtual reality techniques for intuitive bio-nanorobotic prototyping. Using molecular dynamic simulations the operator can design, characterize and prototype the behavior of bio-nanorobotic components and structures. The main novelty of the proposed simulations is based on the characterization of stiffness performances of passive joints-based deca-alanine protein molecule and active joints-based viral protein motor (VPL) in their native environment. Their use as elementary bio-nanorobotic components are also simulated and the results discussed.

INTRODUCTION

Bio-nanorobotics is an emerging area of scientific and technological opportunity. It is a new and rapidly growing interdisciplinary field addressing the assembly, construction and utilization of biomolecular devices based on nanoscale principles and/or dimensions. Research and product development at the interface of physical sciences and biology as applied to this area require multi-skilled teams and often novel technical approaches for material synthesis, characterization and applications. In this way proteins and DNA could act as motors, mechanical joints, transmission elements, or sensors. If all of these different components were assembled together they can form bio-nanorobots with multiple degrees-of-freedom that are able to apply forces and manipulate objects in the nanoscale world. These motors, which are called biomolecular motors, have attracted a great deal of attention recently because they have high efficiency, they could be self-replicating, and hence cheaper in mass usage, and they are readily available in nature. A number of enzymes such as kinesin [START_REF] Block | Kinesin what gives?[END_REF], RNA polymerase [START_REF] Wang | Force and velocity measurement for single molecules of RNA polymerase[END_REF], myosin [START_REF] Kitamura | A single myosin head moves along an actin filament with rectangular steps of 5.3nm[END_REF], dynein [START_REF] Shingyoji | Dynein arms are oscillating force generators[END_REF], adenosine triphosphate (ATP) synthase [START_REF] Montegano | Constructing nanomechanical devices powered by biomolecular motors[END_REF], viral protein linear (VPL) motor [START_REF] Dubey | Viral Protein Linear (VPL) Nano-Actuators[END_REF] and DNA can function as nanoscale linear, oscillatory or rotary biological motors. In addition, there are compliance devices such as springlike proteins called fibronectin [START_REF] Erickson | Streching single protein molecules: Titin os a wired spring[END_REF] and vorticellids [START_REF] Mahadevan | Mobility powered by supramolecular springs and ratchets[END_REF], as well as synthetic contractile plant polymers [START_REF] Knoblauch | ATP-independent contractile proteins from plants[END_REF] which can act as compliant joints in biomolecular robotic systems. The idea is to use biomolecular motors as the actuators of such bio-nanorobots, where the structural elements are carbon nanotubes, while the joints are formed by appropriately designed DNA elements. Figure 1a motors, at the origin of the bio-nanorobot actuation.

Going beyond a knowledge of the forces derived from these nanomanipulation experiments requires a contribution from molecular dynamic simulations to be able to understand the bio-nanomechanics of proteins and develop dynamic and kinematic models to study their performances. The ability to visualize the atom-to-atom interaction in real-time and see the results in a fully immersive 3-D environment is an additional feature of such simulations [START_REF] Haase | VR techniques for the investigation of molecule data[END_REF][START_REF] Drees | Highly Immersive Molecular Modeling (HIMM): an architecture for the integration of molecular modeling and virtual reality[END_REF][START_REF]Collaborative Visualization and Simulation Environment (COVISE)[END_REF][START_REF] Humphrey | VMD:Visual Molecular Dynamics[END_REF][START_REF] Ferreira | New trends in Bio-Nanorobotics using Virtual Reality technologies[END_REF]. In this work, we consider a mechanical molecular study of unfolding proteins acting M.Hamdi, G.Sharma, A.Ferreira, D.Mavroidis Prototyping Bio-Nanorobots Using Molecular Dynamic Simulation as passive or active joints in bio-nanorobotic systems. We therefore decided to begin our investigations by simulating the forces involved under various external mechanical stress (stretching, contraction, shearing, bending) to predict the type of force spectra, reversibility, degrees of freedom and irreversible work that may be expected from single-molecule protein manipulation experiments.

The paper is organized as follows: Section II presents mechanical molecular simulations of deca-alanine and viral proteins as passive/active links before to make a discussion about the current developments in bionanorobotics field in Section 3.

SIMULATION OF BIO-NANOROBOTIC COMPONENTS

Simulation of Elementary Bionanorobotic Module

Figure 2 shows a schematic of an elementary bionanorobotic module composed of a moving platform supported by the VPL motor and two deca-alanine proteins. The first image in Figure 4a shows the VPL in its initial state and the second image shows it in the final extended state due to pH activation. For detailed information on the working of the VPL motor the reader is encouraged to read reference [START_REF] Dubey | Viral Protein Linear (VPL) Nano-Actuators[END_REF]. Two deca-alanine proteins can be used as passive spring elements to join two platforms and form a single d.o.f parallel platform that is actuated by the upward stretching of the VPL actuator. Their elastic behavior can be used as a passive control element or as the restitution force that will bring the platform back to its original position. The proposed MD and VR system allows to simulate proteins and theoretically evaluate the forces generated in biochemical reactions, and even to exert external forces to alter the fate of these reactions. We present below the simulated mechanical properties of different passive and active bio-nanorobotic components of Figure 2a when subjected to external forces. The external forces (stretching, shearing or bending) are applied using a force feedback device (shown as a virtual AFM tip in figures) in order to study the mechanical properties of the principal architectural elements [START_REF] Hamdi | Molecular Mechanics Study on Bionanorobotic Components using Force Feedback[END_REF]. The various deformations that have been studied use an adiabatic energy mapping.

α-Helix Deca-Alanine Protein as Passive Joint

We applied the techniques described above to an exemplary system, helix-coil transition of deca-alanine in vacuum and in solvent. The well-known deca-alanine is an oligopeptide composed of ten alanine residues (Figure 5). In vacuum at room temperature (T=300°K), the stable configuration of deca-alanine is a α-helix. Stretching the molecule by an external force can induce its transition to an extended (coiled) form. This helix-coil transition represents a simple but basic folding system acting as a passive like-spring. In the simulation, we fix one end of the molecule (the main chain nitrogen atom of the first residue) at the origin and constrain the other end (the capping nitrogen atom of the C-terminus) to move only along the z axis, thereby removing the irrelevant degrees of freedom, i.e., removing the overall translation and rotation. For this, a guiding potential [START_REF] Park | Free energy calculation from steered molecular dynamics simulations using Jarzynski's equality[END_REF]

( ) ( ) ( ) [ ] 2 2 / ; λ ζ λ - = r r k u
(1) is added to control the end-to-end distance ξ which is a function of the 3N-dimensional position r of the system. The moving guiding potential used in the pulling simulations is represented by a spring which is connected to the C-terminus and pulled with a constant velocity v. The parameter λ is varied from 15 to 35 Å with a constant speed v of 0.1 Å/ns. A force constant of k=500 pN/Å is used in order to allow end-to-end distance ξ closely follow the constraint center λ. The external work curve is defined as: Depending on the sign of v, the external work can be defined for either stretching or contracting motion of the protein. Fig. 4a shows two distinct conformational transitions that provoke the conversion of α-helix to an extended form approaching the coil conformation. The force increases rather smoothly to almost 10pN up to a relative length of the protein. Once this transition is completed, the hydrogen bonds start to break and the structure further extends toward the coil conformation (intrinsic elastic regime), as shown in Part II, of the force curve (~700pN). At the lowest forces, the molecule behaves as a Hookian spring and its extension is proportional to the force applied at the end with a reversible motion. A useful approximation for spring constant k alan is given by the inextensible worm-like chain (WLC) model [START_REF] Park | Free energy calculation from steered molecular dynamics simulations using Jarzynski's equality[END_REF]. Then, if the stretching force increases gradually until to reach its stretching limit (~3600pN) with an irreversible motion in Part III. Fig. 4b shows the work done by forward pulling (stretching) and backward pulling at the same speed. As the protein environment has an important influence on its conformation, we studied the influence of the dynamics of water molecules (as a solvent) onto the protein-water interactions. Fig. 5 shows the influence of the water-protein interactions on the external force which shows that a greater force (and work) is required for reversible extension of the decaalanine protein. The water solvent increases considerably the Hookian spring k str of the protein structure. However, as the system contains solvent molecules, the relaxation time increases such that the helix-coil transition can be induced in a reversible manner with a hysteresis behavior. It should be noticed that the use of protein as passive joints suppose that the deca-alanine protein can also be mechanically dependent of temperature versus the work produced by the protein molecule stressed in an unnatural unfolding pathway. The previous results showed that the native structure is not destroyed under normal physiological conditions. In some unnatural conformations, lateral shearing and bending forces applied on a protein molecule has been simulated: fixedfree boundary conditions and fixed-fixed boundary conditions. These tests simulate disturbances of the bionanorobotic component under various operating conditions. For these conformations, Fig. 6 presents the lateral forces obtained. As shown in Fig. 6a, the lateral Hookian spring k shear has high stiff spring value that is able to counteract microenvironment variations and mechanical disturbances of a bio-nanorobotic platform. In this case, in contrast to stretching described above, the force variation is roughly monotonic with different plateau leading to different Hookian spring values. This is explained by a successive rather than a concurrent rupture of the hydrogen bonds joining the strands. Shearing is largely limited to breaking hydrogen bonds as there is little conformational change in the extended peptide backbones. Conversely, Fig. 6b shows a linear variation of force behavior when considering pure bending deformation of the protein. It shows that for little length deformation, it requires low constant force. After a threshold value, lateral bending must break the van der Waals interactions of the entire surface, leading to high forces and strong length dependence. Finally, these results indicate that it may be possible to obtain uncoupled mechanical spring behavior of the protein: stiff in lateral and compliant in Furthermore, under normal operating conditions, deca-alanine protein shows a reversibility of displacement-force characteristics which allows its use as spring-like joint in bio-nanorobotic platforms. longitudinal directions.

Viral protein linear (VPL) motor as active joint

In this part, we study the molecular properties of viral proteins to change their 3D conformation depending on the pH level of environment. Thus, a new linear biomolecular actuator type called Viral Protein Linear (VPL) motor, developed originally in [START_REF] Dubey | Computational Studies of Viral Protein Nano-Actuators[END_REF], is characterized as an active linear joint. The structure is like a hairpin composed of three coils, having one C terminal (carboxy-end) and undergoes a conformational change induced by mildly acidic conditions (i.e., pH around 5). With the change in pH, the N-terminals pop out of the inner side and the peptide acquires a straightened position. The VPL motor uses the Influenza virus protein Hemagglutinin (HA). Two known states are established, i.e., the native state and the fusogenic state of the 36-residue peptide of HA. The structural data of these states are obtained from the Protein Data Bank (PDB) [START_REF] Berman | The Protein Data Bank[END_REF]. The representative "open" structure can be generated by forcing the structure away from the native conformation (Fig. 8a) to open state (conformation) (Fig. 8b) with constrained high-temperature molecular dynamics. Both the forward (closed to open) and the reverse (open to close) transformations are carried out for two end-point structures of 9Å. This peptide is able to perform repeatable motion controlled by variation of pH.

In order to study the mechanical limits of the reference end-point states with a reversible motion, simulations of the mechanical stretching through a guiding potential of Eq.2 has been investigated. Here, we stretch the viral protein in an irreversible manner and examine the resulting distribution of force.

Mavroidis Prototyping Bio-Nanorobots Using Molecular Dynamic Simulation

The spring constant is settled at k=500pN/Å and T=300°K. The molecule is stretched by changing the parameter λ from 15 to 40 Å with a constant speed. Figure 8a gives the results of displacement and force stretching (K stret = 625pN/nm) of the VPL motor. Fig. 8b-c shows the shearing (K shear = 312pN/nm) and bending results (K bend = 714pN/nm) when v=1Å/ns, k=500pN/Å and T=300°K. A more realistic environment of the VPL requires the inclusion of the effect of pH on the protein.

In order to take into account the real-time effect of pH on the ionic stability of the protein, a current model will be considered in a next phase.

SIMULATION OF A BIO-NANOROBOTIC PARALLEL PLATFORM

In order to prototype mechanical designs of bio-robotic structures, we simulated the parallel nanorobotic platform of Fig. 9 of four passive parallel links using serially-linked deca-alanine proteins connected to a graphite platform at both ends. Each link is composed of of three deca-alanine proteins serially linked. The attachment of the different components are 4 carbon atoms (proteins/graphite interface) and 3 hydrogen atoms (protein/protein interface). The dimensions for the ractangular graphite sheet are 14.8nm by 8.5nm and the total length of the three proteins is 13.1nm. We applied stretching forces at the upper graphite platform.

Simulations showed that the parallel connection of serially-linked deca-alanine proteins permits to augment considerably the resulting springforce and to decrease the overall displacement. As example, Fig. 10 shows the stretching force curve of two parallel links composed of four serial spring-like proteins (deca- alanine) for v=1Å/ns, k=500pN/Å and T=300°K. The spring force is considerably increased symmetrically for both parallel links until to reach its point of rupture. As expected during stretching (serial/parallel structure) the generated forces in parallel configuration is multiplied by 2 while in serial configuration, the displacement is multiplied roughly by 4. The elongation of the serial configuration is mainly dominated by unfolding the αhelices of the different deca-alanine proteins. However, the rupture point is not due to the rupture of the protein but simply by the rupture of the attachment between the proteins (1,1') and (2,2') as shown in Fig. 10. We can see in Fig. 11 the linear behavior of the stretching force curve at each protein/protein joint (joints 1, 2, 3 and 4). It should be noted in the Fig. 10 that the force behavior of each parallel link is quite similar. As a result of our simulations (stretching, bending and shearing) the different stiffnesses differ strongly depending of the external disturbances applied to the nanorobotic platform: In order to reduce the number of components, the serial configuration of deca-alanine proteins have been replaced by ROP proteins (parallel link). The repressor of primer protein (ROP) is a small, dimeric molecule consisting of two identical chains of 63 amino acids. The two monomers pack together as a fully antiparallel four helixbundle. The bend region of Rop has attracted considerable interest as a parallel molecular spring due to its stability and elasticity properties [START_REF] Kresse | Four-helix bundle topology re-engineered: monomeric Rop protein variants with different loop arrangements[END_REF]. In the simulation, we constrain both ends of two α-helices of the molecule to move only along the z axis for stretching simulations and fix the short turn (Fig. 12). Compared to the elastic behavior of deca-alanine proteins (see Fig. 4a), we can see the same reversible elastic behavior with greater forces due to its parallel structure. Furthermore, each passive link behaves as a perfect reversible linear joint when it is relaxed from its stretched state. Due to its native parallel structure, we need only four ROP proteins connected to the graphite platform. VI. CONCLUSION This paper presents a molecular mechanics study carried out with a molecular dynamics computation. It allows simulating the force, position and energy feedback of spring-like and actuator-like proteins for design evaluation of future bio-nanorobots. The preliminary mechanical force results given in this study corroborates the force results when stretching α-helix, β-ribbon proteins and double-helical DNA molecules. Further refinement will be carried out in order to integrate the VPL motor into the parallel platform for active actuation.

Fig. 1 :

 1 Fig. 1: Several VPL motors placed in parallel (left) and series (right) to multiply force and displacement respectively.

Fig. 2 :

 2 One degree of freedom Bio-Nanorobotic module actuated by a viral protein motor and two α-helix deca-alanine protein springs.

Fig. 3 :

 3 Fig. 3: Unfolding of helical deca-alanine. Left, a folded configuration (α-helix) is shown. The six hydrogen bonds that stabilize the helix are shown. Middle and right, extended configurations (coil) when stretching the molecule by an external force (shown as a virtual AFM tip).

  , G.Sharma, A.Ferreira, D.Mavroidis Prototyping Bio-Nanorobots Using Molecular Dynamic Simulation

  Figure 4a-b shows the maximal force and energy variation (before breaking) as a function of stretching distance.

Figure 4 :

 4 Figure 4: α-Helix to ribbon stretching. (a) Force curve and (b) Work done by forward pulling (stretching) and backward pulling (contracting) with v=0.1 Å/sec. For the forward pulling, the position of the constraint center ξ is varied from 15 to 35Å; for the backward pulling, from 35 to 15 Å.

Figure 5 :

 5 Figure 5: Force curve of α-Helix to ribbon done by forward stretching with a reversible motion (Part I and II).

Force

  , G.Sharma, A.Ferreira, D.Mavroidis Prototyping Bio-Nanorobots Using Molecular Dynamic Simulation

Fig. 6 :

 6 Fig. 6: Force curve of α-Helix deca-alannine protein when perturbed by a (a) lateral shearing force F shea and (b) bending force F bend .

Fig. 7 :

 7 Fig.7: (a) loop 36 protein in the native state; (b) open-state conformation of the VPL motor shown with van der Waals surface distribution.

Figure 8 :

 8 Figure 8: VPL of force-versus-distance characteristics: (a) stretching, (b) shearing and (c) bending for v=1Å/ns, k=500pN/Å and T=300°K.

  , G.Sharma, A.Ferreira, D.

Fig. 9 :

 9 Fig.9: Parallel nanorobotic platform composed of two graphite platforms and four serially-linked passive linear links. The four parallel links are composed of three serial deca-alanine proteins.

Fig. 10 :

 10 Fig.10: Stretching force curve of two parallel links composed of four serial deca-alanine proteins acting as elastic and reversible springs.

Fig. 11 :

 11 Fig.11: Force at each protein link of a four serial deca-alanine proteins acting as elastic and reversible springs.

FIG. 12 :

 12 FIG.12: Double α-helix to ribbon stretching. (a) Force curve and (b) hysteresis curve done by forward stretching (with v=0.1 Å/sec) and relaxation of the structure when the stretching force is zero.

  stretching stiffness is strongly influenced by the native environment: (k stret ) air ≅ 400 pN/nm and (k stret ) water ≅ 70 pN/nm -lateral shearing (k shear ≅ 700 pN/nm) is much more stiffer than lateral bending (k shear ≅ 30 pN/nm) which ensures a good mechanical stability of the platform against external disturbances.

	M.Hamdi, G.Sharma, A.Ferreira, D.Mavroidis
	Prototyping Bio-Nanorobots Using Molecular Dynamic Simulation
	Carbon atoms
	Graphite platform
	Hydrogen atoms
	3 Proteins

-


Kunal Dutta
email: kunal.dutta@inria.fr

Arijit Ghosh

On Subgraphs of Bounded Degeneracy in Hypergraphs

Keywords: degenerate graphs, independent sets, hypergraphs, and random permutations

A k-uniform hypergraph is d-degenerate if every induced subgraph has a vertex of degree at most d. Given a k-uniform hypergraph H = (V (H), E(H)), we show there exists an induced subgraph of size at least

,

and dH (v) denotes the degree of vertex v in the hypergraph H. This connects, extends, and generalizes results of Alon-Kahn-Seymour (Graphs and Combinatorics, 1987), on d-degenerate sets of graphs, Dutta-Mubayi-Subramanian (SIAM Journal on Discrete Mathematics, 2012) on d-degenerate sets of linear hypergraphs, and Srinivasan-Shachnai (SIAM Journal on Discrete Mathematics, 2004) on independent sets in hypergraphs to d-degenerate subgraphs of hypergraphs. Our technique also gives optimal lower bounds for a more generalized definition of degeneracy introduced by Zaker (Discrete Applied Mathematics, 2013). We further give a simple nonprobabilistic proof of the Dutta-Mubayi-Subramanian bound for linear k-uniform hypergraphs, which extends the Alon, Kahn and Seymour (Graphs and Combinatorics, 1987) proof technique to hypergraphs. Finally we provide several applications in discrete geometry, extending results of Payne-Wood (SIAM Journal on Discrete Mathematics, 2013) and Cardinal-Tóth-Wood (Journal of Geometry, 2016). We also address some natural algorithmic questions.

The proof of our main theorem combines the random permutation technique of Bopanna-Caro-Wei and Beame and Luby, together with a new local density argument which may be of independent interest.

.

Introduction

For k ≥ 2, a k-uniform hypergraph H is a pair H = (V, E) where E(H) ⊆ V (H) k
respectively. When there is no chance of confusion, we will use V and E to denote V (H) and E(H). For a vertex v ∈ V (H), degree d H (v) of V (H) will denote |{e : e ∈ E(H), v ∈ e}|. For readability, k -1 will be denoted by t.

For a subset I ⊆ V (H), the induced k-uniform hypergraph H(I) of I denotes the hypergraph (I, E(H) ∩ I k ). A hypergraph is linear if every pair of vertices are contained in at most a single hyperedge, i.e. any pair of hyperedges intersect in at most one vertex. A hypergraph H = (V, E) is d-degenerate if the induced hypergraph of all subsets of V has a vertex of degree at most d, i.e., for all I ⊆ V , there exists v ∈ I such that d H(I) (v) ≤ d. For a k-uniform hypergraph H = (V, E), we will denote by α k, d (H) the size of a maximum-sized subset of V whose induced hypergraph is d-degenerate, i.e., α k, d (H) = max {|I| : I ⊆ V, H(I) is d-degenerate} .

Observe that α(H) := α k, 0 (H) is the independence number of the hypergraph H.

1.1. Previous Results. Turán [START_REF] Turán | On an extremal problem in graph theory[END_REF] gave a lower bound on the independence number of graphs: α(G) ≥ n d+1 where d is the average degree of vertices in G. Caro [START_REF] Caro | New results on the independence number[END_REF] and Wei [START_REF] Wei | A lower bound on the stability number of a simple graph[END_REF] independently showed that for graphs

α(G) ≥ v∈V (G) 1 d G (v) + 1
, see [START_REF] Alon | The Probabilistic Method[END_REF]. This degree-sequence based bound matches the original averagedegree based lower bound of Turán in the case when all degrees are equal, and improves it for general degree sequences. For hypergraphs, Spencer [START_REF] Spencer | Turán's theorem for k-graphs[END_REF] gave a bound on the independence number, based on the average degree d: α(H) ≥ c k n d 1/t , where c k is independent of n and d. Caro and Tuza [START_REF] Caro | Improved Lower Bounds on k -Independence[END_REF] generalized the Caro-Wei result to the case of hypergraphs: Theorem 1.1. For all k-uniform hypergraph H, we have

α(H) ≥ v∈V 1 d H (v)+1/t d H (v)
. 1

The above theorem directly implies the following corollary, which gives Spencer's bound: Corollary 1.2. For all k ≥ 2, There exists d k > 0 such that all k-uniform hypergraphs H satisfy

α(H) ≥ d k v∈V 1 (1 + d H (v)) 1/t .
1 Where for l ∈ N ∪ {0} and r ∈ R, r l = r(r-1)...(r-l+1) l!

.

Further, Thiele [START_REF] Thiele | A Lower Bound on the Independence Number of Arbitrary Hypergraphs[END_REF] obtained a lower bound on the independence number of arbitrary (non-uniform) hypergraphs, in terms of the degree rank, a generalization of the degree sequence.

On the algorithmic side, Srinivasan and Shachnai [START_REF] Shachnai | Finding Large Independent Sets in Graphs and Hypergraphs[END_REF], used the random permutation method of Beame and Luby [START_REF] Beame | Parallel Search for Maximal Independence Given Minimal Dependence[END_REF] and also Bopanna-Caro-Wei (see e.g. [START_REF] Alon | The Probabilistic Method[END_REF], [START_REF] Dutta | New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs[END_REF]), together with the FKG correlation inequality, to obtain a randomized parallel algorithm for independent sets, which matched the asymptotic bound of Caro and Tuza [START_REF] Caro | Improved Lower Bounds on k -Independence[END_REF]. Dutta, Mubayi and Subramanian [aDMS12] also used the Bopanna-Caro-Wei method; alongwith some new combinatorial identities, they obtained degree-sequence based lower bounds on the independence numbers of K r -free graphs and linear k-uniform hypergraphs, which generalized the earlier average-degree based bounds of Ajtai, Komlós, and Szemerédi [START_REF] Ajtai | A Note on Ramsey Numbers[END_REF], Shearer [START_REF] Shearer | A note on the independence number of triangle-free graphs[END_REF][START_REF] Shearer | On the Independence Number of Sparse Graphs[END_REF] and Duke, Lefmann and Rödl [START_REF] Duke | On Uncrowded Hypergraphs[END_REF], in terms of degree sequences.2 Average degree vs. degree-sequence. Intuitively, a bound using the degree sequence should be expected to be better than a bound using just the average degree, since it has more information about the graph. For the above bounds on the independence numbers, this essentially follows from the convexity of the function x -1/t . Dutta, Mubayi and Subramanian [START_REF] Dutta | New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs[END_REF] gave constructions of hypergraphs which show that the bounds based on the degree-sequence can be stronger than those based on the average degree by a polylogarithmic factor in the number of vertices.

Large d-degenerate subgraphs. Unlike independent sets in graphs, ddegenerate subgraphs have been less well-investigated. However, it includes as special cases zero-degenerate subgraphs i.e. independent sets, as well as 1-degenerate subgraphs, i.e. maximum induced forests, whose complements are the well-known hitting set and feedback vertex set problems respectively. The best known result on this question is that of Alon, Kahn and Seymour [START_REF] Alon | Large Induced Degenerate Subgraphs[END_REF], who proved the following lower bound for α 2, d (G):

3 Theorem 1.3 ([AKS87]). For all graphs G = (V, E) we have α 2, d (G) ≥ v∈V min 1, d + 1 d G (v) + 1 .
This bound is sharp for every G which is a disjoint union of cliques. Moreover, they gave a polynomial time algorithm that finds in G an induced d-degenerate subgraph of at least this size.

On the algorithmic side, Pilipczuk and Pilipczuk [START_REF] Pilipczuk | Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n[END_REF] addressed the question of finding a maximum d-degenerate subgraph of a graph, giving the first algorithm with running time o(2 n ). Zaker [START_REF] Zaker | Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs[END_REF] studied a more general version of degeneracy and gave upper and lower bounds for finding the largest subgraph of a 2-uniform graph having a given generalized degeneracy.

The proof of Dutta-Mubayi-Subramanian [START_REF] Dutta | New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs[END_REF] implies the following lower bound on α k, d for linear hypergraphs (though not explicitly stated in their paper):

Theorem 1.4 ([aDMS12]). Let G = (V, E) be a linear k-uniform hyper- graph, and for all v ∈ V , d G (v) denote the degree of v in G. Then (1) α k, d (G) ≥ w(G) := v∈V w G (v),
where

(2) w(v) =      1 if d G (v) ≤ d 1 1+((k-1)(d+1)) -1 ( d G (v) d+1 ) ( d G (v)+ 1 k-1 d G (v)-d-1 ) if d G (v) > d.
A possible extension and a counterexample. When d = 0, i.e. the subgraph is an independent set, the above expression reduces to the Caro-Tuza bound in Theorem 1.1. In the proof of the above theorem, the term corresponding to a given vertex v in the above expression is actually the fraction of orderings of the vertices, in which there are at most d hyperedges involving v and some vertices occuring prior to v, in the ordering. For linear k-uniform hypergraphs, the above expression is exact, but this does not hold for general k-uniform hypergraphs. However, in the case when d = 0, the above expression still gives an upper bound on the fraction of such orderings. One may wonder if a similar property might hold for general k-uniform graphs, for general d.

That is, does it hold that for any given vertex v ∈ V , the fraction of orderings of vertices where at most d hyperedges can be formed using only the vertex v and vertices occuring prior to v, is at most

1 1+((k-1)(d+1)) -1 ( d G (v) d+1 ) ( d G (v)+ 1 k-1 d G (v)-d-1 ) ?
This however can be seen to be false, from the following example: Counterexample Consider the 3-uniform hypergraph H = (V, E), given by V = {1, 2, 3, 4, 5} and E = {{1, 2, 3}, {1, 3, 4}, {1, 4, 5}, {1, 5, 2}}. Taking d = 1, we get that the expression obtained from the above expression for the vertex 1, is

(3 -1) • 2 1 + (3 -1) • 2 4 2 4+ 1 3-1 4 = 216 315 = 24 35 .
On the other hand, the fraction of orderings of vertices, where the vertices occuring prior to 1 together with the vertex 1, constitute at most one hyperedge, is 72 120 = 3 5 < 24 35 . Therefore, the expression in Theorem 1.4 clearly overshoots the actual fraction of orderings.

Thus, the bound in Theorem 1.4 does not hold for general d.

1.2. Our Results. We first give a completely different and an extremely simple proof of Theorem 1.4 using a weight function. Our proof follows along the lines of the proof of Theorem 1.3 due to Alon, Kahn and Seymour [START_REF] Alon | Large Induced Degenerate Subgraphs[END_REF].

Although the counterexample in the previous subsection shows that the bound in Theorem 1.4 does not hold for general d and general k-uniform hypergraphs, we show that the asymptotic expression (in terms of d and d G (v)) still holds, thus extending Theorem 1.4 asymptotically to the case of general hypergraphs:

Theorem 1.5. Let G = (V, E) be a k-uniform hypergraph, and for all v ∈ V , d G (v) denote the degree of v in G. Then (3) α k, d (G) ≥ v∈V min 1, c k d + 1 d(v) + 1 1/t , where t = k -1 and c k = 2 -1+ 1 (k-1) 1 -1 k .
Further, there exists a randomized algorithm that can extract a d-degenerate set of above size in expectation.

Our proof uses the random permutation method [AS08] of Bopanna-Caro-Wei, together with a new local density argument, avoiding advanced correlation inequalities. As a consequence, we obtain a simpler proof as well as a generalization of the result of Srinivasan and Shachnai [START_REF] Shachnai | Finding Large Independent Sets in Graphs and Hypergraphs[END_REF].

The rest of the paper is organised as follows: Section 2 has the simpler proof of Theorem 1.4, Section 3 has the proof of Theorem 1.5 and in Section 4 we prove lower bounds for a more generalized definition of degeneracy. In Section 4, we will show that our proof technique for Theorem 1.5 gives optimal lower bounds for a more generalized definition of degeneracy introduced recently by Zaker [START_REF] Zaker | Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs[END_REF]. In Section 5 we give several applications of our results in discrete and combinatorial geometry. Finally in the conclusion there are some remarks and open questions.

Linear Hypergraphs

In this section we will give an alternative proof of the Theorem 1.4. The proof will follow exactly along the lines of the proof by Alon, Kahn and Seymour [AKS87] of Theorem 1.3.

First observe that

d G (v) r d G (v)+1/t d G (v)-r = 1 1 + 1 t(r+1) . . . 1 + 1 td G (v) This implies that w(v) is decreasing in d G (v) for all values of d G (v) ≥ r. Also, observe that (4) d G (v)-1 r d G (v)-1+1/t d G (v)-1-r = 1 + 1 t d G (v) d G (v) r d G (v)+1/t d G (v)-r
The alternative proof will be by induction on the number n of vertices of the k-uniform hypergraph G. The base case of n = 1 follows trivially. Assuming the result holds for n -1, we will now show that the result also holds for n.

Given a vertex v ∈ V , let H v denote the hypergraph G(V ) where V = V \ {v}. Case 1. If we have a vertex v ∈ V (G) with d G (v) ≤ d, then consider H = H v . Observe that α k, d (G) = α k, d (H) + 1. Since ∀u ∈ V , we have from Equation (4), w G (u) ≤ w H (u). This implies w(H) = u∈V w H (u) ≥ u∈V w G (u) = w(G) -1.
The last inequality follows from the fact that w

G (v) = 1 since d G (v) ≤ d. Using the induction hypothesis α k, d (G) ≥ w(G) and the fact that α k, d (G) = α k, d (H) + 1, we get α k, d (G) = α k, d (H) + 1 ≥ w(H) + 1 ≥ w(G).
Case 2. Now we will consider the case where d G (v) > d, ∀v ∈ V (G). Let ∆ = max u∈V (G) d G (u), and let v ∈ V (G) be a vertex with d G (v) = ∆. Let u 1 , . . . , u l , where l = t∆, be the neighbors of v in G. Note that l = t∆ follows from the fact that G is a linear hypergraph. We will now show that w(H) ≥ w(G), where H = H v .

w(H) = u∈V w H (u) = w(G) -w G (v) - l i=1 w G (u i ) + l i=1 w H (u i ) = w(G) -w G (v) + l i=1 w G (u i ) t d G (u i ) ≥ w(G)
The second last inequality follows from the facts that d H (u i ) = d G (u i ) -1 (as G is a linear hypergraph) and Equation (4). The last inequality follows from the facts that d G (u) ≤ ∆ for all u ∈ V and w G (u i ) ≥ w G (v) (direct consequence of Equation (4)). From induction hypothesis we have

α k, d (H) ≥ w(H) ≥ w(G).
This completes the proof of Theorem 1.4 since α k, d (G) ≥ α k, d (H).

General k-uniform Hypergraphs

In this section we shall prove a lower bound on α k,d (H) for general kuniform hypergraph H in terms of its degree sequence. We will give a very simple randomized algorithm to obtain an d-degenerate subgraph of a kuniform hypergraph, whose analysis in expectation will yield the desired bound in Theorem 1.5.

3.1. Details of the Algorithm. Before we can give the details of the algorithm, we will need some definitions. Definition 3.1. Let σ be an ordering of the vertices of H.

• Fix a vertex v ∈ V (H). Call a hyperedge e ∈ E(H) with v ∈ e a backward edge with respect to σ, if ∀u ∈ e \ {v}, σ(u) < σ(v). • We will denote by b σ (v) the number of backward edges of the vertex v with respect to the ordering σ.

Algorithm 1 RandPermute

Input: H := (V, E) and d; // H is a k-uniform hypergraph Random odering: Let σ be a random ordering of the vertex set V ; Initialization: I ← ∅; // I will be the degenerate subset we output;

for v ∈ V do Compute: b σ (v); if b σ (v) ≤ d then I ← I ∪ {v}; end if end for Output: I;
3.2. Analysis of the Algorithm. Theorem 1.5 directly follows from the following result.

Claim 3.2. E [|I|] ≥ v∈V min 1, c k d + 1 d H (v) + 1 1/t , where c k = c k = 2 -(1+ 1 k-1 ) 1 -1 k = 2 -(1+o k (1)
) . Proof. For all vertices v ∈ V , we will denote by N (v) the neighbors of v in H.

Given an arbitrary vertex v ∈ V , and a random ordering of the vertices σ, we need to bound Pr [v ∈ I] from below. Since the event of v being selected depends on the relative ordering of the vertices in N (v), therefore, the probability v being selected in I in a random ordering is the number of orderings for which v is selected, divided by (|N (v)| + 1)!. Let σ be an ordering of the vertices of V , such that v is selected in I in the ordering σ. Given a vertex v ∈ V , consider now L v := (V (L v ), E(L v )), the (k -1)uniform link hypergraph on the neighbourhood of v, defined as follows:

V (L v ) := N (v)
, and

E(L v ) := {S ⊂ V (L v ) : S ∪ {v} ∈ E},
i.e., the vertices are the neighbours of v, and the edges are those edges of the original hypergraph H which contained v, but with v removed. Clearly

|E(L v )| = d H (v). Let F ⊂ V (L v ) be F := {u ∈ N (v) : σ(u) < σ(v)} ,
i.e., the vertices in the neighbourhood of v which occur before v in the ordering σ. We want L v (F ) to have at most d hyperedges. The vertices occurring before v can be ordered arbitrarily amongst themselves, and similarly for the vertices occuring after v. So we get that the probability that v is selected in I is given by:

Pr [v ∈ I] = J⊂V (Lv) : |E(Lv(J))|≤d (|J|)! (|V (L v )| -|J|)! (|V (L v )| + 1)! = 1 |V (L v )| + 1 J⊂V (Lv) : |E(Lv(J))|≤d 1 |V (Lv)| |J|
For k = 2, the link hypergraph is a 1-graph i.e. a set of vertices, each vertex being a 1-edge. Hence the summation in the RHS evaluates to d + 1 (counting 1 for each case when there are exactly 0, 1, . . . , d vertices before v, in the random ordering). Therefore

E [|I|] = v∈V Pr [v ∈ I] = v∈V min 1, d + 1 d(v) + 1 ,
and we get the theorem of Alon, Kahn and Seymour (Theorem 1.3). For general k-uniform hypergraphs, observe that if d H (v) ≤ d, then Pr [v ∈ I] = 1. However, if d H (v) > d, then we need to look at the link hypergraph which can be an arbitrary k -1-uniform hypergraph. In this case, we shall prove the following general lemma, (which may be of independent interest).

Lemma 3.3. For each k-uniform hypergraph H = (V, E), such that |V | = n, |E| = m, we have J⊂V (H) : |E(J)|≤a 1 n |J| ≥ c k n a + 1 m 1/k . where c k = 2 -(1+1/k) .
Indeed, we get that the probability that v is selected in I is given by:

Pr [v ∈ I] = 1 |V (L v )| + 1 J⊂V (Lv) : |E(Lv(J))|≤d 1 |V (Lv)| |J| ≥ c k-1 |V (L v )| |V (L v )| + 1 × (d + 1) 1/(k-1) |E(L v )| 1/(k-1) (from Lemma 3.3) ≥ c k-1 |V (L v )| |V (L v )| + 1 × (d + 1) 1/(k-1) d H (v) 1/(k-1) (as |E(L v )| = d H (v)) ≥ c k d + 1 d H (v) + 1 1/(k-1) , (5)
where

c k = 2 -(1+ 1 k-1 ) 1 - 1 k = 2 -(1+o k (1)) .
Note that Inequality (5) follows from the fact that since d

H (v) > d ≥ 0, we must have at least k -1 vertices in the hypergraph L v , i.e., |V (L v )| ≥ k -1.
It only remains to prove Lemma 3.3, which we will prove using a local density argument.

Proof of Lemma 3.3. For all 1 ≤ s ≤ n, we define

ρ s := E |S|=s [|E(H(S))|] = S⊆V, |S|=s E(H(S)) n s .
Note that the expectation is taken over all subsets of V of size s, and

E(H(S)) = {e ∈ E(H) : e ⊆ S} .
Counting the number of pairs (e, S), where e ∈ E(H), and S ⊂ V : |S| = s, e ∈ S, in two ways, we get the average local density of sets of size s is

ρ s = m n-k s-k n s = m(s) k (n) k ≤ ms k n k .
(Here a b := 0 if b < 0). This is as follows: let

z := # (e, S) : e ∈ E, S ∈ V s , e ⊂ S .
Then each of the n s sets of size s contributes, on average, ρ s -many entries to z. On the other hand, each edge e ∈ E(H) belongs to n-k s-k -many sets of size s. Equating the two summations gives the claimed average local density. Now, we use the above observation to prove the lemma. Partition the summands on the LHS into n parts, depending on the size of the set J (i.e. the number of neighbouring vertices which precede v in the random ordering):

n i=1    J∈( V i ) : |E(H(J))|≤a 1 n i    .
When i < k, it is easy to see that the inner summation is 1. The main idea of the proof is the following: first, observe that for any i ∈ [n], the inner summation is just the probability that a randomly picked set of exactly i vertices has fewer than a + 1 edges. Next, the expected number of edges in a randomly chosen i-vertex subset, is upper bounded by ρ i , and for small enough i, is much smaller than (a + 1)/2. So the probability that a random i-set contains more than twice the expected number, is at most half. So for all such i, the contribution to the outer sum is at least 1/2. The number of such terms in the outer sum then gives the claimed lower bound.

Formally, let X i be a random variable giving the number of edges contained in a randomly chosen set on i vertices. By Markov's inequality:

Pr [X i ≥ 2.E [X i ]] ≤ 1 2 .
We have that E [X i ] = ρ i . Therefore, the LHS becomes:

n i=1 Pr [X i < a + 1] = 1 - n i=1 Pr [X i ≥ a + 1]
With foresight, we split the above sum into two parts, when i ≤ t * := n(a+1) 1/k (2m) 1/k , and when i > t * . Observe that when i ≤ t * , we have that

mi k n k ≤ a+1 2 . We get n i=1 Pr [X i < a + 1] = t * i=1 Pr [X i < a + 1] + i>t * Pr [X i < a + 1] ≥ t * i=1 1 - E [X i ] a + 1 = t * i=1 1 - m(i) k (a + 1)(n) k ≥ t * i=1 1 - mi k (a + 1)n k ≥ t * i=1 1 - 1 2 ≥ n(a + 1) 1/k 2(2m) 1/k .
where in the second step we used Markov's inequality on the first summation, and in the penultimate step we used the observation on t * noted above. This completes the proof of Lemma 3.3.

Remark 3.4. For simplicity of exposition we did not try to optimize c k in the proof of Theorem 1.5. We observe that

c k = 2 -(1+ 1 k-1 ) 1 - 1 k ≥ 1 8 ,
for all k ≥ 2, and c k → 1 2 as k → ∞.

Generalized degeneracy

In a recent paper Zaker [START_REF] Zaker | Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs[END_REF] generalized the definition of definition of degeneracy to arbitrary function over the vertex set of graphs taking values from non-negative integers. This is a strict generalization of degeneracy to graphs, and in this section we will now show that techniques from this paper can be directly used to get asymptotically bounds for this definition as well.

Let H be a k-uniform hypergraph with |V (H)| = n, and let κ : V (H) → N ∪ {0} be a non-negative integer assignment to the vertices of H. We will say H is κ-degenerate if the vertices of H can be ordered as v 1 , . . . , v n such that the degree of vertex v i in the hypergraph

H i = H ({1, . . . , i}) is at most κ(v i ).
Let H be k-uniform hypergraph, and let κ :

V (H) → N ∪ {0}, then α k,κ (H) = max |I| : I ⊆ V (H), H(I) is η-degenerate where η = κ | I .
Directly applying the random permutation technique from Section 3 will give us the following result. We have included the proof of completeness.

Theorem 4.1. For all graphs G = (V, E) and κ : V (H) → N ∪ {0}, we have exists an induced subgraph H of G with

α k,κ (G) = v∈V min 1, κ(v) + 1 d G (v) + 1 .
Moreover there exists a randomized polynomial time algorithm that finds in G an induced subgraph H which is η-degenerate, where η = κ | V (H) , and the

expected size of |V (H)| is v∈V min 1, κ(v)+1 d G (v)+1 .
Proof. Let σ be a random ordering of the vertex set V . Without loss of generality set

σ := v 1 < v 2 < • • • < v n .
The vertex set of V is processed in the increasing order with respect to σ starting with v 1 . We will include a vertex v i in the set I if the number of neighbors of v appearing before v in the random ordering σ, i.e., if

|N (v i ) ∩ {v 1 , . . . , v i-1 }| ≤ κ(v i ) then v i ∈ I.
The output of this procedure H = G(I). Observe that H is ηdegenerate where η = κ | I . So the only thing left to prove is the lower bound

on E σ [|I|]. Observe that if d G (v i ) ≤ κ(v i ) then Pr [v i ∈ I] = 1, otherwise Pr [v i ∈ I] = κ(v i ) i=0 d G (v i ) j j! (d G (v i ) -j)! (d G (v i ) + 1)! = κ(v i ) + 1 d G (v i ) + 1 . Therefore E σ [|I|] = n i=1 Pr [v i ∈ I] = n i=1 min 1, κ(v i ) + 1 d G (v i ) + 1
This completes the proof.

Using the inductive argument in Section 2 we will get the following generalization of Theorem 1.4 Theorem 4.2. Let G = (V, E) be a linear k-uniform hypergraph, and κ :

V → N ∪ {0}. Then (6) α k, κ (G) ≥ w(G, κ) := v∈V w G (v, κ), where (7) w
G (v, κ) =    1 if d G (v) ≤ κ(v) 1 1+(t(κ(v)+1)) -1 ( d G (v) κ(v)+1 ) ( d G (v)+1/t d G (v)-κ(v)-1 ) if d G (v) > κ(v).
For general k-uniform hypergraphs, using random permutation and the proof technique from Section 3, we can prove the following generalization of Theorem 1.5.

Theorem 4.3. Let G = (V, E) be a k-uniform hypergraph, and κ :

V → N ∪ {0}. Then (8) α k, κ (G) ≥ v∈V min 1, c k κ(v) + 1 d G (v) + 1 1/t , where t = k -1 and c k = 2 -1+ 1 (k-1)
1 -1 k . There exists a randomized algorithm that can extract a d-degenerate set of above size in expectation.

Applications in Discrete Geometry

In this section, as an application of Theorem 1.5 we will prove several generalizations of a result of Payne and Wood [START_REF] Payne | On the General Position Subset Selection Problem[END_REF] in incidence geometry, on the maximum size of a subset, of an n point set in the plane, such that no three points in the subset are collinear.

Lemma 5.1.

(1) Let P be a set of n points in the plane such that for any line l in the plane |l ∩ P | ≤ . For d ≤ O(n log + 2 ) there exists a subset S ⊆ P with at most d|S| collinear triples in S and

|S| = Ω d n 2 n log + 2 . And if ≤ O( √ n), then |S| = Ω d n log .
(2) Let P be a set of n points in the plane such that for any line l in the plane |l ∩ P | ≤ . Let k ≥ 4 be a constant and d ≤ O( k-3 n + k-1 ).

Then there exists a subset S ⊆ P of size

Ω n d k-3 n + k-1 1/(k-1)
such that S has at most d|S| collinear k-tuples in S.

And if ≤ O( √ n), then |S| = Ω n k-2 d k-3 1/(k-1)
.

The following result of Payne and Wood [START_REF] Payne | On the General Position Subset Selection Problem[END_REF], proved using Szemerédi-Trotter theorem [START_REF] Szemerédi | Extremal problems in discrete geometry[END_REF] on incidence geometry, will be used to prove Lemma 5.1.

Lemma 5.2 ([PW13]).

(1) Let P be a set of n points in the plane such that for any line l in the plane |l ∩ P | ≤ . Then the number of collinear 3-tuples in P is at most O(n 2 log + n 2 ).

(2) Let P be a set of n points in the plane such that for any line l in the plane |l ∩ P | ≤ . Then, for k ≥ 4, the number of collinear k-tuples in P is at most O( k-3 n 2 + k-1 n).

Proof of Lemma 5.1. Let H be a k-uniform hypergraph with V (H) = P , and {p 1 , . . . , p k } ∈ E(H) if there exists a line a line l in the plane with {p 1 , . . . , p k } ∈ l. Lemma 5.2 bounds the size of E(H). The result now follows directly from Theorem 1.5.

In a followup work Cardinal, Tóth and Wood [START_REF] Cardinal | General position subsets and independent hyperplanes in d-space[END_REF], using Elekes and Tóth's [ET05, Theorem 2.3] generalisation to hyperplane point incidences in R d of Szemeredi-Trotter's theorem [START_REF] Szemerédi | Extremal problems in discrete geometry[END_REF] on incidence geometry, proved the following theorem. As in the proof of Lemma 5.1 using the above result together with Theorem 1.5 implies the following result. such that S has at most d|S| cohyperplanar (m + 1)-tuples in S.

These geometric results can be easily extended to the polynomial settings. Let F ⊂ R[X 1 , . . . , X m ] be a family of non-zero polynomial functions with real coefficients in m variables statisfying the following property: every f ∈ F can be written as a linear combination of the polynomials f 0 (X), . . . , f b (X) where f 0 (X) = 1 and the polynomials f i (X) are linearly independent in R[X 1 , . . . , X m ]. Now a point set P in R m , with |P | > b, is said to be in general position if no more than b points of P lies on a zero set of a polynomial in F. In this situation we are interested in extracting a large subset S of P such that number of (b + 1)-tuples in S which lie on a zero set of at least one polynomial in F is at most d|S|.

First observe that this definition captures many notions of general position with respect to algebraic and geometric objects of bounded complexity.

Remark 5.5.

(1) Family of spheres in R m : This set is generated by the polynomials m i=1 X 2 i , X 1 , . . . , X m , 1 . A set P in R m is said to be in general position with respect to spheres if no more than m + 1 points of P lie on any given sphere. This notion of general position is extremely important in computational geometry both from theoretical and practical sides. For example, see [ This set is generated by the set S = {X j 1 1 . . . X jm m | 0 ≤ m i=1 j i ≤ D}. Observe that |S| = D+m m . A set P in R m is said to be in general position with respect to this family if no more than D+m m -1 points of P lie on any given non-zero polynomial in R[X 1 , . . . , X m ] with degree bounded by D. This notion of general position appears in semialgebraic range searching [START_REF] Pankaj | On Range Searching with Semialgebraic Sets[END_REF].

We can associate with the polynomial family F the following Veronese mapping: Φ F : R m → R b , where Φ F (X) = (f 1 (X), . . . , f b (X)) .

It is easy to see that if there exists a set of points S in R m and a nonzero polynomial f (X) ∈ F such that S ⊆ Z(f (X)), where Z(f (X)) ⊆ R m denotes the zero set of the polynomial in R m , then there exists a hyperplane H in R b with Φ F (S) ⊂ H.

The following result is a direct consequence of above construction and Lemma 5.4. Lemma 5.6. Let F ⊆ R[X 1 , . . . , X m ] be a family of non-zero polynomials obtained by linear combination of non-zero polynomials f 0 (X), f 1 (X), . . . , f b (X) where X = (X 1 , . . . , X m ), f 0 (X) = 1 and the polynomials f i (X) are linearly independent in R[X 1 , . . . , X m ]. Let P be a n-point set in R m such that for all non-zero polynomial f (X) ∈ F we have |Z(f (X)) ∩ P | ≤ .

(1) If = O(n 1/3 ), then there exists S ⊂ P of size such that S has at most d|S| (b + 1)-tuples in S and each of these (b + 1)-tuples are a subset of zero sets of some polynomials in F.

Conclusion

Our randomized algorithm for finding d-degenerate subgraphs of k-uniform hypergraphs inherits the analysis of Srinivasan and Shachnai [START_REF] Shachnai | Finding Large Independent Sets in Graphs and Hypergraphs[END_REF] for independent sets:

(i) The RandPermute algorithm runs in RNC, as long as d is polylogarithmic in the number of vertices and edges. (ii) Our proof technique generalizes to non-uniform hypergraphs. (iii) All our results generalize to the vertex-weighted scenario, where we want an induced d-degenerate subgraph of maximum weight.

It is interesting to ask if the RandPermute algorithm can be used to solve the conjecture of Beame and Luby [START_REF] Beame | Parallel Search for Maximal Independence Given Minimal Dependence[END_REF], which asks whether iterating the RandPermute algorithm always yields a maximal independent set.

Lemma 5. 3 (

 3 Lemma 4.5[START_REF] Cardinal | General position subsets and independent hyperplanes in d-space[END_REF]). Let P be a set of n-points in R m such that for any hyperplane H in R m , we have |P ∩ H| ≤ where = O( √ n). Then the number of cohyperplanar (m+1)-tuples in P is at most O(n m log ).

Lemma 5. 4 .

 4 Let P be a set of n points in R m such that for any hyperplane H in R m we have |P ∩ H| ≤ where = O( √ n). Then there exists S ⊂ P of size

Ω

  dn log such that S has at most d|S| (b + 1)-tuples in S each of which is a subset of zero set of some polynomials in F. (2) If = O( √ n) and the Veronese map Φ F : R m → R b restricted to the set P is injective, then there exists S ⊂ P of size Ω dn log

  Family of hyperplanes in R m : This family is a linear combination of the polynomials {X 1 , . . . , X m , 1}. A set P in R m is said to be in general position with respect to spheres if no more than m points of P lie on any given hyperplane. For example, see [BCKO08, EM90, ES95, ES97, BDG13].(3) Polynomials in R[X 1 , . . . , X m ] with degree bounded by D:

	BCKO08, EM90,
	ES95, ES97, BDG13].
	(2)

Their proof also yields an elementary proof of the main bound of Srinivasan and Shachnai[START_REF] Shachnai | Finding Large Independent Sets in Graphs and Hypergraphs[END_REF] without using correlation inequalities, though not explicitly stated.

Alon, Kahn and Seymour [AKS87] actually defined a d-degenerate graph as one where every subgraph has a vertex of degree less than d.

Acknowledgements. Kunal Dutta and Arijit Ghosh are supported by European Research Council under Advanced Grant 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions) and Ramanujan Fellowship (No. SB/S2/RJN-064/2015) respectively. Part of this work was done when Kunal Dutta and Arijit Ghosh were Researchers at Max-Planck-Institute for Informatics, Germany, supported by the Indo-German Max Planck Center for Computer Science (IMPECS).


Keywords: Resonant Tunneling Diodes, MOBILE, Multithreshold Threshold gate, nanopipelining

The basic building blocks for Resonant Tunnelling Diode (RTD) logic circuits are Threshold Gates (TGs) instead of the conventional Boolean gates (AND, OR, NAND, NOR) due to the fact that, when designing with RTDs, threshold gates can be implemented as efficiently as conventional ones, but realize more complex functions. Recently, RTD structures implementing Multi-Threshold Threshold Gates (MTTGs) have been proposed which further increase the functionality of the original TGs while maintaining their operating principle and allowing also the implementation of nanopipelining at the gate level. This paper describes the design of n-bit adders using these MTTGs. A comparison with a design based on TGs is carried out showing advantages in terms of latency, device counts and power consumption.

I. INTRODUCTION & BACKGROUND

Resonant tunnelling diodes (RTDs) are very fast non linear circuit elements which exhibit a negative differential resistance (NDR) region in their current-voltage characteristics (see Figure 1a) which can be exploited to significantly increase the functionality implemented by a single gate in comparison to conventional technologies, thus reducing circuit complexity [START_REF] Mazumder | Digital Circuit Applications of Resonant Tunneling Devices[END_REF]. Circuit applications of RTDs are mainly based on the MOnostable-BIstable Logic Element (MOBILE) [START_REF] Chen | InP-Based High Performance Monostable-Bistable Transition Logic Elements (MOBILEs) Using Integrated Multiple-Input Resonant-Tunneling Devices[END_REF], [START_REF] Maezawa | A New Resonant Tunneling Logic-Gate Employing monostable-bistable transition[END_REF]. The MOBILE, shown in Fig. 1a, is a rising edge triggered current controlled gate which consists of two RTDs connected in series and driven by a switching bias voltage . When is low both RTDs are in the onstate (or low resistance state) and the circuit is monostable. Increasing to an appropriate maximum value ensures that only the device with the lowest peak current switches (quenches) from the on-state to the off-state (the high resistance state). Output is high if the driver RTD is the one which switches and it is low if it is the load. Peak currents are proportional to RTDs areas. Assuming equal current densities, the smallest RTD is the one which switches. Logic functionality is achieved by embedding an input stage which modifies the peak current of one of the RTDs. An input stage com-posed of the series connection of an RTD and a FET transistor has been proposed [START_REF] Pacha | Threshold Logic Circuit Design of Parallel Adders Using Resonant Tunnelling Devices[END_REF]. This is the idea of the inverter MOBILE shown in Fig. 1b. Only when a logic one is applied to the gate of a transistor its associated RTD contributes to the NDR 2 current. RTDs areas are selected such that the relation of the peak currents of NDR 1 and NDR 0 depends on whether the external input signal is "1" or "0". Transistor are sized such that RTDs are the current limiting devices in the series connection of the RTD and the transistor. For high the output node maintains its value even if the input changes. That is, this circuit structure is self-latching allowing to implement pipeline at the gate level without any area overhead associated to the addition of the latches which allows very high throughtoutput.

1.This effort was partially supported by the Spanish Government under project TEC2004-02948/MIC.

V bias V bias V bias RTD 1 RTD 2 V out -1 -0.5 0.5 1 -2 -1 1 2 V RTD (V) I RTD (mA) peak current current valley peak voltage load driver NDR 1 NDR 2 x 1 V bias V out w1 A 1 A 2 A 21 Figure 1. MOBILE circuits, a) basic MOBILE, b) MOBILE inverter. (a) (b) V bias V in V bias
Using Multi-Threshold Threshold Gates in RTD-based Logic Design.

A Case Study 1

Héctor Pettenghi, María J. Avedillo, and José M. Quintana Instituto de Microelectrónica de Sevilla, CNM, Sevilla, SPAIN E-mail: {hector, avedillo, josem}@imse.cnm.es

Threshold logic [START_REF] Muroga | Threshold Logic and Its Applications[END_REF] is a computational model widely used in the design of RTD based circuits [START_REF] Pacha | Threshold Logic Circuit Design of Parallel Adders Using Resonant Tunnelling Devices[END_REF]. That is, the basic building blocks for RTD logic circuits are Threshold Gates (TGs) instead of the conventional Boolean gates (AND, OR, NAND, NOR). This is due to the fact that when designing with RTDs, threshold gates can be implemented as efficiently, in terms of performance and complexity, as conventional Boolean gates but realize more complex functions.

A TG or linear separable function is defined as a logic gate with n binary input variables, , one binary output , and for which there is a set of real numbers: threshold T and weights , such that its input-output relationship is defined as iff , and otherwise. Sum and product are the conventional, rather than the logical, operations. The set of weights and threshold can be denoted in a more compact vector notation way by . TGs are efficiently realized by resorting to the operation principle of the clocked series connection of a pair of RTDs (MOBILE). The functionality of the MOBILE inverter can be extended to the TG as depicted in Figure 2 showing the circuit structure for a generic threshold gate of two inputs , where represents a positive weight and represent a negative one [START_REF] Pacha | Threshold Logic Circuit Design of Parallel Adders Using Resonant Tunnelling Devices[END_REF]. The areas and are determinated by the threshold to be implemented, and the areas and B are selected according to the technology and to the required design trade-offs involving speed, power and robutness against parameter variations. Threshold gates with a larger number of inputs can be easily realized extending this topology.

More recently, RTD structures implementing Multi-Threshold Threshold Gates (MTTGs) [START_REF] Haring | Multi-Threshold Threshold Elements[END_REF] have been proposed which further increase the functionality of the original TGs while maintaining their MOBILE operating principle and associated advantages [START_REF] Avedillo | Beyond Threshold Logic: Multi-threshold Threshold Gates[END_REF], [START_REF] Avedillo | Multi-threshold Threshold Logic Circuit Design Using Resonant Tunneling Devices[END_REF], [START_REF] Pettenghi | Useful Logic Blocks Based on Clocked Series-Connected RTDs" Proceedings[END_REF], [START_REF] Pettenghi | New Circuit Topology for Logi Gates Based on RTDs[END_REF].

MTTGs are a generalization of the conventional TGs. Formally, A k-threshold MTTG is a logic element with n binary input variables, , one binary output , and for which there is a set of real numbers: thresholds , , and weights , such that its input-output relation is defined as: iff , with , ;

output is equal to zero otherwise. As in the TGs, the set of weights and thresholds can be denoted in a more compact vector notation way by .

There are a number of theoretical properties for MTTGs which suggest they can be extremely powerful in digital design [START_REF] Haring | Multi-Threshold Threshold Elements[END_REF]. In particular, any n-input switching function can be realized by a single MTTG with at most (2 n -1) thresholds simply assigning . Moreover, usually exponential weights and exponential number of thresholds are not required. Thus, from a logic point of view, the MTTG is a powerful concept. This paper describes the design of n-bit adders using RTDbased MTTGs. The rest of the paper is organized as follows. Section II describes an adder implemented by means of TGs and reported by Pacha et al [START_REF] Pacha | Threshold Logic Circuit Design of Parallel Adders Using Resonant Tunnelling Devices[END_REF]. Section III describes the proposed adder using MTTGs and the realization of tthese more powerful gates on the basis of the concept of the MOBILE. Section IV compares three-bit adders designed with each of the architectures.

II. ADDERS BASED ON TGS

Figure 3a shows the logic diagram of a nanopipelined carry propagation n-bit adder based on TGs reported in [START_REF] Pacha | Threshold Logic Circuit Design of Parallel Adders Using Resonant Tunnelling Devices[END_REF]. It is comprised of the chain of full adders (FAs) and MOBILE followers (latches) to support pipeline. The first FA has been simplified. Since the carry output of the FA is a threshold function, it is implemented by a single threshold gate. The sum output of a FAs is a three-input EXOR function, which is not linear separable, and thus require a network of TGs to be realized. It is implemented using a two stage network with four gates as depicted in Figure 3a. Figure 3b-e depict the TG based realizations for the two-input EXOR (Figure 3b), the FA (Figure 3c), the two-input AND (Figure 3d) and latches (Figure 3e). Bias signals to operate cascaded MOBILE-type circuits are also shown (Figure 3f). A four phase (evaluation, hold, reset and wait) overlapping clocking scheme is used. Note that second stage (V bias2 ) evaluates while the first stage (V bias1 ) is in the hold phase. For a number of logic levels greater than three, four bias signals are required. In one clock period all the gates are activated. Data can be processed at a frequency determined by the operation speed of four chained MOBILE gates.

x i i 1 … n , , = ( ) , y n 1 + (
)

w 1 w 2 … w n , , , y 1 = w i x i i 1 = n ∑ T ≥ y 0 = w 1 w 2 … w n ; T , , , [ ] w k w l ; T , [ ] w k w l A 1 A 2 A u A 1 B + ( )A u V bias y x l x k w k A u w l A u Figure 2.-Circuit structure for . w k w l ; T , [ ] A 2 B + ( )A u x i i 1 … n , , = ( ) , y n k + (
) ,,,[ ]

T i i 1 … k , , = ( ) w 1 w 2 … w n , , , y 1 = T 2j 1 - w i x i T 2j < i 1 = n ∑ ≤ T j 1 + T j > j 1 … k 2 ⁄ , , = ( ) y w 1 w 2 … w n ; T 1 … T k , ,
w i 2 i 1 - =

III. ADDERS BASED ON MTTGS

Figure 4a depicts the circuit topology we have proposed for a generic MTTG with positive weights defined by , i.e., two inputs and two thresholds [START_REF] Avedillo | Multi-threshold Threshold Logic Circuit Design Using Resonant Tunneling Devices[END_REF]. The specific function implemented by such a circuit depends on the areas of the RTDs. The concept of RTD-based MOBILE is extended to a circuit consisting of three or more RTDs in series. The switching sequence in series-connected RTDs begins also with the RTD with the smallest peak current [START_REF] Chen | An Exclusive-OR Logic Circuit Based on Controlled Quenching of Series-Connected Negative Differential Resistance Devices[END_REF]. If this peak current can be controlled by external inputs, this sequence can be varied and different functions can be obtained at the output nodes.

Figure 4b depicts a more efficient alternative realization of two input two threshold MTTGs [START_REF] Pettenghi | New Circuit Topology for Logi Gates Based on RTDs[END_REF]. Circuit in Figure 4a operates on the basis of current comparison: the NDR with the lowest peak current switches off. Inputs modulate the peak currents of both the bottom (NDR 2 ) and the middle (NDR 1 ) NDRs, although by a different amount since the areas of the RTDs of their associated input stages are different. Thus, concerning NDR 1 and NDR 2 , and assuming, without loss of generality, A 11 > A 21 (A 12 > A 22 ), the same result of the current comparison could be obtained if only NDR 1 is modulated with input stages with area A 11 -A 21 (A 12 -A 22 ) for input variable x 1 (x 2 ). That is what has been done in Fig- ure 4b. However, area relationships of NDR 1 and NDR 2 with NDR 0 must be kept for circuit in Figure 4b to implement the same functionality that circuit in Figure 4a. To achieve this, input stages of area equal to A 21 (A 22 ) for x 1 (x 2 ) common to both have been added to the proposed circuit. Note that the area of some RTDs is reduced with respect to the solution in Figure 4a, thus allowing to reduce the width of their associated transistors. ) and the second one is an MTTG which can be implemented by a single RTD gate extending the topology above described to four RTDs in series. The FA modifica-tion has been done to avoid using a three input EXOR which can not been implemented with the MTTG topology described. Additional latches (implemented as MOBILE buffers) and inverting latches (implemented as MOBILE inverters) are also required to support pipeline. Due to the fact that the proposed adder needs complemented inputs in the modified FAs, it is required to use an inverter in the last stage of the input latches.

w 1 w 2 ; T 1 T 2 , , [ ] & exor [111;2] S 0 A 0 B 0 A 1 B 1 C 2 C n-1 C n A n-1 B n-1 [111;1] [111;3] [1-11;1] S 1 FA S n-1 FA C 1 V bias1 x 2 x 3 x 1 V bias1 x 2 x 3 x 1 V bias1 x 2 x 3 x 1 V bias2 sum [1, 1, 1;2] [1, 1, 1;1] [1, 1, 1;3] [1, 1, -1;1] (c) V bias1 x 1 x 2 V bias1 x 1 x 2 V bias2 y [1, 1;1] [1, 1;2] [1, -1;1] V bias1 x 1 x 2 y
V bias1 V bias2 VBIAS V bias1 x 2 y (a) (b) (d) (e) (f)
Note that he circuit showed in Figure 3a requires a two-level network for the full adder while the architecture in Figure 5a

A 0 B 0 A 1 B 1 S 1 exor [111;2] Modified FA S n-1 C 2 C n-1 C n A n-1 B n-1 C 1 x 2 x 3 x 1 x 3 x 2 x 1 x 1 x 2 x 3 y V bias x 1 x 2 x 2 x 1 y 1 y 2 V bias y x 2 x 3 x 1 V bias x 1 y V bias x 1 x 2
(c) (d) ( e) ( f)
implements the modified full adder with a single level of gates. This means the latency of the proposed adder is reduced.

IV. COMPARISON Three-bit adders have been designed to operate up to 750MHz using each of the architectures in a non commercial but university InP technology in which RTD and transistors can be cointegrated [12]. Minimization of power has been the design target. Simulation results at the operating frequency of 750MHz are depicted in Figure 6. Figure 6a shows the results for the previously reported adder, Figure 6b shows the results for the proposed gate. Note that in this figure the carry is complemented although it can be obtained without complementation changing the majority gate [1, 1, 1; 2] of the last stage to [-1, -1, -1; -1] without increasing of the latency.

For three bit adders operating at 750 MHz the design based in TGs has 15% more devices, its latency is 33% larger and consumes 20% more power than the proposed in this work based on MTTGs.

V. CONCLUSIONS

In this paper a novel nanopipelined n-bit adder based on RTDs and HFET devices has been described. A comparative analysis has been carried between this proposed design and an adder previously reported. The proposed design has several advantages: lower number of transistors, smaller total area of RTDs, lower latency and lower power consumption. Nanopipelined architectures for multipliers and divisors recently reported [START_REF] Gupta | An Algorithm for Nano-pipelining of Circuits and Architectures for a Nanotechnology[END_REF] can take advantage of these advanced proposed adders.

Figure 3 .

 3 Figure 3. n-bit adder based on TGs. (a) logic diagram. (b) RTD-based realization of two-input EXOR. (c) RTD-based realization of FA. (d) RTD-based realization of two-input AND. (e) Latch. (f) Bias scheme for MOBILE circuits.

Figure

  Figure5adepicts the logic diagram of the proposed nanopipelining carry-propagation n-bit adder. Note that it uses modified full adders in which complemented inputs are processed. Each of them comprises only two logic gates (only one logic level): the three-input mayority and the three-input EXNOR. The first one is a TG ([1, 1, 1; 2]) and the second one is an MTTG which can be implemented by a single RTD gate extending the topology above described to four RTDs in series. The FA modifica-

Figure 4 .

 4 Figure 4.-Circuit structures for generic two-input two-threshold MTTG with positive weights.

Figure 5 .

 5 Figure 5. n-bit adder based on MTTGs. (a) logic diagram. (b) RTD realization of two-input EXOR. (c) RTD realization of three-input EXNOR. (d) RTD realization of Majority [111;2]. (e) inverting latch. (f) RTD realization of two-input NAND.

Figure 6 .

 6 Figure 6.-Simulations results for three-bit adders. (a) TG based. (b) MTTG based.

© TIMA Editions / ENS 2005 ISBN: 2-916187-02-2