Advanced search
Start date

Structural and algorithmic aspects of combinatorial objects


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)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

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: