\documentclass{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\def\FAPESP{\textsc{fapesp}}
\def\CNPq{\textsc{cnp}q}
\def\CAPES{\textsc{capes}}
\def\CAPESDAAD{\textsc{capes-daad}}
\def\CAPESCOFECUB{\textsc{capes-cofecub}}
\def\DAAD{\textsc{daad}}
\def\GMD{\textsc{gmd}}
\def\FINEP{\textsc{finep}}
\def\MCT{\textsc{mct}}



\newcommand{\dmoldura}[1]{{\noindent\fbox{\fbox{\parbox[t]{14.0cm}{ #1 }}}\vspace*{.5cm}}}

% 
\setlength{\parindent}{0ex}
\setlength{\parskip}{0.5pc}
\setlength{\textwidth}{14.4cm}
\setlength{\textheight}{19 cm}
% \setlength{\topmargin}{0.3cm}
% \setlength{\headheight}{0cm}
% \setlength{\headsep}{0cm}
 \setlength{\oddsidemargin}{0.8cm}
 \setlength{\evensidemargin}{0.8cm}

                %%%%%%%%%%%%%%%%%% para Bolsa Pesquisa CNPq %%%%%%%%%%%%%%%%%%%%
\begin{document}
\centerline { \bf {\sc ANEXO}} 
\begin{center}
\dmoldura{
\centerline {\phantom{a} }
\centerline {\Large \bf {\sc Workshop on Combinatorics, Algorithms, and
    Applications }} 

\centerline { {1 a 5 de setembro de 2003}}
\centerline {{Ubatuba, SP}}
\centerline{\phantom{a}}
}
\end{center}

%\vspace{0.3cm}

\centerline{\large RESUMO DAS PALESTRAS}

\bigskip 
\bigskip

\bigskip

\centerline {\large \bf Union-Closed Set Systems and Geometric Lattices}
    
\bigskip

\centerline {Dwight Duffus} % Emory University


P. Frankl's conjecture regarding union-closed set systems -- that some element
in the underlying set is in at least half the sets in the system -- has
immediate translation as a natural problem for finite lattices.  Attempts to
solve the conjecture in this context have led, not surprisingly, to partial
results for special classes of lattices.  We describe one attempt to attack
the conjecture using Dilworth's result on embedding lattices in geometric
lattices.  This is joint work with B. Sands [University of Calgary] and R.
Roth [Emory University].


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip

\medskip

 
\centerline {\large \bf  Random Walks on Random Graphs}
\bigskip

\centerline {Alan Frieze}

We give tight estimates for the cover time of random graphs and random regular
graphs. We also give estimates for the number of vertices visited in a random
walk on a randomly growing "web-graph".
This is joint work with Colin Cooper.


\bigskip

\medskip


\centerline {\large \bf  Virtual Knot Theory}

\bigskip

\centerline{ Louis H. Kauffman}


Virtual knot theory is a generalization of classical knot theory to
the study of abstract oriented Gauss codes modulo Reidemeister moves.  A
diagrammatic representation of virtual knots is obtained by extending
classical knot diagrams to include virtual crossings that are neither
undercrossings nor overcrosssings. The theory can be characterized by a set of
moves on these extended diagrams. Virtual knot theory is equivalent to the
study of knots and links in thickened oriented surfaces stabilized by the
addition and subtraction of empty handles. Many classical invariants
generalize to invariants of virtual knots and links, with interesting
variations. The talk will discuss virtual knots with unit Jones polynomial,
detecting classicality of virtual knots, quantum invariants of virtual knots,
quandles and biquandles, Vassiliev invariants and the structure of virtual
three-manifolds.

\bigskip
\newpage


\centerline {\large \bf Social networks in knowledge management}

\bigskip

\centerline{Prabhakar Raghavan}

Beginning with Milgram's classic ``six degrees of separation'' experiments in
the 1960's, social network theory has evolved to study how individuals
interact and disseminate information. More recently, the study has come to
encompass the broader network involving people as well as the documents and
information they interact with - examples include recommendation systems and
the use of link analysis in web search engines. This talk will provide an
overview of this evolving area and the many research problems that arise,
including issues in privacy protection.



\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\centerline {\large \bf The Total Colouring Conjecture}


 \bigskip

\centerline{ Bruce Reed}



A total colouring of a graph is a colouring of its vertices and
edges so that no two adjacent vertices get the same colour. No two adjacent
edges get the same colour, and no edge gets the same colour as an endpoint.  A
total colouring of a graph of maximum degree Delta clearly requires at least
Delta + 1 colours. The Total Colouring Conjecture, formulated by Behzad and
Vizing independently, states that Delta +2 colours always suffice.
We present some partial evidence for this conjecture. 

%%%%%%%%%%%%%%%%%%%%%%%%

 \bigskip

\centerline {\large \bf Components and Primes}

\bigskip

\centerline { Bruce Richmond} %  <lbrichmo@pythagoras.math.uwaterloo.ca>

\medskip

There is an analogy between the prime factors of the first n integers and the
components of combinatorial objects of size $n$. The objects may be
permutations which may be factored into cycles. The objects may be polynomials
over a finite field which can be factored into into irreducible polynomials.
The unique factorization gives an analogy between generating functions but
more is true. The probability that the first $n$ integers have largest prime
factor $\le m$ is asymptotic to the Dickman function evaluated at $\log n/\log
m$ for $m$ sufficiently small compared to $n$. The probability that the
smallest prime factor of the first $n$ integers is $\ge m$ is asymptotic to
the Buchstab function evaluated at $\log n/\log m$ divided by $\log m$. We can
obtain the corresponding probabilities for combinatorial objects by replacing
$\log n$ and $\log m$ by $n$ and $m$. This was pointed out by
Billingsley(1972) and Knuth and Trabb-Pardo(1976). Gourdon established this
analogy for the largest component using the Flajolet-Odlyzko singularity
analysis for general classes of combinatorial objects. Panario and Richmond
followed with the analogy for the smallest component. Recently the Buchstab
and Dickman original recur!  sive arguments have been adapted to combinatorial
objects by Bender,Mashatan,Panario and Richmond. When the objects are
2-regular graphs new Buchstab and Dickman functions arise.These results will
be surveyed.



%%%%%%%%%%%%%

 \bigskip


\centerline {\large \bf Chromatic numbers and configurations in graphs}


 \bigskip

\centerline {Carsten Thomassen}% , Technical University of Denmark.

Hajos' conjecture from 1961 says that every graph of chromatic
number $k$ contains a subdivision of the complete graph on $k$ vertices. The
conjecture was disproved in by Catlin in 1979 for all $k$ greater than 6. We
relate this conjecture to other aspects of graph theory and we discuss also in
detail the case $k=4$. In this case a stronger version of the conjecture holds:
Every 4-chromatic graph contains a subdivision of the complete graph on 4
vertices such that all six edges correspond to odd paths, a conjecture made by
Toft in 1975 and proved independently by Wenan Zang and the present lecturer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 


 \bigskip

\centerline {\large \bf Certificates and Graph Algorithms}

\bigskip

\centerline {Jerry Spinrad}

\medskip

The notion of a certificate for a property, which is due to Edmonds,
arises frequently in complexity theory. A certificate is a proof that
a property holds, and the length of a certificate may be much shorter
than the time needed to find such a certificate.

This talk will discuss three different areas of graph algorithms, in which
certificates have played crucial roles.

The first is the notion of a robust algorithm. A robust algorithm to
solve a problem on a class of inputs must solve the problem correctly
if the input is in the class, and if the input is not in the class may either
solve the problem correctly or answer that the input is not valid.

The second type of problem related to certificates involves using
matrix multiplication to improve asymptotic running times of algorithms.
Matrix multiplication is used to improve time bounds for such problems 
as finding minimal fill, two-pairs, asteroidal triples, and a variety 
of other problems on graphs.

A third area where certificates arise is a certifying algorithm,
which is required to produce output such that the answer is "easy" to
verify.

%%%%%%%%%%%%%%%%%

\bigskip

\centerline {\large \bf  Analysis of Rabin's irreducibility test for 
       polynomials over finite fields}

 \bigskip

\centerline{Alfredo Viola}


We give a precise average-case analysis of Rabin's algorithm for testing the
irreducibility of polynomials over finite fields. The main technical
contribution of the paper is the study of the probability that a random
polynomial of degree $n$ contains an irreducible factor of degree dividing
several maximal divisors of the degree $n$. We then study the expected value
and the variance of the number of operations performed by the algorithm. We
present an exact analysis when $n=p_1$ and $n=p_1p_2$ for $p_1,p_2$ prime
numbers, and an asymptotic analysis for the general case. Our method
generalizes to other algorithms that deal with similar divisor conditions. In
particular, we analyze the average-case number of operations for two variants
of Rabin's algorithm, and determine the ordering of prime divisors of $n$ that
minimizes the leading factor.

The emphasis of the talk will be on the combinatorial aspects of the problem.
This is joint work with Daniel Panario, Boris Pittel and Bruce Richmond.


\end{document}

