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

Publication# Uniform s-Cross-Intersecting Families

Abstract

In this paper we study a question related to the classical Erdos-Ko-Rado theorem, which states that any family of k-element subsets of the set [n] = {1,..., n} in which any two sets intersect has cardinality at most ((n-1)(k-1)). We say that two non-empty families A, B subset of (([n])(k)) are s-cross-intersecting if, for any A is an element of A, B is an element of B, we have |A boolean AND B| >= s. In this paper we determine the maximum of |A| + |B| for all n. This generalizes a result of Hilton and Milner, who determined the maximum of |A| + |B| for nonempty 1-cross-intersecting families.

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 publications (4)

Related MOOCs (1)

Related concepts (19)

Introduction to optimization on smooth manifolds: first order methods

Learn to optimize on smooth, nonlinear spaces: Join us to build your foundations (starting at "what is a manifold?") and confidently implement your first algorithm (Riemannian gradient descent).

Subset

In mathematics, set A is a subset of a set B if all elements of A are also elements of B; B is then a superset of A. It is possible for A and B to be equal; if they are unequal, then A is a proper subset of B. The relationship of one set being a subset of another is called inclusion (or sometimes containment). A is a subset of B may also be expressed as B includes (or contains) A or A is included (or contained) in B. A k-subset is a subset with k elements. The subset relation defines a partial order on sets.

Antiprism

In geometry, an n-gonal antiprism or n-antiprism is a polyhedron composed of two parallel direct copies (not mirror images) of an n-sided polygon, connected by an alternating band of 2n triangles. They are represented by the Conway notation An. Antiprisms are a subclass of prismatoids, and are a (degenerate) type of snub polyhedron. Antiprisms are similar to prisms, except that the bases are twisted relatively to each other, and that the side faces (connecting the bases) are 2n triangles, rather than n quadrilaterals.

Sphere

A sphere () is a geometrical object that is a three-dimensional analogue to a two-dimensional circle. Formally, a sphere is the set of points that are all at the same distance r from a given point in three-dimensional space. That given point is the centre of the sphere, and r is the sphere's radius. The earliest known mentions of spheres appear in the work of the ancient Greek mathematicians. The sphere is a fundamental object in many fields of mathematics. Spheres and nearly-spherical shapes also appear in nature and industry.

A family of subsets of {1, ... , n} is called intersecting if any two of its sets intersect. A classical result in extremal combinatorics due to Erdos, Ko and Rado determines the maximum size of an intersecting family of k-subsets of {1, ... , n}. In this ...

Max-min fairness is widely used in various areas of networking. In every case where it is used, there is a proof of existence and one or several algorithms for computing the max-min fair allocation; in most, but not all cases, they are based on the notion ...

2002Let parallel to.parallel to be a norm in R-d whose unit ball is B. Assume that V subset of B is a finite set of cardinality n, with Sigma(v is an element of V) v = 0. We show that for every integer k with 0