Combinatorics | EPFL Graph Search

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science. Combinatorics is well known for the breadth of the problems it tackles. Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry, as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is graph theory,

On the power of combinatorial and spectral invariants

We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the eigenspaces (in addition to the usual angles between standard basis vectors and eigenspaces). The exact power of the new invariant is still an open problem. We also define combinatorial invariants based on standard graph isomorphism heuristics and compare their strengths with the spectral invariants. In particular, we show that a simple edge coloring invariant is at least as powerful as all these spectral invariants. (C) 2009 Elsevier Inc. All rights reserved.

2010

Combinatorics For General Kinetically Constrained Spin Models

Laure Irène Marêché

We study the set of possible configurations for a general kinetically constrained model (KCM), a nonmonotone version of the U-bootstrap percolation cellular automata. We solve a combinatorial question that, is a generalization of a problem addressed by Chung, Diaconis, and Graham [Adv. in Appl. Math., 27 (2001), pp. 192-206] for a specific one-dimensional KCM, the East model. Since the general models we consider are in any dimension and lack the oriented character of the East dynamics, we have to follow a completely different route than the one taken by Chung, Diaconis, and Graham. Our combinatorial result is used by Mareche, Martinelli, and Toninelli to complete the proof of a conjecture put forward by Morris.

SIAM PUBLICATIONS2020

On some problems related to 2-level polytopes

Manuel Francesco Aprile

In this thesis we investigate a number of problems related to 2-level polytopes, in particular from the point of view of the combinatorial structure and the extension complexity. 2-level polytopes were introduced as a generalization of stable set polytopes of perfect graphs, and despite their apparently simple structure, are at the center of many open problems ranging from information theory to semidefinite programming. The extension complexity of a polytope P is a measure of the complexity of representing P: it is the smallest size of an extended formulation of P, which in turn is a linear description of a polyhedron that projects down to P. In the first chapter, we examine several classes of 2-level polytopes arising in combinatorial settings and we prove a relation between the number of vertices and facets of such polytopes, which is conjectured to hold for all 2-level polytopes. The proofs are obtained through an improved understanding of the combinatorial structure of such polytopes, which in some cases leads to results of independent interest. In the second chapter, we study the extension complexity of a restricted class of 2-level polytopes, the stable set polytopes of bipartite graphs, for which we obtain non-trivial lower and upper bounds. In the third chapter we study slack matrices of 2-level polytopes, important combinatorial objects related to extension complexity, defining operations on them and giving algorithms for the following recognition problem: given a matrix, determine whether it is a slack matrix of some special class of 2-level polytopes. In the fourth chapter we address the problem of explicitly obtaining small size extended formulations whose existence is guaranteed by communication protocols. In particular we give an algorithm to write down extended formulations for the stable set polytope of perfect graphs, making a well known result by Yannakakis constructive, and we extend this to all deterministic protocols.

EPFL2018

On some problems related to 2-level polytopes

Manuel Francesco Aprile

EPFL2018