Disjoint sets | EPFL Graph Search

In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set. For example, {1, 2, 3} and {4, 5, 6} are disjoint sets, while {1, 2, 3} and {3, 4, 5} are not disjoint. A collection of two or more sets is called disjoint if any two distinct sets of the collection are disjoint. Generalizations This definition of disjoint sets can be extended to families of sets and to indexed families of sets. By definition, a collection of sets is called a family of sets (such as the power set, for example). In some sources this is a set of sets, while other sources allow it to be a multiset of sets, with some sets repeated. An \left(A_i\right)_{i \in I}, is by definition is a set-valued function (that is, it is a function that assigns a set A_i to every element i \in I in its domain) whose domain I is called its (and elements of its

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once, at endpoint or at a crossing. Let

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

. We settle Harborth's conjecture in the affirmative. 2. A \emph{monotone cylindrical} graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called \emph{simple} if any pair of its edges have at most one point in common: an endpoint or a point at which they properly cross. We say that two edges are \emph{disjoint} if they do not intersect. We show that every simple complete monotone cylindrical graph on

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

by Suk and independently by Fulek. We remark that our proof implies a polynomial time algorithm for finding this set of pairwise disjoint edges. 3. A {\em tangle} is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a {\em degenerate tangle}. We settle a problem of Pach, Radoi\v ci'c, and T'oth \cite{TTpaper}, by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles. 4. We show that for a constant

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016

Group Approximation in Cayley Topology and Coarse Geometry, Part II: Fibred Coarse Embeddings

Masato Mimura

The objective of this series is to study metric geometric properties of disjoint unions of Cayley graphs of amenable groups by group properties of the Cayley accumulation points in the space of marked groups. In this Part II, we prove that a disjoint union admits a fibred coarse embedding into a Hilbert space (as a disjoint union) if and only if the Cayley boundary of the sequence in the space of marked groups is uniformly a-T-menable. We furthermore extend this result to ones with other target spaces. By combining our main results with constructions of Osajda and Arzhantseva Osajda, we construct two systems of markings of a certain sequence of finite groups with two opposite extreme behaviors of the resulting two disjoint unions: With respect to one marking, the space has property A. On the other hand, with respect to the other, the space does not admit fibred coarse embeddings into Banach spaces with non-trivial type (for instance, uniformly convex Banach spaces) or Hadamard manifolds; the Cayley limit group is, furthermore, non-exact.

2019

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

The present thesis deals with problems arising from discrete mathematics, whose proofs make use of tools from algebraic geometry and topology. The thesis is based on four papers that I have co-authored, three of which have been published in journals, and one has been submitted for publication (and also appeared as a preprint on the arxiv, and as an extendend abstract in a conference). Specifically, we deal with the following four problems: \begin{enumerate} \item We prove that if

M\in \mathbb{C}^{2\times2}

is an invertible matrix, and

B_M:\mathbb{C}^2\times\mathbb{C}^2\to\mathbb{C}

is a bilinear form

B_M(p,q)=p^TMq

, then any finite set

S

contained in an irreducible algebraic curve

C

of degree

d

\mathbb{C}^2

determines

\Omega_d(|S|^{4/3})

distinct values of

B_M

, unless

C

is a line, or is linearly equivalent to a curve defined by an equation of the form

x^k=y^l

, with

k,l\in\mathbb{Z}\backslash\\{0\\}

, and

\gcd(k,l)=1

. \item We show that if we are given

m

points and

n

lines in the plane, then the number of distinct distances between the points and the lines is

\Omega(m^{1/5}n^{3/5})

, as long as

m^{1/2}\le n\le m^2

. Also, we show that if we are given

m

points in the plane, not all collinear, then the number of distances between these points and the lines that they determine is

\Omega(m^{4/3})

. We also study three-dimensional versions of the distinct point-line distances problem. \item We prove the lower bound

\Omega(|S|^4)

on the number of ordinary conics determined by a finite point set

S

\mathbb{R}^2

, assuming that

S

is not contained in a conic, and at most

c|S|

points of

S

lie on the same line (for some $0

EPFL2017

Algebraic and topological methods in combinatorics

Adrian Claudiu Valculescu

M\in \mathbb{C}^{2\times2}

is an invertible matrix, and

B_M:\mathbb{C}^2\times\mathbb{C}^2\to\mathbb{C}

is a bilinear form

B_M(p,q)=p^TMq

, then any finite set

S

contained in an irreducible algebraic curve

C

of degree

d

\mathbb{C}^2

determines

\Omega_d(|S|^{4/3})

distinct values of

B_M

, unless

C

is a line, or is linearly equivalent to a curve defined by an equation of the form

x^k=y^l

, with

k,l\in\mathbb{Z}\backslash\\{0\\}

, and

\gcd(k,l)=1

. \item We show that if we are given

m

points and

n

lines in the plane, then the number of distinct distances between the points and the lines is

\Omega(m^{1/5}n^{3/5})

, as long as

m^{1/2}\le n\le m^2

. Also, we show that if we are given

m

points in the plane, not all collinear, then the number of distances between these points and the lines that they determine is

\Omega(m^{4/3})

. We also study three-dimensional versions of the distinct point-line distances problem. \item We prove the lower bound

\Omega(|S|^4)

on the number of ordinary conics determined by a finite point set

S

\mathbb{R}^2

, assuming that

S

is not contained in a conic, and at most

c|S|

points of

S

lie on the same line (for some $0

EPFL2017

Simple topological graphs

Andres Jacinto Ruiz Vargas

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016