Faits: A. L'extrémité du périmètre compris entre le chemin G._ et la route H._, à Sion, fait l'objet d'un plan de structuration adopté le 21 avril 2005 par le Conseil municipal de Sion. Il comprend actuellement les parcelles nos 16092 à 16097 et 16099 sur lesquelles ont été édifiées cinq villas mitoyennes, un immeuble de quatre appartements et un garage, le tout formant un lotissement dénommé "Les Jardins de Gravelone" (ci-après: le lotissement). Il s'y trouve également les parcelles n° 16259 (avec un immeuble de huit appartements), 16335 (avec une villa individuelle) et, en son centre, la parcelle n° 11630, non bâtie et appartenant à Y._. Un dépassement de la densité admissible (soit 0,5) a été constaté sur le périmètre du lotissement, nécessitant une compensation équivalant à 390 m2 de surface dans le périmètre du plan de structuration. Au mois d'avril 2008, une modification du périmètre du plan a été mise à l'enquête, portant sur l'adjonction de la parcelle n° 5254, non bâtie, située au nord-ouest. Elle fit l'objet de l'opposition de E._ et F._, C._ et D._, A._ et B._ (ci-après: les opposants), tous propriétaires de parts de PPE d'immeubles situés dans le lotissement. Ces oppositions furent rejetées le 10 juin 2009 par le Conseil municipal de la ville de Sion, et celui-ci adopta le nouveau plan de structuration avec pour condition, notamment, l'inscription d'une servitude de non-bâtir de 390 m2 sur la parcelle n° 11630 en faveur des parcelles constituant le lotissement et de la ville de Sion. Cette décision a fait l'objet, d'une part, d'un recours formé par Y._, qui s'opposait à l'inscription d'une servitude grevant sa parcelle et, d'autre part, de quatre recours formés par les opposants précités, qui contestaient l'intégration de la parcelle n° 5254. B. Par décision du 22 juin 2011, le Conseil d'Etat valaisan a admis le recours de Y._. Ce dernier n'avait jamais consenti à une cession de droits à bâtir en faveur des parcelles situées à l'est et aucune disposition légale ne permettait, en dehors d'une procédure d'expropriation, de déposséder un propriétaire de l'indice d'utilisation de sa parcelle. Le transfert de densité étant une condition sine qua non à l'intégration de la parcelle n° 5254, l'ensemble de la décision municipale a été annulée. Par décision du même jour, le Conseil d'Etat a également admis le recours formé par les opposants. Il a constaté la nullité de la décision du Conseil communal, car l'extension du périmètre du plan de structuration était de la compétence du Conseil général. La parcelle n° 5254 se trouvait dans une zone différente (zone individuelle coteau sensible), de sorte qu'une cession de densité n'était pas possible. C. Par arrêt du 13 janvier 2012, La Cour de droit public du Tribunal cantonal valaisan a rejeté le recours formé par les opposants contre la décision du Conseil d'Etat admettant le recours de Y._. Les recourants persistaient à demander l'inscription d'une servitude de densité grevant la parcelle n° 11630, une telle servitude ayant été promise par Y._ en sa qualité de promoteur immobilier et imposée dans deux décisions rendues en 2007. La Cour de droit public a considéré qu'indépendamment des éventuelles promesses faites par Y._, celui-ci avait toujours refusé de grever sa parcelle et ne pouvait y être contraint selon le droit public. Par ailleurs, la décision du 10 juin 2009 ayant été annulée, la condition qui y était liée n'avait plus de raison d'être. Enfin, lors de ses séances des 6 et 20 septembre 2007, le Conseil municipal n'avait pris aucune décision contraignante à l'égard de Y._. D. Par acte du 16 février 2012, les opposants, soit A._, B._, C._ et D._, F._ et E._ forment un recours en matière de droit public par lequel ils demandent l'annulation de l'arrêt cantonal et l'inscription d'une servitude de non-bâtir à charge de la parcelle n° 11630, en faveur des fonds constituant le lotissement et de la ville de Sion. La cour cantonale a renoncé à se déterminer. Le Conseil d'Etat conclut au rejet du recours. Y._ conclut au rejet du recours dans la mesure où il est recevable. A l'invitation du Tribunal fédéral, l'avocat des recourants a produit les procurations en sa faveur, à l'exception de celle de D._ qui fait défaut. 