Publication

Uniform s-Cross-Intersecting Families

Andrei Kupavskii
2017
Journal Articles

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

https://infoscience.epfl.ch/entities/publication/01006d5d-381f-47bd-b5a5-8bcf0ab8cbdb

About this result

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.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Andrei Kupavskii
2017
Journal Articles

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/01006d5d-381f-47bd-b5a5-8bcf0ab8cbdb

About this result

Related concepts (24)

Uniform polytope

In geometry, a uniform polytope of dimension three or higher is a vertex-transitive polytope bounded by uniform facets. The uniform polytopes in two dimensions are the regular polygons (the definition is different in 2 dimensions to exclude vertex-transitive even-sided polygons that alternate two different lengths of edges). This is a generalization of the older category of semiregular polytopes, but also includes the regular polytopes. Further, star regular faces and vertex figures (star polygons) are allowed, which greatly expand the possible solutions.

4-polytope

In geometry, a 4-polytope (sometimes also called a polychoron, polycell, or polyhedroid) is a four-dimensional polytope. It is a connected and closed figure, composed of lower-dimensional polytopal elements: vertices, edges, faces (polygons), and cells (polyhedra). Each face is shared by exactly two cells. The 4-polytopes were discovered by the Swiss mathematician Ludwig Schläfli before 1853. The two-dimensional analogue of a 4-polytope is a polygon, and the three-dimensional analogue is a polyhedron.

16-cell

In geometry, the 16-cell is the regular convex 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {3,3,4}. It is one of the six regular convex 4-polytopes first described by the Swiss mathematician Ludwig Schläfli in the mid-19th century. It is also called C16, hexadecachoron, or hexdecahedroid . It is a part of an infinite family of polytopes, called cross-polytopes or orthoplexes, and is analogous to the octahedron in three dimensions. It is Coxeter's polytope.

Related publications (2)

Uniform s-Cross-Intersecting Families

Chat with Graph Search

Counting Intersecting and Pairs of Cross-Intersecting Families

Small subset sums