Bubbling Solutions for the SU(3) Chern‐Simons Model on a Torus

We consider the following nonlinear system derived from the SU(3) Chern‐Simons models on a torus Ω: where $\delta_p$ denotes the Dirac measure at $p\in\Omega$ . When $\{p_j^1\}_1^{N_1}= \{p_j^2\}_1^{N_2}$ , if we look for a solution with $u_1=u_2=u$ , then (0.1) is reduced to the Chern‐Simons‐Higgs equation: The existence of bubbling solutions to (0.1) has been a longstanding problem. In this paper, we prove the existence of such solutions such that $u_1\ne u_2$ even if $\{p_j^1\}_1^{N_1}=\{p_j^2\}_1^{N_2}$ . © 2012 Wiley Periodicals, Inc.     

Disjoint cycles with chords in graphs

Let be integers, , , and let for each , be a cycle or a tree on vertices. We prove that every graph G of order at least n with contains k vertex disjoint subgraphs , where , if is a tree, and is a cycle with chords incident with a common vertex, if is a cycle. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 87–98, 2009     

Maximum number of colorings of (2k,k2)‐graphs

Let consist of all simple graphs on 2k vertices and edges. For a simple graph G and a positive integer , let denote the number of proper vertex colorings of G in at most colors, and let . We prove that and is the only extremal graph. We also prove that as . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 135–148, 2007     

Cutting two graphs simultaneously

Consider two graphs, and , on the same vertex set V, with and having edges for . We give a simple algorithm that partitions V into sets A and B such that and . We also show, using a probabilistic method, that if and belong to certain classes of graphs, (for instance, if and both have a density of at least 2/, or if and are both regular of degree at most with n sufficiently large) then we can find a partition of V into sets A and B such that for . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 19–32, 2008     

C‐perfect hypergraphs

Let ${\mathcal{H}}=({{X}},{\mathcal{E}})Let ${\mathcal{H}}=({{X}},{\mathcal{E}})$ be a hypergraph with vertex set X and edge set ${\mathcal{E}}$. A C‐coloring of ${\mathcal{H}}$ is a mapping ?:X→? such that |?(E)|<|E| holds for all edges ${{E}}\in{\mathcal{E}}$ (i.e. no edge is multicolored). We denote by $\bar{\chi}({\mathcal{H}})$ the maximum number |?(X)| of colors in a C‐coloring. Let further $\alpha({\mathcal{H}})$ denote the largest cardinality of a vertex set S?X that contains no ${{E}}\in{\mathcal{E}}$, and $\tau({\mathcal{H}})=|{{X}}|-\alpha({\mathcal{H}})$ the minimum cardinality of a vertex set meeting all $E \in {\mathcal{E}}$. The hypergraph ${\mathcal{H}}$ is called C‐perfect if $\bar{\chi}({\mathcal{H}}\prime)=\alpha({\mathcal{H}}\prime)$ holds for every induced subhypergraph ${\mathcal{H}}\prime\subseteq{\mathcal{H}}$. If ${\mathcal{H}}$ is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k∈? there exists a finite upper bound h(r, k) on the number of minimally C‐imperfect hypergraphs ${\mathcal{H}}$ with $\tau({\mathcal{H}})\le {{k}}$ and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010     

A better bound for the cop number of general graphs

In this note, we prove that the cop number of any n‐vertex graph G, denoted by , is at most . Meyniel conjectured . It appears that the best previously known sublinear upper‐bound is due to Frankl, who proved . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 45–48, 2008     

The cover time of random geometric graphs

We study the cover time of random geometric graphs. Let $I(d)=[0,1]^{d}$ denote the unit torus in d dimensions. Let $D(x,r)$ denote the ball (disc) of radius r. Let $\Upsilon_d$ be the volume of the unit ball $D(0,1)$ in d dimensions. A random geometric graph $G=G(d,r,n)$ in d dimensions is defined as follows: Sample n points V independently and uniformly at random from $I(d)$ . For each point x draw a ball $D(x,r)$ of radius r about x. The vertex set $V(G)=V$ and the edge set $E(G)=\{\{v,w\}: w\ne v,\,w\in D(v,r)\}$ . Let $G(d,r,n),\,d\geq 3$ be a random geometric graph. Let $C_G$ denote the cover time of a simple random walk on G. Let $c>1$ be constant, and let $r=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011     

Circular chromatic index of Cartesian products of graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are incident. Let □ , where □ denotes Cartesian product and H is an ‐regular graph of odd order, with (thus, G is s‐regular). We prove that , where is the minimum, over all bases of the cycle space of H, of the maximum length of a cycle in the basis. When and m is large, the lower bound is sharp. In particular, if , then □ , independent of m. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 7–18, 2008     

Enumeration of generalized Hadamard matrices of order 16 and related designs

