Bounds on margin distributions in learning problems

Let be a probability space and let P_n be the empirical measure based on i.i.d. sample (X₁,…,X_n) from P. Let be a class of measurable real valued functions on For define F_f(t):=P{ft} and F_n,f(t):=P_n{ft}. Given γ(0,1], define _n,γ(δ):=1/(n^1−γ/2δ^γ). We show that if the L₂(P_n)-entropy of the class grows as ^−α for some α(0,2), then, for all and all δ(0,Δ_n), Δ_n=O(n^1/2),

and

where and c(σ)↓1 as σ↓0 (the above inequalities hold for any fixed σ(0,1] with a high probability). Also, define

Then for all

uniformly in and with probability 1 (for the above ratio is bounded away from 0 and from ∞). The results are motivated by recent developments in machine learning, where they are used to bound the generalization error of learning algorithms. We also prove some more general results of similar nature, show the sharpness of the conditions and discuss the applications in learning theory.     

An application of the Turán theorem to domination in graphs

A function f:V(G)→{+1,−1} defined on the vertices of a graph G is a signed dominating function if for any vertex v the sum of function values over its closed neighborhood is at least 1. The signed domination number γ_s(G) of G is the minimum weight of a signed dominating function on G. By simply changing “{+1,−1}” in the above definition to “{+1,0,−1}”, we can define the minus dominating function and the minus domination number of G. In this note, by applying the Turán theorem, we present sharp lower bounds on the signed domination number for a graph containing no (k+1)-cliques. As a result, we generalize a previous result due to Kang et al. on the minus domination number of k-partite graphs to graphs containing no (k+1)-cliques and characterize the extremal graphs.     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.     

Acyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called thepath partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

RELATIVE WIDTH OF SMOOTH CLASSES OF MULTIVARIATE PERIODIC FUNCTIONS WITH RESTRICTIONS ON ITERATED LAPLACE DERIVATIVES IN THE L2-METRIC

For two subsets W and V of a Banach space X, let Kn(W, V, X) denote the relative Kolmogorov n-width of W relative to V defined by Kn (W, V, X) := inf sup Ln f∈W g∈V∩Ln inf ‖f-g‖x,where the infimum is taken over all n-dimensional linear subspaces Ln of X. Let W2(△r) denote the class of 2w-periodic functions f with d-variables satisfying ∫[-π,π]d |△rf(x)|2dx ≤ 1,while △r is the r-iterate of Laplace operator △. This article discusses the relative Kolmogorov n-width of W2(△r) relative to W2(△r) in Lq([-r, πr]d) (1 ≤ q ≤∞), and obtain its weak asymptotic result.     

On positive solutions of some nonlinear fourth-order beam equations

The existence, uniqueness and multiplicity of positive solutions of the following boundary value problem is considered:

u⁽⁴⁾(t)−λf(t,u(t))=0, for 0<t<1,u(0)=u(1)=u″(0)=u″(1)=0,

where λ>0 is a constant, f :[0,1]×[0,+∞)→[0,+∞) is continuous.     

The vertex-cover polynomial of a graph

In this paper we define the vertex-cover polynomial Ψ(G,τ) for a graph G. The coefficient of τ^r in this polynomial is the number of vertex covers V′ of G with |V′|=r. We develop a method to calculate Ψ(G,τ). Motivated by a problem in biological systematics, we also consider the mappings f from {1, 2,…,m} into the vertex set V(G) of a graph G, subject to f⁻¹(x)f⁻¹(y)≠ for every edge xy in G. Let F(G,m) be the number of such mappings f. We show that F(G,m) can be determined from Ψ(G,τ).     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

ContributionsEdge colorings of graphs embeddable in a surface of low genus

In this paper, by using the Discharging Method, we show that any graph with maximum degree Δ 8 that is embeddable in a surface Σ of characteristic χ(Σ) 0 is class one and any graph with maximum degree Δ 9 that is embeddable in a surface Σ of characteristic χ(Σ) = − 1 is class one. For surfaces of characteristic 0 or −1, these results improve earlier results of Mel'nikov.     

Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}.     

An upper bound for the chromatic number of line graphs

It was conjectured by Reed [B. Reed, ω,α, and χ, Journal of Graph Theory 27 (1998) 177–212] that for any graph G, the graph’s chromatic number χ(G) is bounded above by , where Δ(G) and ω(G) are the maximum degree and clique number of G, respectively. In this paper we prove that this bound holds if G is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph G and produces a colouring that achieves our bound.     

Labeling planar graphs with a condition at distance two

An L(2,1)-labeling of a graph is a mapping c:V(G)→{0,…,K} such that the labels assigned to neighboring vertices differ by at least 2 and the labels of vertices at distance two are different. The smallest K for which an L(2,1)-labeling of a graph G exists is denoted by λ_2,1(G). Griggs and Yeh [J.R. Griggs, R.K. Yeh, Labeling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586–595] conjectured that λ_2,1(G)≤Δ² for every graph G with maximum degree Δ≥2. We prove the conjecture for planar graphs with maximum degree Δ≠3. All our results also generalize to the list-coloring setting.     

Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Λ(u)−Λ(v)|2, when u,v are neighbors in G, and |Λ(u)−Λ(v)|1 when the distance of u,v in G is two. The discrete number of frequencies used is called order and the range of frequencies used, span. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span (min span RCP) or the order (min order RCP).In this paper, we deal with an interesting, yet not examined until now, variation of the radiocoloring problem: that of satisfying frequency assignment requests which exhibit some periodic behavior. In this case, the interference graph (modelling interference between transmitters) is some (infinite) periodic graph. Infinite periodic graphs usually model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they can model very large networks produced by the repetition of a small graph.A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph G_i(V_i,E_i). The edge set of G is derived by connecting the vertices of each iteration G_i to some of the vertices of the next iteration G_i+1, the same for all G_i. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest.We give two basic results:

• We prove that the min span RCP is PSPACE-complete for periodic planar graphs.

• We provide an O(n(Δ(G_i)+σ)) time algorithm (where|V_i|=n, Δ(G_i) is the maximum degree of the graph G_i and σ is the number of edges connecting each G_i to G_i+1), which obtains a radiocoloring of a periodic planar graph G that approximates the minimum span within a ratio which tends to as Δ(G_i)+σ tends to infinity.

We remark that, any approximation algorithm for the min span RCP of a finite planar graph G, that achieves a span of at most αΔ(G)+constant, for any α and where Δ(G) is the maximum degree of G, can be used as a subroutine in our algorithm to produce an approximation for min span RCP of asymptotic ratio α for periodic planar graphs.

L approximation with trigonometric n-nomials

We compare the degree of approximation to L²(−π, π) by nth degree trigonometric polynomials, with the degree of approximation by trigonometric n-nomials, which are linear combinations, with constant (complex) coefficients, of any 2n + 1 members of the sequence {exp (ikx)}, − ∞ < k < ∞.     

All hypoenergetic graphs with maximum degree at most 3

The energy E(G) of a graph G is defined as the sum of the absolute values of its eigenvalues. A connected graph G of order n is said to be hypoenergetic if E(G)<n. All connected hypoenergetic graphs with maximum degree Δ3 have been characterized. In addition to the four (earlier known) hypoenergetic trees, we now show that complete bipartite graph K_2,3 is the only hypoenergetic cycle-containing hypoenergetic graph. By this, the validity of a conjecture by Majstorović et al. has been confirmed.     

On the list dynamic coloring of graphs

A proper vertex coloring of a graph G is called a dynamic coloring if for every vertex v of degree at least 2, the neighbors of v receive at least two different colors. Assume that is the minimum number k such that for every list assignment of size k to each vertex of G, there is a dynamic coloring of G such that every vertex is colored with a color from its list. In this paper, it is proved that if G is a graph with no component isomorphic to C₅ and Δ(G)≥3, then , where Δ(G) is the maximum degree of G. This generalizes a result due to Lai, Montgomery and Poon which says that under the same assumptions χ₂(G)≤Δ(G)+1. Among other results, we determine , for every natural number n.     

Asymptotic behaviour of nonlinear parabolic equations with critical exponents. A dynamical systems approach

We investigate the large-time behaviour of solutions to the nonlinear heat-conduction equation with absorption u_t = Δ(u^{σ + 1}) − u^β in Q = R^N × (0, ∞) (E) with N 1, σ > 0 and critical absorption exponent β = σ + 1 + 2/N; the initial function u(x, 0) = 0 is assumed to be integrable, nonnegative and compactly supported. We prove that u converges as t → ∞ to a unique self-similar function which is a contracted version of one of the asymptotic profiles of the nonabsorptive problem u_t = Δ(u^{σ + 1}), the same for any initial data. The cornerstone of the proof is a result about ω-limits of (infinite-dimensional) asymptotical dynamical systems. Combining this result with an asymptotic evaluation of the mass function as well as typical PDE estimates gives the behaviour of (E) for large times.Similar unusual asymptotic behaviour is obtained for the equation u_t = div(¦Du¦^σ Du) − u^β with same conditions on σ and u(x, 0) and critical value for β = σ + 1 + (σ + 2)/N.     

Asymptotic distribution of the increase of the largest canonical correlation when one of the vectors is augmented

Let r₁ > r₂ > … be the sample canonical correlations in a sample of size n from a multivariate normal population partitioned into two subvectors with population canonical correlations ₁ > ₂ > …. Let one of the subvectors be augmented by adding one or more variables to it. For the increase in the largest canonical correlation, Δr in the sample and Δ in the population, it is shown that √n(Δr − Δ) → ^DN(0, σ²) and a formula for σ² is derived.     

Coloring edges of embedded graphs

In this paper, we prove that any graph G with maximum degree , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000     

Long time behaviour for generalized complex Ginzburg–Landau equation

In this paper, the two-dimensional generalized complex Ginzburg–Landau equation (CGL)

u_t=ρu−Δφ(u)−(1+iγ)Δu−νΔ²u−(1+iμ)|u|^2σu+αλ₁(|u|²u)+β(λ₂)|u|²