**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Michal Lason

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related publications (6)

Loading

Loading

Loading

People doing similar research (4)

Related units (1)

Courses taught by this person

No results

Related research domains (2)

Intersection graph

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special c

Clique problem

In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several d

Michal Lason, Bartosz Maria Walczak

For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing vectors in Z(w)? We state a conjecture that the answer is k(w-1). We prove the conjecture for w = 4. Also, for all k and so, we construct several quite different examples of families of desired size k(w-1). This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set. (C) 2019 Elsevier Inc. All rights reserved.

The well-known "necklace splitting theorem" of Alon (1987) asserts that every k-colored necklace can be fairly split into q parts using at most t cuts, provided k(q - 1) t + 2 is a sufficient condition (while k > t is necessary). We generalize this result to Euclidean spaces of arbitrary dimension d, and to arbitrary number of parts q. We prove that if k(q - 1) > t + d + q - 1, then there is a measurable k-coloring of R-d such that no axis-aligned cube has a fair q-splitting using at most t axis-aligned hyperplane cuts. Our bound is of the same order as a necessary condition k(q - 1) > t implied by Alon's 1987 work. Moreover, for d = 1, q = 2 we get exactly the result of the 2009 work. Additionally, we prove that if a stronger inequality k(q - 1) > dt + d + q - 1 is satisfied, then there is a measurable k-coloring of R-d with no axis-aligned cube having a fair q-splitting using at most t arbitrary hyperplane cuts. The proofs are based on the topological Baire category theorem and use algebraic independence over suitably chosen fields.

We answer several questions posed by Beck, Cox, Delgado, Gubeladze, Haase, Hibi, Higashitani, and Maclagan in [Cox et al. 14, Question 3.5 (1),(2), Question 3.6], [Beck et al. 15, Conjecture 3.5(a),(b)], and [Hasse et al. 07, Open question 3 (a),(b) p. 2310, Question p. 2316] by constructing a new family of non-normal very ample polytopes. These polytopes are certain segmental fibrations of unimodular graph polytopes, we explicitly compute their invariants - Hilbert function, Ehrhart polynomial, and gap vector.