Home | Speakers | Schedule | Abstracts | Support | Registration | Directions | Lodging | Acknowledgment|





CombinaTexas: Combinatorics in the South-Central U.S.
February 25--26, 2005
Texas State University -San Marcos



Abstracts
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.