Speaker:
Siemion Fajtlowicz
Title:
Automated Conjectures
Abstract:
I will discuss philosophical, mathematical and educational aspects
of automated conjectures based on experiences with Graffiti - a computer
program which has inspired many papers, several by very well-known
mathematicians. Philosophical and mathematical issues are related to
Penrose's "Shadows of the Mind" and his controversial claim that
computers can not have human mathematical intuitions. I will also
discuss
conjectures of the chemistry version of Graffiti which suggest that
stable fullerenes tend to minimize their maximum independent sets and
that
they tend to be good expanders as well as the latest conjectures of
Graffiti about
diamondoids.
|
Speaker:
Lisa Fleischer
Title: How to Influence Noncooperative, Selfish Agents
Abstract:
The societal value of a distribution of finite resources is frequently
measured in terms of of aggregate utility. Decisions, however,
are frequently controlled by noncooperative agents who try to
maximize their own private utility.
Papadimitriou coined the term "price of anarchy"
to refer to the ratio of social utility achieved by
selfish agents versus the social optimal.
The network routing game was proposed by Wardrop in the 1950's
to model traffic flow. For this game, the price of anarchy
can be arbitrarily bad. We review these results, and then
describe some solutions to prevent this bad outcome. These
include charging users for network use; and
managing a small portion of traffic wisely. Some of these
results carry over to more general congestion games.
|
Speaker:
Pavol Hell
Title: FULL COLOURING, HOMOMORPHISM, AND
CONSTRAINT SATISFACTION PROBLEMS
Abstract:
I will discuss colouring type problems in which
the inputs have a restricted structure. These
restrictions (`fullness' of various kinds) include
variables having lists (of allowed values), or
pairs of variables being in binary relations, etc.
List colourings, list homomorphisms, and list
matrix partitions are typical examples of full
problems. The latter occur naturally in many
constructions associated with the study of
graph perfection. I will describe some simple
full problems for which the complexity is an
open question. I will also discuss a new kind
of chromatic number associated with full problems.
Most of the work is joint with Tomas Feder, some
with Xuding Zhu.
|
Speaker:
Frank Hsu
Title: Information-based Combinatorial Fusion
Abstract:
In applications such as figure skating, information retrival and
structure-based drug discovery in virtual screening, information from
multi-sources and/or multi-sensors have to be combined/fused to derive
better results, to come up with better estimates, or to make better
decisions. In this talk, we discuss rank function, score function,
rank combination, score combination, and rank/score graph. We then use the
Cayley graph G(S(sub n), P(sub n)) as the rank space to pursue better
combination/fusion. Some open problems will be also addressed.
This talk is , and should be ,considered as applications of combinatorics
to some fundamental issues in the new emerging field of Informatics.
|
Speaker:
Daniel Panario
Title:
Largest and smallest components in combinatorial
decomposable structures
Abstract:
In this talk we first review the relation between objects and
components, and we focus on extremal sizes of components.
We give several properties of largest and smallest components
of decomposable combinatorial objects. Examples of these
structures are: permutations; $2$-regular graphs; random
mappings (functional digraphs); permutations with particular
characteristics (e.g. permutations without cycles of length
one); children's yards; polynomials over finite fields;
random mappings patterns; squarefree polynomials over finite
fields (without repeated irreducible factors); arithmetical
semigroups; etc.
Then, we concentrate on the probability of connectedness
for structures of size n when all components must have
size at least m. In the border between almost certain
connectedness and almost certain disconnectedness, we
encounter a generalized Buchstab function.
[Based on joint works with Bruce Richmond (2001) and
Ed Bender, Atefeh Mashatan and Bruce Richmond (2004).]
|
Speaker:
Jozsef Solymosi
Title: Affine Cubes of Integers
Abstract:
In 1892 Hilbert proved that for any partitioning of the
natural numbers into finitely many classes, one class will contain
arbitrary large affine cubes. A set of integers S is called an
affine d-cube, if there are d+1 natural numbers x_0,x_1, ... ,x_d
such that S={x_0+Sum_{i \in I}x_i : for every I \subset [1,d]}.
This theorem has many generalizations, the most popular ones are
the van der Waerden and Shur theorems. However, affine cubes are
still very useful objects which (unlike arithmetic progressions)
can be found in sparse sets of integers. After reviewing the basic
properties of the affine cubes, we show an efficient algorithm
to find them.
|
Speaker:
Frank Sottile
Title:The Horn recursion in the Schubert calculus
Abstract:
A consequence of Knutson and Tao's proof of the saturation
conjecture is a conjecture of Horn, which implies that the
non-vanishing of Littlewood-Richardson numbers is recursive:
A Littlewood-Richardson number is non-zero if and only if
its partition indices satisfy the Horn inequalities imposed
by all `smaller' non-zero Littlewood-Richardson numbers.
A way to express this Horn Recursion is that non-vanishing
in the Schubert calculus of a Grassmannian is controlled by
non-vanishing in the Schubert calculus of all smaller Grassmannians.
In joint work with Kevin Purbhoo, we have extended this
Horn recursion to the cominuscule Schubert calculus.
Our results are interesting even for the Grassmannian,
as the inequalities we obtain are different than the Horn
inequalities. We also obtain two completely different
sets of inequalities for the analogs of Littlewood-Richardson
numbers for Schur P- and Q- functions.
In this talk, I will first discuss the classican Horn recursion,
which was about the eigenvalues of sums of Hermitian matrices,
and then relate this to the combinatorics of Littlewood-
Richardson numbers from representation theory and Schubert
calculus, explaining the Horn inequalities. Next, I
wil explain the combinatorial consequences of this work with
Purbhoo, in particular giving the inequalities we obtain.
|
Home |
Speakers |
Schedule |
Abstracts |
Support |
Registration |
Directions |
Lodging |
Acknowledgment|
URL: /~cyan/combinatexas
Copyright ©2004 by
Catherine Yan
Last Modified on
31/Jan/05. |