**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.

Publication# Forbidden induced subposets of given height

Abstract

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

Official source

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 concepts (5)

Rights

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 system, social convention, or ethical theory. Rights are of essential importance in such disciplines as law and ethics, especially theories of justice and deontology. The history of social conflicts has often involved attempts to define and redefine rights.

Perpendicular

In elementary geometry, two geometric objects are perpendicular if their intersection forms right angles (angles that are 90 degrees or π/2 radians wide) at the point of intersection called a foot. The condition of perpendicularity may be represented graphically using the perpendicular symbol, ⟂. Perpendicular intersections can happen between two lines (or two line segments), between a line and a plane, and between two planes.

Boolean algebra (structure)

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 operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra (with involution).