**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# Istvan Tomon

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

People doing similar research (166)

Related publications (10)

Courses taught by this person

No results

Loading

Loading

Loading

Related research domains (4)

Rights are legal, social, or ethical principles of freedom or entitlement; that is, rights are the fundamental normative rules about what is allowed of people or owed to people according to some legal

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic opera

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

Related units (3)

Let P be a partially ordered set. The function La* (n, P) denotes the size of the largest family F subset of 2([n]) that does not contain an induced copy of P. It was proved by Methuku and Palvolgyi that there exists a constant C-P (depending only on P) such that La*(n,P) < C-P(left perpendicular n/2 right perpendicular n). However, the order of the constant C-P following from their proof is typically exponential in vertical bar P vertical bar. Here, we show that if the height of the poset is constant, this can be improved. We show that for every positive integer h there exists a constant c(h) such that if P has height at most h, then La* (n, P) = 2 vertical bar P vertical bar, then vertical bar F vertical bar

Dániel József Korándi, Istvan Tomon

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is the union of r comparability (or more generally, perfect) graphs, then either G or its complement contains a clique of size n(1/(r+1)). This bound is known to be tight for r = 1. The question whether it is optimal for r >= 2 was studied by Dumitrescu and Toth. We prove that it is essentially best possible for r = 2, as well: we introduce a probabilistic construction of two comparability graphs on n vertices, whose union contains no clique or independent set of size n(1/3+o(1)). Using similar ideas, we can also construct a graph G that is the union of r comparability graphs, and neither G nor its complement contain a complete bipartite graph with parts of size cn/(log n)(r). With this, we improve a result of Fox and Pach.

The Boolean lattice (2[n],subset of) is the family of all subsets of [n]={1,MIDLINE HORIZONTAL ELLIPSIS,n}, ordered by inclusion. Let P be a partially ordered set. We prove that if n is sufficiently large, then there exists a packing P of copies of P in (2[n],subset of) that covers almost every element of 2[n]: P might not cover the minimum and maximum of 2[n], and at most |P|-1 additional points due to divisibility. In particular, if |P| divides 2n-2, then the truncated Boolean lattice 2[n]-{ null ,[n]} can be partitioned into copies of P. This confirms a conjecture of Lonc from 1991.