Lunch Seminar MESIO UPC-UB

Speaker:

Abstract:

Volem saber si un graf amb molts vèrtexs i moltes arestes té algun triangle. Aquesta és una propietat local i una resposta definitiva pot requerir una exploració de tot el graf. Si en tenim prou de saber que el graf no està lluny de no tenir triangles de sobte descobrim (amb gran fascinació) que n’hi ha prou amb analitzar una sola mostra.

Aquesta estratègia, que s’aplica a estructures combinatòries i algebraiques bastant generals, es coneix amb el nom de Property Testing. En el cas de grafs densos està relacionat amb un resultat cèlebre, el teorema de Szemerédi, que es pot descriure dient que una classe ampla d’estructures combinatòries   (un graf, per exemple) té una component aleatòria i una component estructurada que es poden analitzar per separat. El Property Testing explota aquesta dualitat per plantejar un mètode de mostreig de propietats d’una eficàcia inusual. Tot i que l’èxit d’aquesta estratègia es basa en la naturalesa de l’univers que s’explora, té un àmbit d’aplicació sorprenentment ampli. El pla de la xerrada és exposar l’estratègia general, avaluar-ne l'eficàcia i ilustrar-la amb alguns exemples..