Integer | EPFL Graph Search

An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of mathematics, the set of integers is often denoted by the boldface Z or blackboard bold \mathbb{Z}. The set of natural numbers \mathbb{N} is a subset of \mathbb{Z}, which in turn is a subset of the set of all rational numbers \mathbb{Q}, itself a subset of the real numbers \mathbb{R}. Like the natural numbers, \mathbb{Z} is countably infinite. An integer may be regarded as a real number that can be written without a fractional component. For example, 21, 4, 0, and −2048 are integers, while 9.75, 51/5, and are not. The integers form the smallest group and the smallest ring containing the natural numbers. In algebraic number theory,

On some algebraic and extremal problems in discrete geometry

Seyed Hossein Nassajianmojarrad

In the present thesis, we delve into different extremal and algebraic problems arising from combinatorial geometry. Specifically, we consider the following problems. For any integer

n\ge 3

, we define

e(n)

to be the minimum positive integer such that any set of

e(n)

points in general position in the plane contains

n

points in convex position. In 1935, Erd\H{o}s and Szekeres proved that

e(n) \le {2n-4 \choose n-2}+1

and later in 1961, they obtained the lower bound

2^{n-2}+1 \le e(n)

, which they conjectured to be optimal. We prove that

e(n) \le {2n-5 \choose n-2}-{2n-8 \choose n-3}+2

. In a recent breakthrough, Suk proved that

e(n) \le 2^{n+O\left(n^{2/3}\log n\right)}

. We strengthen this result by extending it to pseudo-configurations and also improving the error term. Combining our results with a theorem of Dobbins et al., we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes T'{o}th and by Pach and T'{o}th, respectively. Let

c(n)

(and

c'(n)

) denote the smallest positive integer

N

such that any family of

N

pairwise disjoint convex bodies in general position (resp.,

N

convex bodies in general position, any pair of which share at most two boundary points) has an

n

members in convex position. We show that

c(n)\le c'(n)\le 2^{n+O\left(\sqrt{n\log n}\right)}

. Given a point set

P

in the plane, an ordinary circle for

P

is defined as a circle containing exactly three points of

P

. We prove that any set of

n

points in the plane, not all on a line or a circle, determines at least

\frac{1}{4}n^2-O(n)

ordinary circles. We determine the exact minimum number of ordinary circles for all sufficiently large

n

, and characterize all point sets that come close to this minimum. We also consider the orchard problem for circles, where we determine the maximum number of circles containing four points of a given set and describe the extremal configurations. A special case of the Schwartz-Zippel lemma states that given an algebraic curve

C\subset \mathbb{C}^2

of degree

d

and two finite sets

A,B\subset \mathbb{C}

, we have

|C\cap (A\times B)|=O_d(|A|+|B|)

. We establish a two-dimensional version of this result, and prove upper bounds on the size of the intersection

|X\cap (P\times Q)|

for a variety

X\subset \mathbb{C}^4

and finite sets

P,Q\subset \mathbb{C}^2

. A key ingredient in our proofs is a two-dimensional version of a special case of Alon's combinatorial Nullstellensatz. As corollaries, we generalize the Szemer'edi-Trotter point-line incidence theorem and several known bounds on repeated and distinct Euclidean distances. We use incidence geometry to prove some sum-product bounds over arbitrary fields. First, we give an explicit exponent and improve a recent result of Bukh and Tsimerman by proving that

\max \{ |A+A|, |f(A, A)|\}\gg |A|^{6/5}

for any small set

A\subset \mathbb{F}_p

and quadratic non-degenerate polynomial

f(x, y)\in \mathbb{F}_p[x, y]

. This generalizes the result of Roche-Newton et al. giving the best known lower bound for the term

\max \{ |A+A|, |A \cdot A |\}

. Secondly, we improve and generalize the sum-product results of Hegyv'{a}ri and Hennecart on

\max\{ |A+B|, |f(B,C)|\}

, for a specific type of function

f

. Finally, we prove that the number of distinct cubic distances generated by any small set

A\times A\subset \mathbb{F}_p^2

\Omega(|A|^{8/7})

, which improves a result of Yazici et al.

EPFL2017

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release times, and weights and we want to compute a (possibly preemptive) schedule for them. The objective is to minimize the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its release date and its completion time. It had been a long-standing open problem to find a polynomial time O(1)-approximation algorithm for this setting. In a recent break-through result, Batra, Garg, and Kumar (FOCS 2018) found such an algorithm if the input data are polynomially bounded integers, and Feige, Kulkarni, and Li (SODA 2019) presented a black-box reduction to this setting. The resulting approximation ratio is a (not explicitly stated) constant which is at least 10000. In this paper we improve this ratio to 2 + epsilon. The algorithm by Batra, Garg, and Kumar (FOCS 2018) reduces the problem to DEMAND MULTICUT ON TREES and solves the resulting instances via LP-rounding and a dynamic program. Instead, we first reduce the problem to a (different) geometric problem while losing only a factor 1 + epsilon, and then solve its resulting instances up to a factor of 2 + epsilon by a dynamic program. In particular, our reduction ensures certain structural properties, thanks to which we do not need LP-rounding methods. We believe that our result makes substantial progress towards finding a PTAS for weighted flow time on a single machine.

ASSOC COMPUTING MACHINERY2021

Monochromatic cycle covers in random graphs

Dániel József Korándi

A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such covering cycles does not depend on the size of K-n but only on the number of colors. We initiate the study of this phenomenon in the case where K-n is replaced by the random graph G(n,p). Given a fixed integer r and p=p(n)>= n-1/r+epsilon, we show that with high probability the random graph G similar to G(n,p) has the property that for every r-coloring of the edges of G, there is a collection of f '(r)=O(r8logr) monochromatic cycles covering all the vertices of G. Our bound on p is close to optimal in the following sense: if pMUCH LESS-THAN(logn/n)1/r, then with high probability there are colorings of G similar to G(n,p) such that the number of monochromatic cycles needed to cover all vertices of G grows with n.

WILEY2018