We investigate signings of symmetric GDD( , 16, )s over for . Beginning with , at each stage of this process a signing of a GDD( , 16, ) produces a GDD( , 16, ). The initial GDDs ( ) correspond to Hadamard matrices of order 16. For , the GDDs are semibiplanes of order 16, and for the GDDs are semiplanes of order 16 which can be extended to projective planes of order 16. In this article, we completely enumerate such signings which include all generalized Hadamard matrices of order 16. We discuss the generation techniques and properties of the designs obtained during the search. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 119–135, 2009     

Regularized trace of the inverse of the dirichlet laplacian

For the eigenvalues $( \lambda_{n}) _{n=1}^{\infty}$ of the Dirichlet Laplacian on a bounded convex domain $\font\open=msbm10 at 10pt\def\C{\hbox{\open C}}\Omega\subset{\C}$ , we find the sum of the series the regularized trace of the inverse of Dirichlet Laplacian. © 2011 Wiley Periodicals, Inc.     

A critical center‐stable manifold for Schrödinger's equation in three dimensions

Consider the focusing $\dot H^{1/2}$ ‐critical semilinear Schrödinger equation in $\font\open=msbm10 at 10pt\def\R{\hbox{\open R}}\R^3$ It admits an eight‐dimensional manifold of special solutions called ground state solitons. We exhibit a codimension‐1 critical real analytic manifold ${\cal N}$ of asymptotically stable solutions of (0.1) in a neighborhood of the soliton manifold. We then show that ${\cal N}$ is center‐stable, in the dynamical systems sense of Bates and Jones, and globally‐in‐time invariant. Solutions in ${\cal N}$ are asymptotically stable and separate into two asymptotically free parts that decouple in the limit—a soliton and radiation. Conversely, in a general setting, any solution that stays $\dot H^{1/2}$ ‐close to the soliton manifold for all time is in ${\cal N}$ . The proof uses the method of modulation. New elements include a different linearization and an endpoint Strichartz estimate for the time‐dependent linearized equation. The proof also uses the fact that the linearized Hamiltonian has no nonzero real eigenvalues or resonances. This has recently been established in the case treated here—of the focusing cubic NLS in $\font\open=msbm10 at 10pt\def\R{\hbox{\open R}}\R^3$ —by the work of Marzuola and Simpson and Costin, Huang, and Schlag. © 2012 Wiley Periodicals, Inc.     

Persistence of activity in threshold contact processes,an “Annealed approximation” of random Boolean networks

We consider a model for gene regulatory networks that is a modification of Kauffmann's J Theor Biol 22 (1969), 437–467 random Boolean networks. There are three parameters: $n = {\rm the}$ number of nodes, $r = {\rm the}$ number of inputs to each node, and $p = {\rm the}$ expected fraction of 1'sin the Boolean functions at each node. Following a standard practice in thephysics literature, we use a threshold contact process on a random graph on n nodes, in which each node has in degree r, to approximate its dynamics. We show that if $r\ge 3$ and $r \cdot 2p(1-p)>1$ , then the threshold contact process persists for a long time, which correspond to chaotic behavior of the Boolean network. Unfortunately, we are only able to prove the persistence time is $\ge \exp(cn^{b(p)})$ with $b(p)>0$ when $r\cdot 2p(1-p)> 1$ , and $b(p)=1$ when $(r-1)\cdot 2p(1-p)>1$ . © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Graph classes characterized both by forbidden subgraphs and degree sequences

Given a set of graphs, a graph G is ‐free if G does not contain any member of as an induced subgraph. We say that is a degree‐sequence‐forcing set if, for each graph G in the class of ‐free graphs, every realization of the degree sequence of G is also in . We give a complete characterization of the degree‐sequence‐forcing sets when has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131–148, 2008     

A system of equations for describing cocyclic Hadamard matrices

Given a basis for 2‐cocycles over a group G of order , we describe a nonlinear system of 4t‐1 equations and k indeterminates over , whose solutions determine the whole set of cocyclic Hadamard matrices over G, in the sense that ( ) is a solution of the system if and only if the 2‐cocycle gives rise to a cocyclic Hadamard matrix . Furthermore, the study of any isolated equation of the system provides upper and lower bounds on the number of coboundary generators in which have to be combined to form a cocyclic Hadamard matrix coming from a special class of cocycles. We include some results on the families of groups and . A deeper study of the system provides some more nice properties. For instance, in the case of dihedral groups , we have found that it suffices to check t instead of the 4t rows of , to decide the Hadamard character of the matrix (for a special class of cocycles f). © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 276–290, 2008     

Ore‐type condition for the existence of connected factors

