On lines missing polyhedral sets in 3-space

We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:

1. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
2. AnO(n ^1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
3. An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
4. An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n ^4/3+ε+k ^1/3 n ^1+ε+klog² n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].

The tools used to obtain these results include Plücker coordinates of lines, random sampling, and polarity transformations in 3-space.     

Convergence of representation averages and of convolution powers

LetS be a locally compact (σ-compact) group or semi-group, and letT(t) be a continuous representation ofS by contractions in a Banach spaceX. For a regular probability μ onS, we study the convergence of the powers of the μ-averageUx=∫T(t)xdμ(t). Our main results for random walks on a groupG are:

1. if μ is adapted and strictly aperiodic, and generates a recurrent random walk, thenU ⁿ (U-I) converges strongly to 0. In particular, the random walk is completely mixing.
2. If μ×μ is ergodic onG×G, then for every unitary representationT(.) in a Hilbert space,U ⁿ converges strongly to the orthogonal projection on the space of common fixed points. These results are proved for semigroup representations, along with some other results (previously known only for groups) which do not assume ergodicity.
3. If μ is spread-out with supportS, then $\left\| {\mu ^{n + K} - \mu ^n } \right\| \to 0$ if and only if e $ \in \overline { \cup _{j = 0}^\infty S^{ - j} S^{j + K} } .$ .

     

A generalization of the katona theorem for crosst-intersecting families

LetX be ann-element set and letA and? be families of subsets ofX. We say thatA and? are crosst-intersecting if |A ∩ B| ≥ t holds for all A ∈A and for allB ∈ ?. Suppose thatA and ? are crosst-intersecting. This paper first proves a crosst-intersecting version of Harper's Theorem:

1. There are two crosst-intersecting Hamming spheresA ₀,? ₀ with centerX such that |A| ≤ |A ₀| and|?| ≤ |? ₀| hold.
2. Suppose thatt ≥ 2 and that the pair of integers (|A) is maximal with respect to direct product ordering among pairs of crosst-intersecting families. Then,A and? are Hamming spheres with centerX.

Using these claims, the following conjecture of Frankl is proven:

1. Ifn + t = 2k ? 1 then |A| |?| ≤ max \(\left\{ {\left( {K_k^n + \left( {_{k - 1}^{n - 1} } \right)} \right)^2 ,K_k^n K_{k - 1}^n } \right\}\) holds, whereK _l ⁿ is defined as \(\left( {_n^n } \right)\left( {_{n - 1}^n } \right) + \cdots + \left( {_l^n } \right).\)
2. Ifn + t = 2k then |A| |? ≤ (K _k ⁿ )² holds.

The extremal configurations are also determined.     

Treewidth computation and extremal combinatorics

For a given graph G and integers b,f ≥0, let S be a subset of vertices of G of size b+1 such that the subgraph of G induced by S is connected and S can be separated from other vertices of G by removing f vertices. We prove that every graph on n vertices contains at most $n\left( {_b^{b + f} } \right)$ such vertex subsets. This result from extremal combinatorics appears to be very useful in the design of several enumeration and exact algorithms. In particular, we use it to provide algorithms that for a given n-vertex graph G

1. compute the treewidth of G in time O(1.7549 ⁿ ) by making use of exponential space and in time O(2.6151 ⁿ ) and polynomial space
2. decide in time O(n ⁵· $_{k + 2}^{\left\lceil {(2n + k + 8)/3} \right\rceil } $ ) if the treewidth of G is at most k
3. list all minimal separators of G in time O(1.6181 ⁿ ) and all potential maximal cliques of G in time O(1.7549 ⁿ ).

This significantly improves previous algorithms for these problems.     

On an Ulam's problem

The existence and the uniqueness (with respect to a filtration-equivalence) of a vector flowX on ? ⁿ ,n≥3, such that:

1. X has not any stationary points on ? ⁿ ;
2. all orbits ofX are bounded;
3. there exists a filtration forX are proved in the present note.

     

The problem of differentiating an asymptotic expansion in real powers. Part II: Factorizational theory

In Part II of our work we approach the problem discussed in Part I from the new viewpoint of canonical factorizations of a certain nth order differential operator L. The main results include:

1. characterizations of the set of relations $$ f^{(k)} (x) = P^{(k)} (x) + o^{(k)} (x^{\alpha _n - k} ),x \to + \infty ,0 \leqslant k \leqslant n - 1, $$ where $$ P(x) = a_1 x^{\alpha _1 } + \cdots + a_n x^{\alpha _n } and \alpha _1 > \alpha _2 > \cdots > \alpha _n , $$ by means of suitable integral conditions
2. formal differentiation of a real-power asymptotic expansion under a Tauberian condition involving the order of growth of L
3. remarkable properties of asymptotic expansions of generalized convex functions.

     

Group inverse for a class of 2×2 anti-triangular block matrices over skew fields

Suppose K is a skew field. Let K ^m×n denote the set of all m×n matrices over K. In this paper, we give necessary and sufficient conditions for the existence and explicit representations of the group inverses of the block matrices in the following three cases, respectively:

1. $\mathrm{rank}(S)=\mathrm{rank}(B^{\pi}A)$ ;
2. $\mathrm{rank}(S)=\mathrm{rank}(AB^{\pi})$ ;
3. $\mathrm{rank}(S)=\mathrm{rank}(B^{\pi}A)=\mathrm{rank}(AB^{\pi})$ ,

where A,B,C??K ^n×n , B ^# exists, R(B)=R(C), N(B)=N(C) and S=B ^?? AB ^?? . The paper??s conclusions generalized some related results of Zhao and Bu (Electron. J. Linear Algebra 21:63?C75, 2010).     

Analytische Fortsetzbarkeit von zufälligen Potenzreihen bezüglich abhängiger Zufallsvariabler

Рассматриваются слу чайная величина \(\mathfrak{X} = (X_n (\omega ))\) , удовлетворяющая усл овиюE(X _n ⁴ )≦M, и соответствующ ий случайный степенн ой ряд \(f_x (z;\omega ) = \mathop \sum \limits_{n = 0}^\infty a_n X_n (\omega )z^n\) . Устанавливаются тео ремы непродолжимост и почти наверное:

1. дляf _x при условиях с лабой мультипликати вности на \(\mathfrak{X}\) ,
2. для \(f_{\tilde x}\) , где \(\mathop \mathfrak{X}\limits^ \sim = (\mathop X\limits^ \sim _n )\) есть подп оследовательность в \(\mathfrak{X}\) ,
3. для по крайней мере од ного из рядовf _x′ илиf _x″ , где \(\mathfrak{X}'\) и \(\mathfrak{X}''\) — некоторые п ерестановки \(\mathfrak{X}\) , выбираемые универс ально, т. е. независимо от коэффициентовa _n .

     

On the divergence of de la Vallée Poussin means of Fourier series

Пусть {λ _{n 1} ^t8 — монотонн ая последовательнос ть натуральных чисел. Дл я каждой функции fεL(0, 2π) с рядом Фурье строятся обобщенные средние Bалле Пуссена $$V_n^{(\lambda )} (f;x) = \frac{{a_0 }}{2} + \mathop \sum \limits_{k = 1}^n (a_k \cos kx + b_k \sin kx) + \mathop \sum \limits_{k = n + 1}^{n + \lambda _n } \left( {1 - \frac{{k - n}}{{\lambda _n + 1}}} \right)\left( {a_k \cos kx + b_k \sin kx} \right).$$ Доказываются следую щие теоремы.

1. Если λ_n=o(n), то существуе т функция fεL(0, 2π), для кот орой последовательность {V_n ^(λ)(?;x)} расходится почти вс юду.
2. Если λ_n=o(n), то существуе т функция fεL(0, 2π), для кот орой последовательность $$\left\{ {\frac{1}{\pi }\mathop \smallint \limits_{ - \pi /\lambda _n }^{\pi /\lambda _n } f(x + t)\frac{{\sin (n + \tfrac{1}{2})t}}{{2\sin \tfrac{1}{2}t}}dt} \right\}$$ расходится почти всю ду

.     

О рядах по системе Фра нклина

In this paper some basis properties are proved for the series with respect to the Franklin system, which are analogous to those of the series with respect to the Haar system. In particular, the following statements hold:

1. The Franklin series \(\mathop \Sigma \limits_{n = 0}^\infty a_n f_n (x)\) converges a.e. onE if and only if \(\mathop \Sigma \limits_{n = 0}^\infty a_n^2 f_n^2 (x)< + \infty \) a.e. onE;
2. If the series \(\mathop \Sigma \limits_{n = 0}^\infty a_n f_n (x)\) , with coefficients ¦a _n ¦↓0, converges on a set of positive measure, then it is the Fourier-Franklin series of some function from \(\bigcap\limits_{p< \infty } {L_p } \) ;
3. The absolute convergence at a point for Fourier—Franklin series is a local property;
4. If an integrable function (fx) has a discontinuity of the first kind atx=x ₀, then its Fourier-Franklin series diverges atx=x ₀.

     

On the representation of measurable functions by martingales

Пусть (gW, ?,P) - вероятност ное пространство, ?₁??₂?...?? _n ?...,? _n ?? -последовательност ь σ-алгебр и ?_∞ - порожден ная ими минимальная σ-алгебра. В статье указано необ ходимое и достаточно е условие на последовательность σ-алгебр {? _n }, при выполнении кото рого для любой ?_∞-измер имой функцииf(x) существует ряд \(\mathop \sum \limits_{n = 1}^\infty \varphi _n (x)\) центрированных отн осительно {? _n } функций {? _n } _n=1 ^∞ такой, что

1. \(\mathop \sum \limits_{n = 1}^\infty \varphi _n (x)\) абсолютно почти вс юду сходится кf(x) на множестве {x: ¦f(x)¦<+∞};
2. \(\mathop \sum \limits_{n = 1}^\infty \varphi _n (x)\) сходится по мере кf(x) на множестве {х: ¦f(х)¦=+∞ }.

Полученные результа ты представляют обоб щения и усиления доказанных ранее теорем Р. Ганди и Г. Ламба о пре дставлении ?_∞-измерим ых функций мартингалам и {? _n ,? _n } (см. [1] и [2]).     

On projective planes admitting elations and homologies

We consider projective planes Π of ordern with abelian collineation group Γ of ordern(n?1) which is generated by (A, m)-elations and (B, l)-homologies wherem =AB andA εl. We prove

1. Ifn is even thenn=2^e and the Sylow 2-subgroup of Γ is elementary abelian.
2. Ifn is odd then the Sylow 2-subgroup of Γ is cyclic.
3. Ifn is a prime then Π is Desarguesian.
4. Ifn is not a square thenn is a prime power.

     

Elliptic and hyperbolic inversions

Letx andy be orthogonal coordinates of a pointM(u=ax+iby orax+εby) of a plane whereasx′ andy′ are orthogonal coorditanes of a pointM′(v=ax′+iby′ orax′+εby′) inverse ofM in the elliptic or hyperbolic inversion $u\bar \upsilon = k$ (k positive) $\bar \upsilon $ designating the conjugate ofv whilei andε are Clifford numbers such thati ²=?1 andε ² = 1 (a andb are real)O is the origin of axises,Ox is the axis of the inversion.

1. Two inverse points are aligned withO.
2. The inverse of a conic having a centrec is a conic but this inverse is a straight line if the origin is on the conic.

There is a metric relation between sides and diagonals of a quadrilateral inscribed in an ellipse or in an hyperbola.     

On certain properties of linear summation methods of Fourier series on the classesC(ɛ)

Для линейных методов суммирования рядов Ф урье (1) $$L_n (f;x) = \frac{1}{\pi }\mathop \smallint \limits_{ - \pi }^\pi f(x + t)\left( {\frac{1}{2} + \sum\limits_{k = 1}^n {\lambda _{k,n} } \cos kt} \right)dt$$ на классах $$C(\varepsilon ) = \{ f:E_n (f) \leqq \varepsilon _n ;\forall n \geqq 0\} ,\varepsilon = \{ \varepsilon _n \} _{n = 0.}^\infty \varepsilon _n \downarrow 0,$$ доказываются:

1. оценки для порядка р оста норм ∥{L_n∥, если из вестен порядок приближения операторами (1) некоторого классаС (?) (при этом, если опера торы (1) приближают класс С(е) с наилучшим порядком, то находится точная а симптотика возрастания норм {∥ L_n∥);
2. сравнительные оцен ки порядков приближе ния классовС(?) операторами (1), если известен порядок при ближения ими некотор ого более узкого класса С(?*).

В том случае, когда опе раторы (1) приближают кл асс С(?*) с наилучшим порядком, получаются точные по рядковые оценки для л юбого более широкого класса С(?).     

Algorithms for the vector maximization problem

We consider a convex setB inR ⁿ described as the intersection of halfspacesa _i ^T x ≦b _i (i ∈ I) and a set of linear objective functionsf _j =c _j ^T x (j ∈ J). The index setsI andJ are allowed to be infinite in one of the algorithms. We give the definition of theefficient points ofB (also called functionally efficient or Pareto optimal points) and present the mathematical theory which is needed in the algorithms. In the last section of the paper, we present algorithms that solve the following problems:

1. To decide if a given point inB is efficient.
2. To find an efficient point inB.
3. To decide if a given efficient point is the only one that exists, and if not, find other ones.
4. The solutions of the above problems do not depend on the absolute magnitudes of thec _j. They only describe the relative importance of the different activitiesx _i. Therefore we also consider $$\begin{gathered} \max G^T x \hfill \\ x efficient \hfill \\ \end{gathered} $$ for some vectorG.

     

Call Centers with Impatient Customers: Many-Server Asymptotics of the M/M/n + G Queue

The subject of the present research is the M/M/n + G queue. This queue is characterized by Poisson arrivals at rate λ, exponential service times at rate μ, n service agents and generally distributed patience times of customers. The model is applied in the call center environment, as it captures the tradeoff between operational efficiency (staffing cost) and service quality (accessibility of agents). In our research, three asymptotic operational regimes for medium to large call centers are studied. These regimes correspond to the following three staffing rules, as λ and n increase indefinitely and μ held fixed:

Efficiency-Driven (ED): $n\ \approx \ (\lambda / \mu)\cdot (1 - \gamma),\gamma > 0,$

Quality-Driven (QD): $n \ \approx \ ( \lambda / \mu)\cdot (1 + \gamma),\gamma > 0$ , and

Quality and Efficiency Driven (QED): $ n \ \approx \ \lambda/ \mu+\beta \sqrt{\lambda/\mu},-\infty < \beta < \infty $ .

In the ED regime, the probability to abandon and average wait converge to constants. In the QD regime, we observe a very high service level at the cost of possible overstaffing. Finally, the QED regime carefully balances quality and efficiency: agents are highly utilized, but the probability to abandon and the average wait are small (converge to zero at rate 1/ $\sqrt{n}$ ). Numerical experiments demonstrate that, for a wide set of system parameters, the QED formulae provide excellent approximation for exact M/M/n + G performance measures. The much simpler ED approximations are still very useful for overloaded queueing systems. Finally, empirical findings have demonstrated a robust linear relation between the fraction abandoning and average wait. We validate this relation, asymptotically, in the QED and QD regimes.     

Effective analysis of integral points on algebraic curves

LetK be an algebraic number field,S?S _\t8 a finite set of valuations andC a non-singular algebraic curve overK. Letx∈K(C) be non-constant. A pointP∈C(K) isS-integral if it is not a pole ofx and |x(P)| _v >1 impliesv∈S. It is proved that allS-integral points can be effectively determined if the pair (C, x) satisfies certain conditions. In particular, this is the case if

1. x:C→P ¹ is a Galois covering andg(C)≥1;
2. the integral closure of $\bar Q$ [x] in $\bar Q$ (C) has at least two units multiplicatively independent mod $\bar Q$ *.

This generalizes famous results of A. Baker and other authors on the effective solution of Diophantine equations.     

On the number of non-isomorphic subgraphs

Let $\mathcal{K}$ be the family of graphs on ω₁ without cliques or independent subsets of sizew ₁. We prove that

1. it is consistent with CH that everyGε $\mathcal{K}$ has 2^ω many pairwise non-isomorphic subgraphs,
2. the following proposition holds in L: (*)there is a Gε $\mathcal{K}$ such that for each partition (A, B) of ω₁ either G?G[A] orG?G[B],
3. the failure of (*) is consistent with ZFC.

     

Power Majorization and Majorization of Sequences

Let \(\bar x\) , \(\bar y\ \in\ R_n\) be vectors which satisfy x₁ ≥ x₂ ≥ … ≥ x_n and y₁ ≥ y₂ >- … ≥ y_n and Σx_i = Σy_i. We say that \(\bar x\) is power majorized by \(\bar y\) if Σx_i ^p ≤ Σy_i ^p for all real p ? [0, 1] and Σx_i ^p ≥ Σy_i ^p for p ∈ [0, 1]. In this paper we give a classification of functions ? (which includes all possible positive polynomials) for which \(\bar\phi(\bar x) \leq \bar\phi(\bar y)\) (see definition below) when \(\bar x\) is power majorized \(\bar y\) . We also answer a question posed by Clausing by showing that there are vectors \(\bar x\) , \(\bar y\ \in\ R^n\) of any dimension n ≥ 4 for which there is a convex function ? such that \(\bar x\) is power majorized by \(\bar y\) and \(\bar\phi(\bar x)\ >\ \bar\phi(\bar y)\) .