Structural and algorithmic aspects of combinatorial objects

• 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
• Associated research 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/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)

(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)

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.; 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.. Regular pairs in sparse random graphs I. 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.; 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.. Algorithms for maximum independent set in convex bipartite graphs. 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)