In this article, we obtain some Ore‐type sufficient conditions for a graph to have a connected factor with degree restrictions. Let α and k be positive integers with if and if . Let G be a connected graph with a spanning subgraph F, each component of which has order at least α. We show that if the degree sum of two nonadjacent vertices is greater than then G has a connected subgraph in which F is contained and every vertex has degree at most . From the result, we derive that a graph G has a connected ‐factor if the degree sum of two nonadjacent vertices is at least . © Wiley Periodicals, Inc. J. Graph Theory 56: 241–248, 2007     

A note on complete subdivisions in digraphs of large outdegree

Mader conjectured that for all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order . In this note, we observe that if the minimum outdegree of a digraph is sufficiently large compared to its order then one can even guarantee a subdivision of a large complete digraph. More precisely, let be a digraph of order n whose minimum outdegree is at least d. Then contains a subdivision of a complete digraph of order . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 1–6, 2008     

On the existence of a rainbow 1‐factor in 1‐factorizations of K

Let be a 1‐factorization of the complete uniform hypergraph with and . We show that there exists a 1‐factor of whose edges belong to n different 1‐factors in . Such a 1‐factor is called a “rainbow” 1‐factor or an “orthogonal” 1‐factor. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 487–490, 2007     

Random mappings with exchangeable in‐degrees

In this article we introduce a new random mapping model, , which maps the set {1,2,…,n} into itself. The random mapping is constructed using a collection of exchangeable random variables which satisfy . In the random digraph, , which represents the mapping , the in‐degree sequence for the vertices is given by the variables , and, in some sense, can be viewed as an analogue of the general independent degree models from random graph theory. We show that the distribution of the number of cyclic points, the number of components, and the size of a typical component can be expressed in terms of expectations of various functions of . We also consider two special examples of which correspond to random mappings with preferential and anti‐preferential attachment, respectively, and determine, for these examples, exact and asymptotic distributions for the statistics mentioned above. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On k‐detour subgraphs of hypercubes

A spanning subgraph G of a graph H is a k‐detour subgraph of H if for each pair of vertices , the distance, , between x and y in G exceeds that in H by at most k. Such subgraphs sometimes also are called additive spanners. In this article, we study k‐detour subgraphs of the n‐dimensional cube, , with few edges or with moderate maximum degree. Let denote the minimum possible maximum degree of a k‐detour subgraph of . The main result is that for every and On the other hand, for each fixed even and large n, there exists a k‐detour subgraph of with average degree at most . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 55–64, 2008     

Increasing the output length of zero‐error dispersers

Let $\cal{C}$ be a class of probability distributions over a finite set Ω. A function $D : \Omega \mapsto\{0,1\}^{m}$ is a disperser for $\cal{C}$ with entropy threshold $k$ and error $\epsilon$ if for any distribution X in $\cal{C}$ such that X gives positive probability to at least $2^{k}$ elements we have that the distribution $D(X)$ gives positive probability to at least $(1-\epsilon)2^{m}$ elements. A long line of research is devoted to giving explicit (that is polynomial time computable) dispersers (and related objects called “extractors”) for various classes of distributions while trying to maximize m as a function of k. For several interesting classes of distributions there are explicit constructions in the literature of zero‐error dispersers with “small” output length m. In this paper we develop a general technique to improve the output length of zero‐error dispersers. This strategy works for several classes of sources and is inspired by a transformation that improves the output length of extractors (which was given by Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity, (2006) 46–60.) building on earlier work by Gabizon, Raz and Shaltiel (SIAM J Comput 36 (2006) 1072–1094). Our techniques are different than those of Shaltiel (CCC'06; Proceedings of the 21st Annual IEEE Conference on Computational Complexity (2006) 46–60) and in particular give non‐trivial results in the errorless case. Using our approach we construct improved zero‐error 2‐source dispersers. More precisely, we show that for any constant $\delta >0$ there is a constant $\eta >0$ such that for sufficiently large n there is a poly‐time computable function $D :\{0,1\}^{n}\times\{0,1\}^{n}\mapsto\{0,1\}^{\eta n}$ such that for every two independent distributions $X_1,X_2$ over $\{0,1\}^{n}$ each with support size at least $2^{\delta n}$ , the output distribution $D(X_1,X_2)$ has full support. This improves the output length of previous constructions by Barak, Kindler, Shaltiel, Sudakov and Wigderson (Proceedings of the 37th Annual ACM Symposium on Theory of Computing (2005) 1–10) and has applications in Ramsey theory and in improved constructions of certain data structures from the work of Fiat and Naor [SIAM J Comput 22 (1993)]. We also use our techniques to give explicit constructions of zero‐error dispersers for bit‐fixing sources and affine sources over polynomially large fields. These constructions improve the best known explicit constructions due to Rao (unpublished data) and Gabizon and Raz [Combinatorica 28 (2008)] and achieve $m=\Omega(k)$ for bit‐fixing sources and $m=k-o(k)$ for affine sources over polynomial size fields. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011