Aspectos estruturais e algoritmicos de objetos combinatorios.

• Grant number: 96/04505-2
• Support Opportunities: Research Projects - Thematic Grants
• Start date: October 01, 1996
• End date: September 30, 2000
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Yoshiharu Kohayakawa
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• City of the host institution: São Paulo
• Associated research grant(s): 97/06472-7 - 1) circuit covers in series parallel mixed graphs. 2) approximation algorithms for packing problems with orthogonal rotations., AR.EXT; 96/12820-5 - 1) approximation algorithms for 3-d packing problems. 2) szemeredi's regulanity lemma for sparse grapys., AR.BR

Abstract

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)

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

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. (96/04505-2)

DE A MOREIRA‚ C.G.T.; KOHAYAKAWA‚ Y.. Bounds for optimal coverings. DISCRETE APPLIED MATHEMATICS, v. 141, n. 1, p. 263-276, 2004. (96/04505-2)

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. (96/04505-2)

KOHAYAKAWA‚ Y.; RÖDL‚ V.. . RANDOM STRUCTURES & ALGORITHMS, v. 22, n. 4, p. 359-434, 2003. (96/04505-2)

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. (96/04505-2)

KOHAYAKAWA‚ Y.; NAGLE‚ B.; RÖDL‚ V.. Hereditary properties of triple systems. COMBINATORICS PROBABILITY & COMPUTING, v. 12, n. 02, p. 155-189, 2003. (96/04505-2)

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. (96/04505-2)

SOARES‚ J.; STEFANES‚ M.A.. . ALGORITHMICA, v. 53, n. 1, p. 35-49, 2009. (96/04505-2)

LEE‚ O.; WAKABAYASHI‚ Y.. On the circuit cover problem for mixed graphs. COMBINATORICS PROBABILITY & COMPUTING, v. 11, n. 01, p. 43-59, 2002. (96/04505-2)

KOHAYAKAWA‚ Y.; PRÖMEL‚ H.J.; RÖDL‚ V.. Induced ramsey numbers. COMBINATORICA, v. 18, n. 3, p. 373-404, 1998. (96/04505-2)