8083367
On Some Three-Color Ramsey Numbers
Abstract. In this paper we study three-color Ramsey numbers. Let Ki,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G1, G2 and G3, if r(G1, G2)≥s(G3), then r(G1, G2, G3)≥(r(G1, G2)−1)(χ(G3)−1)+s(G3), where s(G3) is the chromatic surplus of G3; (ii) (k+m−2)(n−1)+1≤r(K1,k, K1,m, Kn)≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(Kk,m, Kk,m, Kn)≤c(n/logn), and r(C2m, C2m, Kn)≤c(n/logn)m/(m−1) for sufficiently large n.
206570728
On Book-Complete Graph Ramsey Numbers
It is shown that a graph of orderNand average degreedthat does not contain the bookBm=K1+K1, mas a subgraph has independence number at leastNf(d), wheref(x)~(logx/x)(x?∞). From this result we find that the book-complete graph Ramsey number satisfiesr(Bm, Kn)?mn2/log(n/e). It is also shown that for every treeTmwithmedges,r(K1+Tm,Kn)?(2m?1)n2/log(n/e).
17658871
On generalized Ramsey numbers
Abstract Let f 1 and f 2 be graph parameters. The Ramsey number r ( f 1 ⩾ m ; f 2 ⩾ n ) is defined as the minimum integer N such that any graph G on N vertices, either f 1 ( G )⩾ m or f 2 ( G )⩾n . A general existence condition is given and a general upper bound is shown in this paper. In addition, suppose the number of triangles in G is denoted by t ( G ). We verify that (1−o(1))(24 n ) 1/3 ⩽ r ( t ⩾ n ; t ⩾ n )⩽(1+o(1))(48 n ) 1/3 as n →∞.
206964202
Asymptotic Upper Bounds for Ramsey Functions
Abstract. We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nfa+1(d), where fa+1(d)=∫01(((1−t)1/(a+1))/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(Kk+l,Kn)≤ (l+o(1))nk/(logn)k−1. In particular, r(Kk, Kn)≤(1+o(1))nk−1/(log n)k−2.
1087466
Independence numbers of hypergraphs with sparse neighborhoods
Let H be a hypergraph with N vertices and average degree d. Suppose that the neighborhoods of H are sparse, then its independence number is at least cN(log d/d), where c > 0 is a constant. In particular, let integers r ≥ 3 and n ≥ 1 be fixed, and let H be r-uniform, triangle-free and linear, then its independence number is at least cN logn d/d for all sufficiently large d.
5363430
Differential Methods for Finding Independent Sets in Hypergraphs
It is shown by using differential methods that if ${\cal H}$ is a double linear, $r$-uniform hypergraph with degree sequence $\{d_v\}$ such that any subhypergraph induced by a neighborhood has maximum degree less than $m$, then its independence number is at least $\sum_{v}f_{r,m}(d_v)$, where $f_{r,m}(x)$ is a convex function satisfying $f_{r,m}(x)\sim (\log x)/x$ if $r=2$ and $c/x^{1/(r-1)}$ if $r \ge 3$, as $x\to\infty$, and $c=c(r,m)>0$ is a constant. The proof yields a polynomial-time algorithm for finding such an independent set in ${\cal H}$.
14475371
The Perceptron Algorithm with Uneven Margins
The perceptron algorithm with margins is a simple, fast and effective learning algorithm for linear classifiers; it produces decision hyperplanes within some constant ratio of the maximal margin. In this paper we study this algorithm and a new variant: the perceptron algorithm with uneven margins, tailored for document categorisation problems (i.e. problems where classes are highly unbalanced and performance depends on the ranking of patterns). We discuss the interest of these algorithms from a theoretical point of view, provide a generalisation of Novikoff’s theorem for uneven margins, give a geometrically description of these algorithms and show experimentally that both algorithms yield equal or better performances than support vector machines, while reducing training time and sparsity, in classification (USPS) and document categorisation (Reuters) problems.
10776344
Robust Head Tracking Based on a Multi-State Particle Filter
This paper proposes a novel method for robust and automatic realtime head tracking by fusing face and head cues within a multi-state particle filter. Due to large appearance variability of human head, most existing head tracking methods use little object-specific prior knowledge, resulting in limited discriminant power. In contrast, face is a distinct pattern much easier to capture, which motivates us to incorporate a vector-boosted multi-view face detector (C. Huang, et al., 2005) to lend strong aid to general head observation cues including color and contour edge. To simultaneously and collaboratively perform temporal inference of both the face state and the head state, a Markov-network-based particle filter is constructed using sequential belief propagation Monte Carlo (G. Hua, et al., 2004). Our approach is tested on sequences used by previous researchers as well as on new data sets which includes many challenging real-world cases, and shows robustness against various unfavorable conditions
24660543
A note on the lower bounds of signed domination number of a graph
Abstract Let G = (V, E) be a graph. For a function f : V → {−1, 1}, the weight of f is w(f) = Σv ∈ V f(v). For a vertex v in V, we define f[v] = Σu∈N[v] f(u). A signed dominating function of G is a function f : V → {−1, 1} such that f[v] ⩾ 1 for all v ∈ V. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. A signed dominating function of a weight γs(G) we call a γs-function of G. In this paper, we study the signed domination problem of general graph, and obtain some lower bounds of the signed domination number of a graph, and show that these lower bounds are sharp, and extend a result in Dunbar et al. (1995).
12134443
From dual-cube to metacube: efficient low-degree alternatives to hypercube
The hypercube has been widely used as the interconnection network in parallel computers. However, when dealing with the parallel computers of very large scale, the port limitation due to the technology greatly forbid the use of hypercube networks. The hypercube-based SGI Origin2000, a newly developed multiprocessor system, tried to solve this problem by introducing a Cray router. In this paper we first describe a hypercube-like network, called dual-cube, that was motivated by the structure of Origin2000. A dual-cube DC(m) has m+1 links per node where m is the degree of a cluster (m-cube), one more link is used for connecting to a node in another cluster. The dual-cube mitigates the problem of port limitation in the large-scale hypercube network while keeps most of the topological properties of the hypercube network. Then, we describe an interconnection network that extends dual-cube into a more general network called metacube. The metacube has a two-level cube structure with two parameters representing the dimensions of the two-level cubes. Metacube is much more flexible than dual-cube and can solve the port limitation problem completely. The dual-cube and metacube networks can be applied to SGI Origin2000 to connect large number of processors without using Cray router.
1095698
DaNaLIX: a domain-adaptive natural language interface for querying XML
We present DaNaLIX, a prototype domain-adaptive natural language interface for querying XML. Our system is an extension of NaLIX, a generic natural language interface for querying XML. While retaining the portability of a purely generic system like NaLIX, DaNaLIX can exploit domain knowledge, whenever available, to its advantage for query translation. More importantly, in DaNaLIX such domain knowledge does not have to be pre-defined; instead it can be automatically obtained from the interactions between a user and the system. In this demonstration, we describe the overall architecture of DaNaLIX. We also demonstrate how a generic system like DaNaLIX can take advantage of domain knowledge to improve its usability and query translation accuracy. In addition, we show DaNaLIX still possesses the portability of a generic system by using data collections from three different domains. Finally, we present how domain knowledge can be obtained through user interactions in an automatic fashion.