[3] L. Banachowski. A complement to Tarjan's result about the lower bound on the complexity of the set union problem. Information Processing Letters, 11:59-65, 1980. [4] A. M. Ben-Amram and Z....
We give a very simple new proof of the celebrated intersection theorem of D. K. Ray-Chaudhuri and R. M. Wilson. The new proof yields a generalization to nonuniform set systems. Let n
Unextendible product bases (2008)
Let C denote the complex field. A vector v in the tensor product ⊗ m i=1 Cki is called a pure product vector if it is a vector of the form v1 ⊗ v2 · · · ⊗ vm, with vi ∈ C ki. A set F of...
Discrete Comput Geom 4 Disjoint Edges in Geometric Graphs (2008)
N Alon, P Erdös, Discrete Cornputattonal
A stract. Answering an old question in com inatorial geometry, we show that any configuration consisting of a set V of n points in general position in the plane and a set of 6n-5 closed straight line...
N. Alon, M. Tarsi, Beverly Sackler
Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: If G is a directed graph with...
doi:10.1112/plms/pdm027 MEASURES OF PSEUDORANDOMNESS FOR FINITE SEQUENCES: TYPICAL VALUES (2008)
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. R Ödl
Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈{−1, 1} N in order to measure their ‘level of randomness’. Those...
Marek Karpinski, N. Alon, R. Kannan, M. Karpinski
Abstract. We present some recent results and new sampling techniques for absolute and relative approximation of general Constraint Satisfaction Problems (CSP). The methods used are threefold and...
N. Alon, P. Seymour, R. Thomas, A In
[4] I. Babuˇska and A.K. Aziz. On the angle condition in the finite element method. SIAM J.
N. Alon, D. Kleitman, R. Lipton, R. Meshulam, M. Rabin S, J. Spencer
Abstract. Let q be a prime power. It is shown that for any hypergraph ~, ~ = {F~,..., Fdtq_~)+ ~} whose maximal degree is d, there exists Z ¢ ~o c ~, such that IUF~oFI =-- 0 (rood q). For integers...
J. Combinatorial Theory B 38(1985), 73–88. (2008)
N. Alon, N. Alon, P. D. Seymour
[3] N. Alon and V. D. Milman: λ1, isoperimetric inequalities for graphs and superconcentrators,
H. L. Abbott, Discrete Math, N. Alon, N. Alon, Z. Galil, ...
[3] D. Aldous, On the Markov-chain simulation method for uniform combinatorial simulation and simulated annealing, Prob. Eng. Info. Sci. 1 (1987), 33–46. [4] D. Aldous, Some inequalities for...
[2] N. Alon: Eigenvalues and expanders, Combinatorica 6(1986), 83–96. (2008)
N. Alon, S. Arora, C. Lund, R. Motwani, M. Sudan, ...
[3] N. Alon and V. D. Milman: λ1, isoperimetric inequalities for graphs and superconcentrators,
Spanning directed trees with many leaves (2008)
Alon, N, Fomin, F. V., Gutin, G., Krivelevich, M., Saurabh, S.
The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain...
Extremal and Probabilistic Combinatorics (2008)
N. Alon, M. Krivelevich Revised
S of size 4 so that the relation R eithercontains all \Gamma 4 2\Delta = 6 pairs of distinct members of Sor none of them. Here, the symmetric relation R consists of all pairs of friends among the...
N. Alon, I. Dinur, E. Friedgut, B. Sudakov
Abstract. We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among...
R-Linear Decision Tree, (2007)
Models Of Computation, Comput Geom, N. Alon, B. Aronov, Pankaj K. Agarwal, Pankaj K. Agarwal
ize, 2, 9, 31--32 Overmars, Mark, 27, 91 Pach, J'anos, 7, 106 Pal'asti, Ilona, 22 partition graph, 81 as a range searching data structure, 107 level of node in, 82 polyhedral, 102 primal...
Applications of Universal Hashing (2007)
H. Cannsins, Mike Saks, Omness Th Stoc, N. Alon, J. H. Spencer, The Probabilistic, ...
Greenwich CT, 1989. [11] R. Impagliazzo and L.A. Zuckerman. How to Recycle Random Bits. 30th FOCS, pages 248--253, 1989. [12] R.M. Karp, N. Pippenger, and M. Sipser. A Time-Randomness Tradeoff. AMS...
N. Alon, D. S. Gunderson, M. Molloy
For each n and k, we examine bounds on the largest number m so that for any k-coloring of the edges of Kn there exists a copy of Km whose edges receive at most k 1 colors. 1
Measures of pseudorandomness for finite sequences: typical values (2007)
Alon, N., Kohayakawa, Y., Mauduit, C., Moreira, C. G., Rödl, V.
Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈ {−1, 1}N in order to measure their ‘level of randomness’. Those...
Better Algorithms and Bounds for Directed Maximum Leaf Problems (2007)
Alon, N, Fomin, F, Gutin, Gregory, Krivelevich, M, Saurabh, S
The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...
Parameterized Algorithms for Directed Maximum Leaf Problems (2007)
Alon, N, Fomin, F, Gutin, Gregory, Krivelevich, M, Saurabh, S
We prove that finding a rooted subtree with at least $k$ leaves in a directed graph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves...
Measures of pseudorandomness for finite sequences: minimal values (2006)
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. R Ödl
Abstract. Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈ {−1, 1} N in order to measure their ‘level of randomness’. Those...
Extremal and Probabilistic Combinatorics (2006)
N. Alon, M. Krivelevich Revised
It is hard to give a rigorous definition of Combinatorics, hence we start with a few examples illustrating the area. Testing friendship relations between children some fifty years ago, the Hungarian...
Measures of pseudorandomness for finite sequences: minimal values (2006)
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. R Ödl
Abstract. Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈ {−1, 1} N in order to measure their ‘level of randomness’. Two...
Measures of pseudorandomness for finite sequences: minimal values (2006)
N. Alon, Y. Kohayakawa, C. Mauduit, C. G. Moreira, V. R Ödl
Abstract. Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN ∈ {−1, 1} N in order to measure their ‘level of randomness’. Two...
A tournament is an oriented complete graph. The feedback arc set problem for tournaments is the optimization problem of determining the minimum possible number of edges of a given input tournament T...
Algorithms with large domination ratio (2004)
Gutin, G., Alon, N., Krivelevich, M.
Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,n) is the maximum real q such that the solution x(I) obtained by A for any instance I of P...
Algorithms with large domination ratio (2004)
Gutin, G., Alon, N., Krivelevich, M.
Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,n) is the maximum real q such that the solution x(I) obtained by A for any instance I of P...
Algorithms with large domination ratio (2004)
Gutin, G., Alon, N., Krivelevich, M.
Let P be an optimization problem, and let A be an approximation algorithm for P. The domination ratio domr(A,n) is the maximum real q such that the solution x(I) obtained by A for any instance I of P...
Dense graphs are antimagic (2003)
Alon, N., Kaplan, G., Lev, A., Roditty, Y., Yuster, R.
An {\em antimagic labeling} of a graph with $m$ edges and $n$ vertices is a bijection from the set of edges to the integers $1,...,m$ such that all $n$ vertex sums are pairwise distinct, where a...
Smaller Explicit Superconcentrators (2003)
Using a new recursive technique, we present an explicit construction of an infinite family of N-superconcentrators of density 44. The most economical previously known explicit graphs of this type...
Smaller Explicit Superconcentrators (Extended Abstract) (2002)
Using a new recursive technique, we present an explicit construction of an infinite family of N-superconcentrators of density 44. The most economical previously known explicit graphs of this type...
Linear Arboricity and Linear K-Arboricity of Regular Graphs (2001)
N. Alon, V. J. Teague, N. C. Wormald
We nd upper bounds on the linear k-arboricity of d-regular graphs using a probabilistic argument. For small k these bounds are new. For large k they blend into the known upper bounds on the linear...
Alon, N, Kruyt, F A, Youssoufian, H, Buchwald, M
Despite the cloning of four disease-associated genes for Fanconi anemia (FA), the molecular pathogenesis of FA remains largely unknown. To study FA complementation group A using the mouse as a model...
A Ramsey-type problem and the Turán numbers (2000)
N. Alon, P. Erdős, D. S. Gunderson, M. Molloy
For each n and k, we examine bounds on the largest number m so that for any k-coloring of the edges of Kn there exists a copy of Km whose edges receive at most k − 1 colors. We show that for k ≥...
HUNGARIAN ACADEMY OF SCIENCES (2000)
N. Alon, D. S. Gunderson, M. Molloy
sponsor: NSERC (to MM). N. Alon, D. S. Gunderson and M. Molloy would like to dedicate this article to the memory of Paul Erdó´s.
Properly colored Hamilton cycles in edge colored complete graphs (1997)
It is shown that, for >0 and n>n0(), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than edges of the same color contains a Hamilton cycle in which...
Properly colored Hamilton cycles in edge colored complete graphs (1997)
It is shown that, for >0 and n>n0(), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than edges of the same color contains a Hamilton cycle in which...
Properly colored Hamilton cycles in edge colored complete graphs (1997)
It is shown that, for >0 and n>n0(), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than edges of the same color contains a Hamilton cycle in which...
Properly colored Hamilton cycles in edge colored complete graphs (1997)
It is shown that for every ɛ> 0 and n> n0(ɛ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 − 1 √ 2 − ɛ)n edges of the same...
A Purely Combinatorial Proof of the Hadwiger Debrunner (p, q) Conjecture (1997)
Noga Alon, N. Alon, Daniel J. Kleitman
A family of sets has the (p; q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p q d + 1 there is a c = c(p; q; d) ! 1 such...
Properly colored Hamilton cycles in edge colored complete graphs (1997)
It is shown that for every ɛ> 0 and n> n0(ɛ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 − 1 √ 2 − ɛ)n edges of the same...
The algorithmic aspects of the Regularity Lemma (1994)
N. Alon, R. A. Duke, H. Lefmann, V. Rödl, R. Yuster
The Regularity Lemma of Szemerédi is a result that asserts that every graph can be par-titioned in a certain regular way. This result has numerous applications, but its known proof is not...
The algorithmic aspects of the Regularity Lemma (1994)
N. Alon, R. A. Duke, H. Lefmann, V. Rodl, R. Yuster
The Regularity Lemma of Szemer'edi is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not...
Fault tolerant graphs, perfect hash functions and disjoint paths (1992)
Ajtai, M., Alon, N., Bruck, J., Cypher, R., Ho, C.T., Naor, M., ...
Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and...
Fault tolerant graphs, perfect hash functions and disjoint paths (1992)
M. Ajtai, N. Alon, J. Bruck, R. Cypher, C. T. Ho, M. Naor, ...
Given a graph G on n nodes we say that a graph T on n + k nodes is a k-fault tolerant version of G, if we can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still...
Identification of the cystic fibrosis gene: cloning and characterization of complementary DNA (1989)
Riordan, JR, Rommens, JM, Kerem, B, Alon, N, Rozmahel, R, Grzelczak, Z, ...
Overlapping complementary DNA clones were isolated from epithelial cell libraries with a genomic DNA segment containing a portion of the putative cystic fibrosis (CF) locus, which is on chromosome 7....
North-Holland EXPLICIT CONSTRUCTION OF LINEAR SIZED TOLERANT NETWORKS (1986)
For every E> 0 and every integer m> 0, we construct explicitly graphs with O(m/e) vertices and maximum degree 0(1/e*), such that after removing any (1- � ) portion of their vertices or edges,...
Properly colored Hamilton cycles in edge colored complete graphs
It is shown that for every ffl ? 0 and n ? n 0 (ffl), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1 \Gamma 1 p 2 \Gamma ffl)n edges of the...
Telomere maintenance and dysfunction predict recurrence in paediatric ependymoma
Tabori, U, Wong, V, Ma, J, Shago, M, Alon, N, Rutka, J, ...
We have recently described the enzymatic subunit of telomerase (hTERT) as an important prognostic marker for paediatric ependymoma. Because of the lack of good, representative pre-clinical models for...