Centro de Modelamiento Matemático, Universidad de Chile, Chile
A conjecture of Gyárfás says that given any colouring with r colours of the edges of the complete graph K_n on n vertices, there are r disjoint monochromatic paths that induce a partition of V(K_n). The conjecture is true for r\leq 3. Replacing paths with cycles, it is known that in general, the number of cycles needed is greater than r, but can be bounded by a function of r. (Here, single vertices/edges count as cycles.) For r=2, it is known that 2 paths/cycles suffice.
This talk gives an overview on the history and then describes some recent results
for bipartite and multipartite graphs, with fixed values of r. We also study
variants of the problem for r-local colourings, and for r-mean colourings. These
are joint results with Conlon, with Lang, with Lang and Schaudt, and with Schaudt.
Departamento de Ingeniería Industrial, Universidad de Chile, Chile
Consideremos un tablero de Young de una partición λ, esto es, n filas, todas alineadas a la izquierda, donde la fila i tiene un número λ_i de casillas. Decimos que el tablero es Latino si existe una manera de llenar las casillas de la fila i con los números 1, 2, ... , λ_i, y esto para cada fila, de tal forma de obtener números distintos en cada columna. Es fácil convencerse que no todos los tableros son Latinos. La Wide Partition Conjecture (WPC) es un intento por caracterizar los tableros que si lo son.
En esta charla mostraremos como la WPC puede expresarse en el contexto del "k-atom problem", un problema central en Tomografía Discreta. Usando esta formulación, encontramos una condición necesaria para que un tablero sea Latino. Probaremos que esta condición, que en general es más fuerte que la que aparece en la WPC, resulta ser equivalente a esta última para las instancias de la WPC. Además discutiremos un poco sobre como la WPC se relaciona con el "multicommodity flow problem" y un problema de descomposición de grafos bipartitios en emparejamientos perfectos.
Discrete Optimization Group, École Polytechnique Fédérale de Lausanne, Switzerland
Since many interesting polytopes in combinatorial optimization have an exponential number of facets, a common approach in polyhedral combinatorics is to look for extended formulations, i.e. higher-dimensional polyhedra (hopefully, with a "small" number of facets) whose projections onto the original space give the original polytope. In his seminal paper, Yannakakis showed a surprising connection between extended formulations and communication complexity. In particular, given a polytope P with associated slack matrix M, he proved that any deterministic communication protocol computing M provides an extended formulations for P with at most 2^c facets, where c is the complexity of the protocol. This implies that the binary logarithm of the extension complexity xc(P) of P - the minimum number of facets over all extended formulations of P - is upper bounded by the minimum complexity of all deterministic communication protocols computing M.
In this talk we show that this connection can be tightened further when we allow protocols to be randomized. We prove that log_2 xc(P) is, up to small constants, equal to the minimum complexity of a randomized communication protocol computing M in expectation. We exploit this novel connection to investigate the existence of a compact formulation for the matching polytope of the complete graph, a fundamental open problem in polyhedral combinatorics, by showing that such an extended formulation, if exists, cannot be obtained via a deterministic protocol.
Joint work with Samuel Fiorini, Roland Grappe, and Hans Raj Tiwary.
Department of Computer Science and Engineering, Texas A&M University
Optimization has played a key role in making the task of decision making from art to science in the past century. An important challenge that still remains is our ability to incorporate the uncertainty in our knowledge and risk-aversion in our objective. A simple but insightful example of this is encapsulated in the decision question: given a number of route choices, which shall I choose? Interestingly, this simple question (easily solvable in a deterministic setting) becomes highly non-trivial when we incorporate the uncertainty of delays and the individual’s risk-aversion. This primarily stems from the combinatorial nature of the problem coupled with the non-convexity of the objective.
In this talk I explain how to solve this risk-averse route planning problem, and mention how its solution has been adapted in the MIT CarTel system for routing, which incorporates real traffic information (cartel.csail.mit.edu). I then show how the solution extends to a general framework of risk-averse combinatorial optimization, for which I present exact and approximation algorithms. These general-purpose algorithms can also cope with combinatorial problems that are NP-hard, whose deterministic versions we only know how to approximate.
In the second part of the talk, I describe how the risk-averse framework provides a foundation for studying equilibria in stochastic network games. This talk will be accessible to a general audience and is based on parts of the following papers:
Biography
Evdokia Nikolova is an Assistant Professor at the Computer Science & Engineering Department at Texas A&M University. Previously she was a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory at MIT. She graduated with a BA in Applied Mathematics with Economics from Harvard University, MS in Mathematics from Cambridge University, U.K. and Ph.D. in Computer Science from MIT. She is interested in risk analysis from an algorithmic perspective arising in stochastic optimization, networks, economics and complex systems.
University of Warwick, United Kingdom
We study the complexity of the following problem: given a graph, find an induced matching containing a maximal independent set. This problem has applications in the study of topological properties of independence complexes of graphs, which are simplicial complexes whose faces are the independent sets of a graph.
Such a matching, if found, certifies that the topology of the independence complex is non-trivial. More topological information can be derived further if the matching is also of certain size (or minimal/maximal possible). Notably, for chordal graphs, such matchings encode complete information of the topology of the independence complex, which is not the case in general.
We prove that the problem of finding such a matching is NP-complete for general graphs, but in chordal graphs, it has a polynomial-time algorithm. Our algorithm is based on the geometric intersection representation of chordal graphs and has an efficient implementation. We further show that the exact-cardinality version of the problem remains NP-complete even on chordal graphs, but admits a polynomial time algorithm for bounded-leafage chordal graphs. Our hardness results are derived from the hardness of dominating set problems.
Previous best result in this area by Kawamura addresses the case of forests with a particularly complicated algorithm. Our approach implies a simple linear-time algorithm for forests improving significantly on this result.
As a corollary, we obtain polynomial time algorithms for such topological properties as contractibility or simple-connectedness of independence complexes of chordal graphs. These problems are undecidable for general independence complexes.
Joint work with Michal Adamaszek (University of Warwick).
UFRJ y UFF, Rio de Janeiro
Brasil
Characterizations by forbidden subgraphs and forbidden minors are common in Graph Theory. In fact, any closed set in a qoset can have such a characterization, but in the general case these can only be guaranteed by forbidding the complement of the set, and do not seem to lend themselves to any practical applications.
In this work, we begin a study of characterizations by forbidding sets which have nice properties, such as being minimal, finite, etc. More specifically, we characterize the qosets in which every closed set is characterizable by forbidding a minimal set, and show that the problem of determining whether a closed set in a general qoset has a finite forbidding set is undecidable. As a corollary, this problem, when restricted to the poset of finite graphs with the induced subgraph relation.
Joint work with Hugo Nobrega.
Department of Combinatorics and Optimization
Faculty of Mathematics
University of Waterloo
Canada
Semidefinite programming (SDP) is one of the most active research areas in optimization where the variables are represented by symmetric matrices some of which are required to be positive semidefinite. This framework ends up being a powerful generalization of linear programming problems.
Lift-and-project methods provide universal ways of applying SDP techniques to combinatorial optimization problems. I will go over the theory of these methods first. Then, I will turn to their performance on various combinatorial optimization problems with a special focus on the max. weight stable set problem.
I will conclude the talk with a very brief discussion of generalizations of these methods to deal with optimization of polynomials over semi-algebraic sets.