Advanced search
Start date

Structural and algorithmic aspects of combinatorial objects

Grant number: 96/04505-2
Support type:Research Projects - Thematic Grants
Duration: October 01, 1996 - September 30, 2000
Field of knowledge:Physical Sciences and Mathematics - Computer Science
Principal Investigator:Yoshiharu Kohayakawa
Grantee:Yoshiharu Kohayakawa
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated grant(s):97/14469-6 - Robin Thomas | Georgia Institute of Technology - United States, AV.EXT
97/06472-7 - 1) circuit covers in series parallel mixed graphs. 2) approximation algorithms for packing problems with orthogonal rotations, AR.EXT
96/12111-4 - Bruce Reed | Centre National de la Recherche Scientifique - France, AV.EXT
96/12820-5 - 1) approximation algorithms for 3-D packing problems. 2) szemeredi's regulanity lemma for sparse grapys, AR.BR


The main aim of this thematic project is to investigate structural aspects of combinatorial objects. The specific aspects to be considered are the ones motivated by (i) their intrinsic mathematical interest, and by (ii) their importance for the design of efficient algorithms for computational problems of combinatorial nature, and for the proof of lower bounds for the computational complexity of such problems. The main research themes in this project are the following: 1. asymptotic properties of combinatorial structures, investigated through combinatorial and extra-combinatorial methods, such as probabilistic, algebraic, and topological methods. 2. structural properties of graphs, hypergraphs, and related structures. 3. geometric problems and methods in combinatorics, with special emphasis on polyhedral methods in combinatorial optimization. A list of specific research topics, which is not meant to be comprehensive but only illustrative, is the following: numerical problems in Ramsey theory, Turán type extremal problems, asymptotic enumeration of graphs, pseudorandom objects and their applications, algebraic and topological methods, Hilbert bases, data compression, 3-dimensional packing, polyhedral methods in combinatorial optimization, approximation algorithms. (AU)

Scientific publications (10)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
SOARES‚ J.; STEFANES‚ M.A. Algorithms for maximum independent set in convex bipartite graphs. ALGORITHMICA, v. 53, n. 1, p. 35-49, 2009.
DE A MOREIRA‚ C.G.T.; KOHAYAKAWA‚ Y. Bounds for optimal coverings. DISCRETE APPLIED MATHEMATICS, v. 141, n. 1, p. 263-276, 2004.
KOHAYAKAWA‚ Y.; NAGLE‚ B.; RÖDL‚ V. Hereditary properties of triple systems. COMBINATORICS PROBABILITY & COMPUTING, v. 12, n. 02, p. 155-189, 2003.
KOHAYAKAWA‚ Y.; RÖDL‚ V. Regular pairs in sparse random graphs I. RANDOM STRUCTURES & ALGORITHMS, v. 22, n. 4, p. 359-434, 2003.
DONADELLI, JAIR; KOHAYAKAWA, YOSHIHARU. A density result for random sparse oriented graphs and its relation to a conjecture of Woodall. ELECTRONIC JOURNAL OF COMBINATORICS, v. 9, 2002. Web of Science Citations: 1.
LEE‚ O.; WAKABAYASHI‚ Y. On the circuit cover problem for mixed graphs. COMBINATORICS PROBABILITY & COMPUTING, v. 11, n. 01, p. 43-59, 2002.
VAN DER HOLST‚ H.; DE PINA‚ JC. Length-bounded disjoint paths in planar graphs. DISCRETE APPLIED MATHEMATICS, v. 120, n. 1, p. 251-261, 2002.
KOHAYAKAWA‚ Y.; KREUTER‚ B.; OSTHUS‚ D. The length of random subsets of Boolean lattices. RANDOM STRUCTURES & ALGORITHMS, v. 16, n. 2, p. 177-194, 2000.
KOHAYAKAWA‚ Y.; KREUTER‚ B.; STEGER‚ A. An extremal problem for random graphs and the number of graphs with large even-girth. COMBINATORICA, v. 18, n. 1, p. 101-120, 1998.
KOHAYAKAWA‚ Y.; PRÖMEL‚ H.J.; RÖDL‚ V. Induced ramsey numbers. COMBINATORICA, v. 18, n. 3, p. 373-404, 1998.

Please report errors in scientific publications list by writing to: