text:
# Discrete Mathematics: Methods and Challenges

## 1 . Introduction

The originators of the basic concepts of Discrete Mathematics, the mathematics of finite structures, were the Hindus, who knew the formulas for the number of permutations of a set of $`n`$ elements, and for the number of subsets of cardinality $`k`$ in a set of $`n`$ elements, already in the sixth century. The beginning of Combinatorics as we know it today started with the work of Pascal and De Moivre in the $`17`$th century, and continued in the $`18`$th century with the seminal ideas of Euler in Graph Theory, with his work on partitions and their enumeration, and with his interest in latin squares. These old results are among the roots of the study of formal methods of enumeration, the development of configurations and designs, and the extensive work on Graph Theory in the last two centuries. The tight connection between Discrete Mathematics and Theoretical Computer Science, and the rapid development of the latter in recent years, led to an increased interest in combinatorial techniques and to an impressive development of the subject. It also stimulated the study of algorithmic combinatorics and combinatorial optimization.

While many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, without relying on many deep, well developed tools, the modern theory has already grown out of this early stage. There are already well developed enumeration methods, some of which are based on deep algebraic tools. The probabilistic method initiated by Erdős (and to some extent, by Shannon) became one of the most powerful tools in the modern theory, and its study has been fruitful to Combinatorics, as well as to Probability Theory. Algebraic and topological techniques play a crucial role in the modern theory, and Polyhedral Combinatorics, Linear Programming and constructions of designs have been developed extensively. Most of the new significant results obtained in the area are inevitably based on the knowledge of these well developed concepts and techniques, and while there is, of course, still a lot of room for pure ingenuity in Discrete Mathematics, much of the progress is obtained by relying on the fast growing accumulated body of knowledge.

Concepts and questions of Discrete Mathematics appear naturally in many branches of mathematics, and the area has found applications in other disciplines as well. These include applications in Information Theory and Electrical Engineering, in Statistical Physics, in Chemistry and Molecular Biology, and, of course, in Computer Science. Combinatorial topics such as Ramsey Theory, Combinatorial Set Theory, Matroid Theory, Extremal Graph Theory, Combinatorial Geometry and Discrepancy Theory are related to a large part of the mathematical and scientific world, and these topics have already found numerous applications in other fields. A detailed account of the topics, methods and applications of Combinatorics can be found in .

This paper is mostly a survey of two of the main general techniques that played a crucial role in the development of modern combinatorics; algebraic methods and probabilistic methods. Both will be illustrated by examples, focusing on the basic ideas and the connection to other areas. The choice of topics and examples described here is inevitably biased, and is not meant to be comprehensive. Yet, it hopefully provides some of the flavor of the techniques, problems and results in the area in a way which may be appealing to researchers, even if their main interest is not Discrete Mathematics.

## 2 . Dimension, geometry and information theory

Various algebraic techniques have been used successfully in tackling problems in Discrete Mathematics over the years. These include tools from Representation Theory applied extensively in enumeration problems, spectral techniques used in the study of highly regular structures, and applications of properties of polynomials and tools from algebraic geometry in the theory of Error Correcting Codes and in the study of problems in Combinatorial Geometry. These techniques have numerous interesting applications. Yet, the most fruitful algebraic technique applied in combinatorics, which is possibly also the simplest one, is the so-called dimension argument. In its simplest form, the method can be described as follows. In order to bound the cardinality of a discrete structure $`A`$, one maps its elements to vectors in a linear space, and shows that the set $`A`$ is mapped to a linearly independent set. It then follows that the cardinality of $`A`$ is bounded by the dimension of the corresponding linear space. This method is often particularly useful in the solution of extremal problems in which the extremal configuration is not unique. The method is effective in such cases because bases in a vector space can be very different from each other and yet all of them have the same cardinality. Many applications of this basic idea can be found in , , .

### 2.1. Combinatorial geometry

An early application of the dimension argument appears in . A set of points $`AR^n`$ is a two-distance set if at most $`2`$ distinct positive distances are determined by the points of $`A`$. Let $`f(n,2)`$ denote the maximum possible size of a two-distance set in $`R^n`$. The set of all $`0/1`$ vectors in $`R^{n+1}`$ with exactly two $`1`$’s shows that $`f(n,2)n(n+1)/2`$, and the authors of  proved that $`f(n,2)(n+1)(n+4)/2`$. The upper bound is proved by associating each point of a two-distance set $`A`$ with a polynomial in $`n`$ variables, and by showing that these polynomials are linearly independent and all lie in a space of dimension $`(n+1)(n+4)/2`$. This has been improved by Blokhuis to $`(n+1)(n+2)/2`$, by showing that one can add $`n+1`$ additional polynomials that lie in this space to those obtained from the two-distance set, keeping the augmented set linearly independent. See  and its references for more details. The precise value of $`f(n,2)`$ is not known.

Borsuk  asked if any compact set of at least $`2`$ points in $`R^d`$ can be partitioned into at most $`d+1`$ subsets of smaller diameter. Let $`m(d)`$ be the smallest integer $`m`$ so that any such set can be partitioned into a most $`m`$ subsets of smaller diameter. Borsuk’s question is whether $`m(d)=d+1`$ (the $`d+1`$ points of a simplex show that $`m(d)`$ is at least $`d+1`$.) Kahn and Kalai  gave an example showing that this is not the case for all sufficiently large $`d`$, by applying a theorem of Frankl and Wilson . Improved versions of their construction have been obtained by Nilli in 1994, by Raigorodski in 1997, by Hinrichs in 2001 and by Hinrichs and Richter in 2002. The last two results are based on some properties of the Leech Lattice and give a construction showing that already in dimension $`d=298`$, more than $`d+1`$ subsets may be needed. All the constructions and the proofs of their properties are based on the dimension argument. Here is a brief sketch of one of them.

Let $`n=4p`$, where $`p`$ is an odd prime, and let $``$ be the set of all vectors $`𝐱=(x_1,\mathrm{},x_n)\{1,1\}^n`$, where $`x_1=1`$ and the number of negative coordinates of $`𝐱`$ is even. One first proves the following.

If $`𝒢`$ contains no two orthogonal vectors then $`|𝒢|_{i=0}^{p1}\left(\genfrac{}{}{0pt}{}{n1}{i}\right).`$  (1)
This is done by associating each member of $`𝒢`$ with a multilinear polynomial of degree at most $`p1`$ in $`n1`$ variables, so that all the obtained polynomials are linearly independent. Having established (1), define $`S=\{𝐱𝐱:𝐱\}`$, where $``$ is as above, and $`𝐱𝐱`$ is the tensor product of $`𝐱`$ with itself, i.e., the vector of length $`n^2`$, $`(x_{ij}:1i,jn)`$, where $`x_{ij}=x_ix_j`$. The norm of each vector in $`S`$ is $`n`$ and the scalar product between any two members of $`S`$ is non-negative. Moreover, by (1) any set of more than $`_{i=0}^{p1}\left(\genfrac{}{}{0pt}{}{n1}{i}\right)`$ members of $`S`$ contains an orthogonal pair, i.e., two points the distance between which is the diameter of $`S`$. It follows that $`S`$ cannot be partitioned into less than $`2^{n2}/_{i=0}^{p1}\left(\genfrac{}{}{0pt}{}{n1}{i}\right)`$ subsets of smaller diameter. This shows that $`m(d)c_1^\sqrt{d}`$ for some $`c_1>1`$. An upper bound of $`m(d)c_2^d`$ where $`c_2=\sqrt{3/2}+o(1)`$ is known, but determining the correct order of magnitude of $`m(d)`$ is an open question. The following conjecture seems plausible.

###### Conjecture 2.1

There is a constant $`c>1`$ such that $`m(d)>c^d`$ for all $`d1`$.

An equilateral set (or a simplex) in a metric space, is a set $`A`$, so that the distance between any pair of distinct members of $`A`$ is $`b`$, where $`b0`$ is a constant. Trivially, the maximum cardinality of such a set in $`R^n`$ with respect to the (usual) $`l_2`$-norm is $`n+1`$. Somewhat surprisingly, the situation is far more complicated for the $`l_1`$ norms. The $`l_1`$-distance between two points $`\stackrel{}{a}=(a_1,\mathrm{}a_n)`$ and $`\stackrel{}{b}=(b_1,\mathrm{},b_n)`$ in $`R^n`$ is $`\stackrel{}{a}\stackrel{}{b}_1=(_{k=1}^n|a_ib_i|`$. Let $`e(l_1^n)`$ denote the maximum possible cardinality of an equilateral set in $`l_1^n`$. The set of standard basis vectors and their negatives shows that $`e(l_1^n)2n`$. Kusner  conjectured that this is tight, i.e., that $`e(l_1^n)=2n`$ for all $`n`$. For $`n4`$ this is proved in . For general $`n`$, the best known upper bound is $`e(l_1^n)c_1n\mathrm{log}n`$ for some absolute positive constant $`c_1`$. This is proved in  by an appropriate dimension argument. Each vector in an equilateral set of $`m`$ vectors in $`R^n`$ is mapped to a vector in $`l_2^t`$ for an appropriate $`t=t(m,n)`$, by applying a probabilistic technique involving randomized rounding. It is then shown, using a simple argument based on the eigenvalues of the Gram matrix of these new vectors, that they span a space of dimension at least $`c_2m`$, implying that $`c_2mt(m,n)`$ and supplying the desired result. The precise details require some work, and can be found in .

### 2.2. Capacities and graph powers

Let $`G=(V,E)`$ be a simple, undirected graph. The power $`G^n`$ of $`G`$ is the graph whose set of vertices is $`V^n`$ in which two distinct vertices $`(u_1,u_2,\mathrm{},u_n)`$ and $`(v_1,v_2,\mathrm{},v_n)`$ are adjacent iff for all $`i`$ between $`1`$ and $`n`$ either $`u_i=v_i`$ or $`u_iv_iE`$. The Shannon capacity $`c(G)`$ of $`G`$ is the limit $`lim_n\mathrm{}(\alpha (G^n))^{1/n}`$, where $`\alpha (G^n)`$ is the maximum size of an independent set of vertices in $`G^n`$. This limit exists, by super-multiplicativity, and it is always at least $`\alpha (G)`$.

The study of this parameter was introduced by Shannon in , motivated by a question in Information Theory. Indeed, if $`V`$ is the set of all possible letters a channel can transmit in one use, and two letters are adjacent if they may be confused, then $`\alpha (G^n)`$ is the maximum number of messages that can be transmitted in $`n`$ uses of the channel with no danger of confusion. Thus $`c(G)`$ represents the number of distinct messages per use the channel can communicate with no error while used many times.

Calculation of $`c(G)`$ seems to be very hard. For example $`c(C_5)=\sqrt{5}`$ was only shown in 1979 by Lovász , and $`c(C_7)`$ remains unknown. Certain polynomially computable upper bounds on $`c(G)`$ are known including Lovász’s theta function $`\theta (G)`$, and other upper bounds are due to Haemers and to Schrijver.

Another upper bound, based on the dimension argument and related to the bound of Haemers , is described in , where it is applied to solve a problem of Shannon on the capacity of the disjoint union of two graphs. The (disjoint) union of two graphs $`G`$ and $`H`$, denoted by $`G+H`$, is the graph whose vertex set is the disjoint union of the vertex sets of $`G`$ and of $`H`$ and whose edge set is the (disjoint) union of the edge sets of $`G`$ and $`H`$. If $`G`$ and $`H`$ are graphs of two channels, then their union represents the sum of the channels corresponding to the situation where either one of the two channels may be used, a new choice being made for each transmitted letter. Shannon proved that for every $`G`$ and $`H`$, $`c(G+H)c(G)+c(H)`$ and that equality holds in many cases. He conjectured that in fact equality always holds. In  it is shown that this is false in the following strong sense.

###### Theorem 2.2

For every $`k`$ there is a graph $`G`$ so that the Shannon capacity of the graph and that of its complement $`\overline{G}`$ satisfy $`c(G)k,c(\overline{G})k`$, whereas $`c(G+\overline{G})k^{(1+o(1))\frac{\mathrm{log}k}{8\mathrm{log}\mathrm{log}k}}`$ and the $`o(1)`$-term tends to zero as $`k`$ tends to infinity.

Therefore, the capacity of the disjoint union of two graphs can be much bigger than the capacity of each of the two graphs. Strangely enough, it is not even known if the maximum possible capacity of a disjoint union of two graphs $`G`$ and $`H`$, each of capacity at most $`k`$, is bounded by any function of $`k`$. It seems very likely that this is the case.

## 3 . Polynomials, addition and graph coloring

The study of algebraic varieties, that is, sets of common roots of systems of polynomials, is the main topic of algebraic geometry. The most elementary property of a univariate nonzero polynomial over a field is the fact that it does not have more roots than its degree. This elementary property is surprisingly effective in Combinatorics: it plays a major role in the theory of error correcting codes, and has many applications in the study of finite geometries — see, e.g., . A similar property holds for polynomials of several variables, and can also be used to supply results in Discrete Mathematics. In this section we describe a general result of this type, which is called in  Combinatorial Nullstellensatz, and briefly sketch some of its applications in Additive Number Theory and in Graph Theory.

### 3.1. Combinatorial nullstellensatz

Hilbert’s Nullstellensatz (see, e.g., ) is the fundamental theorem that asserts that if $`F`$ is an algebraically closed field, and $`f,g_1,\mathrm{},g_m`$ are polynomials in the ring of polynomials $`F[x_1,\mathrm{},x_n]`$, where $`f`$ vanishes over all common zeros of $`g_1,\mathrm{},g_m`$, then there is an integer $`k`$ and polynomials $`h_1,\mathrm{},h_m`$ in $`F[x_1,\mathrm{},x_n]`$ so that

$$f^k=\underset{i=1}{\overset{n}{}}h_ig_i.$$

In the special case $`m=n`$, where each $`g_i`$ is a univariate polynomial of the form $`_{sS_i}(x_is)`$ for some $`S_iF`$, a stronger conclusion holds. It can be shown that if $`F`$ is an arbitrary field, $`f,g_i,S_i`$ are as above, and $`f`$ vanishes over all the common zeros of $`g_1,\mathrm{},g_n`$ (that is; $`f(s_1,\mathrm{},s_n)=0`$ for all $`s_iS_i`$), then there are polynomials $`h_1,\mathrm{},h_nF[x_1,\mathrm{},x_n]`$ satisfying $`deg(h_i)deg(f)deg(g_i)`$ so that

$$f=\underset{i=1}{\overset{n}{}}h_ig_i.$$

As a consequence of the above one can prove the following.

###### Theorem 3.1

Let $`F`$ be an arbitrary field, and let $`f=f(x_1,\mathrm{},x_n)`$ be a polynomial in $`F[x_1,\mathrm{},x_n]`$. Suppose the degree $`deg(f)`$ of $`f`$ is $`_{i=1}^nt_i`$, where each $`t_i`$ is a nonnegative integer, and suppose the coefficient of $`_{i=1}^nx_i^{t_i}`$ in $`f`$ is nonzero. If $`S_1,\mathrm{},S_n`$ are subsets of $`F`$ with $`|S_i|>t_i`$, then there are $`s_1S_1,s_2S_2,\mathrm{},s_nS_n`$ so that

$$f(s_1,\mathrm{},s_n)0.$$

The detailed proof, as well as many applications, can be found in . A quick application, first proved in , is the assertion that for any prime $`p`$, any loopless graph $`G=(V,E)`$ with average degree bigger than $`2p2`$ and maximum degree at most $`2p1`$ contains a $`p`$-regular subgraph.

To prove it, let $`(a_{v,e})_{vV,eE}`$ denote the incidence matrix of $`G`$ defined by $`a_{v,e}=1`$ if $`ve`$ and $`a_{v,e}=0`$ otherwise. Associate each edge $`e`$ of $`G`$ with a variable $`x_e`$ and consider the polynomial

$$f=\underset{vV}{}[1(\underset{eE}{}a_{v,e}x_e)^{p1}]\underset{eE}{}(1x_e),$$

over $`GF(p)`$. Applying Theorem 3.1 with $`t_i=1`$ and $`S_i=\{0,1\}`$ for all $`i`$, we conclude that there are values $`x_e\{0,1\}`$ such that $`f(x_e:eE)0`$. It is now easy to check that in the subgraph consisting of all edges $`eE`$ for which $`x_e=1`$ all degrees are divisible by $`p`$, and since the maximum degree is smaller than $`2p`$ all positive degrees are precisely $`p`$, as needed.

Pyber applied the above result to solve a problem of Erdős and Sauer and prove that any simple graph on $`n`$ vertices with at least $`200n\mathrm{log}n`$ edges contains a $`3`$-regular subgraph. Pyber, Rödl and Szemerédi proved that this is not very far from being best possible, by showing, using probabilistic arguments, that there are simple graphs on $`n`$ vertices with at least $`cn\mathrm{log}\mathrm{log}n`$ edges that contain no $`3`$-regular subgraphs. See  for some further related results.

### 3.2. Additive number theory

The Cauchy-Davenport Theorem, which has numerous applications in Additive Number Theory, is the statement that if $`p`$ is a prime, and $`A,B`$ are two nonempty subsets of $`Z_p`$, then

$$|A+B|min\{p,|A|+|B|1\}.$$

Cauchy proved this theorem in 1813, and applied it to give a new proof to a lemma of Lagrange in his well known 1770 paper that shows that every positive integer is a sum of four squares. Davenport formulated the theorem as a discrete analogue of a conjecture of Khintchine about the Schnirelman density of the sum of two sequences of integers. There are numerous extensions of this result, see, e.g., . A simple algebraic proof of this result is given in , and its main advantage is that it extends easily and gives several related results. This proof can be described as a simple application of Theorem 3.1. If $`|A|+|B|>p`$, then the result is trivial, as the sets $`A`$ and $`gB`$ intersect, for each $`gZ_p`$. Otherwise, assuming the result is false and $`|A+B||A|+|B|2`$, let $`C`$ be a subset of $`Z_p`$ satisfying $`A+BC`$ and $`|C|=|A|+|B|2`$. Define $`f=f(x,y)=_{cC}(x+yc)`$ and apply Theorem 3.1 with $`t_1=|A|1,t_2=|B|1`$, $`S_1=A,S_2=B`$ to get a contradiction.

Using similar (though somewhat more complicated) arguments, the following related result is proved in .

###### Proposition 3.2

Let $`p`$ be a prime, and let $`A_0,A_1,\mathrm{},A_k`$ be nonempty subsets of the cyclic group $`Z_p`$. If $`|A_i||A_j|`$ for all $`0i<jk`$ and $`_{i=0}^k|A_i|p+\left(\genfrac{}{}{0pt}{}{k+2}{2}\right)1`$ then

$$|\{a_0+a_1+\mathrm{}+a_k:a_iA_i,a_ia_j\text{for all}ij\}|\underset{i=0}{\overset{k}{}}|A_i|\left(\genfrac{}{}{0pt}{}{k+2}{2}\right)+1.$$

The very special case of this proposition in which $`k=1`$, $`A_0=A`$ and $`A_1=A\{a\}`$ for an arbitrary element $`aA`$ implies that if $`AZ_p`$ and $`2|A|1p+2`$ then the number of sums $`a_1+a_2`$ with $`a_1,a_2A`$ and $`a_1a_2`$ is at least $`2|A|3`$. This supplies a short proof of a result of Dias Da Silva and Hamidoune , which settles a conjecture of Erdős and Heilbronn (cf., e.g., ).

Snevily  conjectured that for any two sets $`A`$ and $`B`$ of equal cardinality in any abelian group of odd order, there is a renumbering $`a_i,b_i`$ of the elements of $`A`$ and $`B`$ so that all sums $`a_i+b_i`$ are pairwise distinct.

For the cyclic group $`Z_p`$ of prime order, this follows easily from Theorem 3.1 by considering the polynomial $`f=_{i<j}(x_ix_j)_{i<j}(a_i+x_ia_jx_j)`$ with $`S_1=\mathrm{}=S_k=B`$.

More generally, Dasgupta et al.  proved the conjecture for any cyclic group of odd order, by applying the polynomial method for polynomials over $`Q[\omega ]`$, where $`\omega `$ is an appropriate root of unity, and by considering $`G`$ as a subgroup of the multiplicative group of this field. Further related results appear in .

Additional applications of Theorem 3.1 in additive number theory can be found in .

### 3.3. Graph coloring

Theorem 3.1 has various applications in the study of Graph Coloring, which is the most popular area in Graph Theory. We sketch below the basic approach, following . See also ,  for a related method.

A vertex coloring of a graph $`G`$ is an assignment of a color to each vertex of $`G`$. The coloring is proper if adjacent vertices get distinct colors. The chromatic number $`\chi (G)`$ of $`G`$ is the minimum number of colors used in a proper vertex coloring of $`G`$. An edge coloring of $`G`$ is, similarly, an assignment of a color to each edge of $`G`$. It is proper if adjacent edges receive distinct colors. The minimum number of colors in a proper edge coloring of $`G`$ is the chromatic index $`\chi ^{}(G)`$ of $`G`$. This is equal to the chromatic number of the line graph of $`G`$.

A graph $`G=(V,E)`$ is $`k`$-choosable if for every assignment of sets of integers $`S(v)Z`$, each of size $`k`$, to the vertices $`vV`$, there is a proper vertex coloring $`c:VZ`$ so that $`c(v)S(v)`$ for all $`vV`$. The choice number of $`G`$, denoted by $`ch(G)`$, is the minimum integer $`k`$ so that $`G`$ is $`k`$-choosable. Obviously, this number is at least the chromatic number $`\chi (G)`$ of $`G`$. The choice number of the line graph of $`G`$, denoted by $`ch^{}(G)`$, is usually called the list chromatic index of $`G`$, and it is clearly at least the chromatic index $`\chi ^{}(G)`$ of $`G`$.

The study of choice numbers was introduced, independently, by Vizing  and by Erdős, Rubin and Taylor . There are many graphs $`G`$ for which the choice number $`ch(G)`$ is strictly larger than the chromatic number $`\chi (G)`$ (a complete bipartite graph with $`3`$ vertices in each color class is one such example). In view of this, the following conjecture, suggested independently by various researchers including Vizing, Albertson, Collins, Tucker and Gupta, which apparently appeared first in print in , is somewhat surprising.

###### Conjecture 3.3

( The list coloring conjecture) For every graph $`G`$, $`ch^{}(G)=\chi ^{}(G)`$.

This conjecture asserts that for line graphs there is no gap at all between the choice number and the chromatic number. Many of the most interesting results in the area are proofs of special cases of this conjecture, which is still wide open.

The graph polynomial $`f_G=f_G(x_1,x_2,\mathrm{},x_n)`$ of a graph $`G=(V,E)`$ on a set $`V=\{1,\mathrm{},n\}`$ of $`n`$ vertices is defined by $`f_G(x_1,x_2,\mathrm{},x_n)=\mathrm{\Pi }\{(x_ix_j):i<j,ijE\}`$. This polynomial has been studied by various researchers, starting already with Petersen  in 1891.

Note that if $`S_1,\mathrm{},S_n`$ are sets of integers, then there is a proper coloring assigning to each vertex $`i`$ a color from its list $`S_i`$, if and only if there are $`s_iS_i`$ such that $`f_G(s_1,\mathrm{},s_n)0`$. This condition is precisely the one appearing in the conclusion of Theorem 3.1, and it is therefore natural to expect that this theorem can be useful in tackling coloring problems. By applying it to line graphs of planar cubic graphs, and by interpreting the appropriate coefficient of the corresponding polynomial combinatorially, it can be shown, using a known result of Vigneron  and the Four Color Theorem, that the list chromatic index of every $`2`$-connected cubic planar graph is $`3`$. This is a strengthening of the Four Color Theorem, which is well known to be equivalent to the fact that the chromatic index of any such graph is $`3`$. An extension of this result appears in .

Additional results on graph coloring and choice numbers using the above algebraic approach are described in the survey . These include the fact that the choice number of every planar bipartite graph is at most $`3`$, thus solving a conjecture raised in , and the assertion, proved in , that if $`G`$ is a graph on $`3n`$ vertices, whose set of edges is the disjoint union of a Hamilton cycle and $`n`$ pairwise vertex-disjoint triangles, then the choice number and the chromatic number of $`G`$ are both $`3`$.

## 4 . The probabilistic method

The discovery that deterministic statements can be proved by probabilistic reasoning, led already in the middle of the previous century to several striking results in Analysis, Number Theory, Combinatorics and Information Theory. It soon became clear that the method, which is now called the probabilistic method, is a very powerful tool for proving results in Discrete Mathematics. The early results combined combinatorial arguments with fairly elementary probabilistic techniques, whereas the development of the method in recent years required the application of more sophisticated tools from Probability Theory. In this section we illustrate the method and describe several recent results. More material can be found in the recent books , ,  and .

### 4.1. Thresholds for random properties

The systematic study of Random Graphs was initiated by Erdős and Rényi whose first main paper on the subject is . Formally, $`G(n,p)`$ denotes the probability space whose points are graphs on a fixed set of $`n`$ labelled vertices, where each pair of vertices forms an edge, randomly and independently, with probability $`p`$. The term “the random graph $`G(n,p)`$” means, in this context, a random point chosen in this probability space. Each graph property $`A`$ (that is, a family of graphs closed under graph isomorphism) is an event in this probability space, and one may study its probability $`Pr[A]`$, that is, the probability that the random graph $`G(n,p)`$ lies in this family. In particular, we say that $`A`$ holds almost surely if the probability that $`G(n,p)`$ satisfies $`A`$ tends to $`1`$ as $`n`$ tends to infinity. There are numerous papers dealing with random graphs, and the two recent books ,  provide excellent extensive accounts of the known results in the subject.

One of the important discoveries of Erdös and Rényi was the discovery of threshold functions. A function $`r(n)`$ is called a threshold function for a graph property $`A`$, if when $`p(n)/r(n)`$ tends to $`0`$, then $`G(n,p(n))`$ does not satisfy $`A`$ almost surely, whereas when $`p(n)/r(n)`$ tends to infinity, then $`G(n,p(n))`$ satisfies $`A`$ almost surely. Thus, for example, they identified the threshold function for the property of being connected very precisely: if $`p(n)=\frac{\mathrm{ln}n}{n}+\frac{c}{n}`$, then, as $`n`$ tends to infinity, the probability that $`G(n,p(n))`$ is connected tends to $`e^{e^c}`$.

A graph property is monotone if it is closed under the addition of edges. Note that many interesting graph properties, like hamiltonicity, non-planarity, connectivity or containing at least $`10`$ vertex disjoint triangles are monotone.

Bollobás and Thomason  proved that any monotone graph property has a threshold function. Their proof applies to any monotone family of subsets of a finite set, and holds even without the assumption that the property $`A`$ is closed under graph isomorphism.

Friedgut and Kalai  showed that the symmetry of graph properties can be applied to obtain a sharper result. They proved that for any monotone graph property $`A`$, if $`G(n,p)`$ satisfies $`A`$ with probability at least $`ϵ`$, then $`G(n,q)`$ satisfies $`A`$ with probability at least $`1ϵ`$, for $`q=p+O(\mathrm{log}(1/2ϵ)/\mathrm{log}n).`$

The proof follows by combining two results. The first is a simple but fundamental lemma of Margulis  and Russo , which is useful in Percolation Theory. This lemma can be used to express the derivative with respect to $`p`$ of the probability that $`G(n,p)`$ satisfies $`A`$ as a sum of contributions associated with the single potential edges. The second result is a theorem of , which is proved using Harmonic Analysis, that asserts that at least one such contribution is always large. The symmetry implies that all contributions are the same and the result follows. See also  for some related results. These results hold for every transitive group of symmetries. In  it is shown that one can, in fact, prove that the threshold for graph properties is even sharper, by taking into account the precise group of symmetries induced on the edges of the complete graph by permuting the vertices. It turns out that for every monotone graph property and for every fixed $`ϵ>0`$, the width of the interval in which the probability the property holds increases from $`ϵ`$ to $`1ϵ`$ is at most $`c_\delta /(\mathrm{log}n)^{2\delta }`$ for all $`\delta >0`$. The power $`2`$ here is tight, as shown by the property of containing a clique of size, say, $`2\mathrm{log}_2n`$.

It is natural to call the threshold for a monotone graph property sharp if for every fixed positive $`ϵ`$, the width $`w`$ of the interval in which the probability that the property holds increases from $`ϵ`$ to $`1ϵ`$ satisfies $`w=o(p)`$, where $`p`$ is any point inside this interval. In  Friedgut obtained a beautiful characterization of all monotone graph properties for which the threshold is sharp. Roughly speaking, a property does not have a sharp threshold if and only if it can be approximated well in the relevant range of the probability $`p`$ by a property that is determined by constant size witnesses. Thus, for example, the property of containing $`5`$ vertex disjoint triangles does not have a sharp threshold, whereas the property of having chromatic number bigger than $`10`$ does. A similar result holds for hypergraphs as well. The proofs combine probabilistic and combinatorial arguments with techniques from Harmonic analysis.

### 4.2. Ramsey numbers

Let $`H_1,H_2,\mathrm{},H_k`$ be a sequence of $`k`$ finite, undirected, simple graphs. The (multicolored) Ramsey number $`r(H_1,H_2,\mathrm{},H_k)`$ is the minimum integer $`r`$ such that in every edge coloring of the complete graph on $`r`$ vertices by $`k`$ colors, there is a monochromatic copy of $`H_i`$ in color $`i`$ for some $`1ik`$. By a (special case of) a well known theorem of Ramsey (c.f., e.g., ), this number is finite for every sequence of graphs $`H_i`$.

The determination or estimation of these numbers is usually a very difficult problem. When all graphs $`H_i`$ are complete graphs with more than two vertices, the only values that are known precisely are those of $`r(K_3,K_m)`$ for $`m9`$, $`r(K_4,K_4)`$, $`r(K_4,K_5)`$ and $`r(K_3,K_3,K_3).`$ Even the determination of the asymptotic behaviour of Ramsey numbers up to a constant factor is a hard problem, and despite a lot of efforts by various researchers (see, e.g., ,  and their references), there are only a few infinite families of graphs for which this behaviour is known.

In one of the first applications of the probabilistic method in Combinatorics, Erdős  proved that if $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{1\left(\genfrac{}{}{0pt}{}{k}{2}\right)}<1`$ then $`R(k,k)>n`$, that is, there exists a $`2`$-coloring of the edges of the complete graph on $`n`$ vertices containing no monochromatic clique of size $`k`$. The proof is extremely simple; the probability that a random two-edge coloring of $`K_n`$ contains a monochromatic $`K_k`$ is at most $`\left(\genfrac{}{}{0pt}{}{n}{k}\right)2^{1\left(\genfrac{}{}{0pt}{}{k}{2}\right)}<1`$ , and hence there is a coloring with the required property.

A particularly interesting example of an infinite family for which the asymtotic behaviour of the Ramsey number is known, is the following result of Kim  together with that of Ajtai, Komlós and Szemerédi .

###### Theorem 4.1

(, ) There are two absolute positive constants $`c_1,c_2`$ such that

$$c_1m^2/\mathrm{log}mr(K_3,K_m)c_2m^2/\mathrm{log}m$$

for all $`m>1`$.

The upper bound, proved in , is probabilistic, and applies a certain random greedy algorithm. The lower bound is proved by a “semi-random” construction and proceeds in stages. The detailed analysis is subtle, and is based on certain large deviation inequalities.

Even less is known about the asymptotic behaviour of multicolored Ramsey numbers, that is, Ramsey numbers with at least $`3`$ colors. The asymptotic behaviour of $`r(K_3,K_3,K_m)`$, for example, has been very poorly understood until recently, and Erdős and Sós conjectured in 1979 (c.f., e.g., ) that

$$\underset{m\mathrm{}}{lim}\frac{r(K_3,K_3,K_m)}{r(K_3,K_m)}=\mathrm{}.$$

This has been proved recently, in a strong sense, in , where it is shown that in fact $`r(K_3,K_3,K_m)`$ is equal, up to logarithmic factors, to $`m^3`$. A more complicated, related result proved in , that supplies the asymptotic behaviour of infinitely many families of Ramsey numbers up to a constant factor is the following.

###### Theorem 4.2

For every $`t>1`$ and $`s(t1)!+1`$ there are two positive constants $`c_1,c_2`$ such that for every $`m>1`$

$$c_1\frac{m^t}{\mathrm{log}^tm}r(K_{t,s},K_{t,s},K_{t,s},K_m)c_2\frac{m^t}{\mathrm{log}^tm},$$

where $`K_{t,s}`$ is the complete bipartite graph with $`t`$ vertices in one color class and $`s`$ vertices in the other.

The proof combines spectral techniques, character sum estimates, and probabilistic arguments.

### 4.3. Turán type results

For a graph $`H`$ and an integer $`n`$, the Turán number $`ex(n,H)`$ is the maximum possible number of edges in a simple graph on $`n`$ vertices that contains no copy of $`H`$. The asymptotic behavior of these numbers for graphs of chromatic number at least $`3`$ is well known, see, e.g., . For bipartite graphs $`H`$, however, much less is known, and there are relatively few nontrivial bipartite graphs $`H`$ for which the order of magnitude of $`ex(n,H)`$ is known.

A result of Füredi  implies that for every fixed bipartite graph $`H`$ in which the degrees of all vertices in one color class are at most $`r`$, there is some $`c=c(H)>0`$ such that $`ex(n,H)cn^{21/r}.`$ As observed in , this result can be derived from a simple and yet surprisingly powerful probabilistic lemma, variants of which have been proved and applied by various researchers starting with Rödl and including Kostochka, Gowers and Sudakov (see , , ). The lemma asserts, roughly, that every graph with sufficiently many edges contains a large subset $`A`$ in which every $`a`$ vertices have many common neighbors. The proof uses a process that may be called a dependent random choice for finding the set $`A`$; $`A`$ is simply the set of all common neighbors of an appropriately chosen random set $`R`$. Intuitively, it is clear that if some $`a`$ vertices have only a few common neighbors, it is unlikely all the members of $`R`$ will be chosen among these neighbors. Hence, we do not expect $`A`$ to contain any such subset of $`a`$ vertices. This simple idea can be extended. In particular, it can be used to bound the Turán numbers of degenerate bipartite graphs.

A graph is $`r`$-degenerate if every subgraph of it contains a vertex of degree at most $`r`$. An old conjecture of Erdős asserts that for every fixed $`r`$-degenerate bipartite graph $`H`$, $`ex(n,H)O(n^{21/r}),`$ and the above technique suffices to show that there is an absolute constant $`c>0`$, such that for every such $`H`$, $`ex(n,H)n^{2c/r}`$.

Further questions and results about Turán numbers can be found in ,  and their references.

## 5 . Algorithms and explicit constructions

The rapid development of Theoretical Computer Science and its tight connection to Discrete Mathematics motivated the study of the algorithmic aspects of algebraic and probabilistic techniques. Can a combinatorial structure, or a substructure of a given one, whose existence is proved by algebraic or probabilistic means, be constructed explicitly (that is, by an efficient deterministic algorithm)? Can the algorithmic problems corresponding to existence proofs be solved by efficient procedures? The study of these questions often requires tools from other branches of mathematics.

As described in subsection 3.3, if $`G`$ is a graph on $`3n`$ vertices, whose set of edges is the disjoint union of a Hamilton cycle and $`n`$ pairwise vertex-disjoint triangles, then the chromatic number of $`G`$ is $`3`$. Can we solve the corresponding algorithmic problem efficiently ? That is, is there a polynomial time, deterministic or randomized algorithm, that given an input graph as above, colors it properly with $`3`$ colors? Similarly, as mentioned in subsection 3.3, the list chromatic index of any planar cubic $`2`$-connected graph is $`3`$. Can we color properly the edges of any given planar cubic $`2`$-connected graph using given lists of three colors per edge, in polynomial time?

These problems, as well as the algorithmic versions of additional applications of Theorem 3.1, are open. Of course, an algorithmic version of the theorem itself would provide efficient procedures for solving all these questions. The input for such an algorithm is a polynomial in $`n`$ variables over a field described, say, by a polynomial size arithmetic circuit. Suppose that this polynomial satisfies the assumptions of Theorem 3.1, and that the fact it satisfies it can be checked efficiently. The algorithm should then find, efficiently, a point $`(s_1,s_2,\mathrm{},s_n)`$ satisfying the conclusion of Theorem 3.1.

Unfortunately, it seems unlikely that such a general result can exist, as it would imply that there are no one-way permutations. Indeed, let $`F:\{0,1\}^n\{0,1\}^n`$ be a $`11`$ function, and suppose that for any $`x=(x_1,\mathrm{},x_n)\{0,1\}^n`$, the value of $`F(x)`$ can be computed efficiently. Every Boolean function can be expressed as a multilinear polynomial over $`GF(2)`$, and hence, when we wish to find an $`x`$ such that $`F(x)=y=(y_1,\mathrm{},y_n)`$, we can write it as a system of multilinear polynomials over $`GF(2)`$: $`F_i(x)=y_i`$ for all $`1in`$. Equivalently, this can be written as $`_{i=1}^n(F_i(x)+y_i+1)0`$. This last equation has a unique solution, implying that its left hand side, written as a multilinear polynomial, is of full degree $`n`$ (since otherwise it is easy to check that it attains the value $`1`$ an even number of times). It follows that the assumptions of Theorem 3.1 with $`f=_{i=1}^n(F_i(x)+y_i+1)`$, $`t_i=1`$ and $`S_i=GF(2)`$ hold. Thus, the existence of an efficient algorithm as above would enable us to invert $`F`$ efficiently, implying that there cannot be any one-way permutations. As this seems unlikely, it may be more productive (and yet challenging) to try and develop efficient procedures for solving the particular algorithmic problems corresponding to the results obtained by the theorem.

Probabilistic proofs also suggest the study of the corresponding algorithmic problems. This is related to the study of randomized algorithms, a topic which has been developed tremendously during the last decade. See, e.g.,  and its many references. In particular, it is interesting to find explicit constructions of combinatorial structures whose existence is proved by probabilistic arguments. ”Explicit” here means that there is a an efficient algorithm that constructs the desired structure in time polynomial in its size. Constructions of this type, besides being interesting in their own, have applications in other areas. Thus, for example, explicit constructions of error correcting codes that are as good as the random ones are of interest in information theory, and explicit constructions of certain Ramsey type colorings may have applications in derandomization — the process of converting randomized algorithms into deterministic ones.

It turns out, however, that the problem of finding a good explicit construction is often very difficult. Even the simple proof of Erdős, described in subsection 4.2, that there are two-edge colorings of the complete graph on $`2^{m/2}`$ vertices containing no monochromatic clique of size $`m`$, leads to an open problem which seems very difficult. Can we construct, explicitly, such a coloring of a complete graph on $`n(1+ϵ)^m`$ vertices, in time which is polynomial in $`n`$, where $`ϵ>0`$ is any positive absolute constant ?

This problem is still open, despite a lot of efforts. The best known explicit construction is due to Frankl and Wilson , who gave an explicit two-edge coloring of the complete graph on $`m^{(1+o(1))\frac{\mathrm{log}m}{4\mathrm{log}\mathrm{log}m}}`$ vertices with no monochromatic clique on $`m`$ vertices.

The construction of explicit two-edge colorings of large complete graphs $`K_n`$ with no red $`K_s`$ and no blue $`K_m`$ for fixed $`s`$ and large $`m`$ also appears to be very difficult. Using probabilistic arguments it can be shown that there are such colorings for $`n`$ which is $`c\left(\frac{m}{\mathrm{log}m}\right)^{(s+1)/2}`$ for some absolute constant $`c>0`$. The best known explicit construction, however, given in , works only for $`m^{\delta \sqrt{\mathrm{log}s/\mathrm{log}\mathrm{log}s}}`$, for some absolute constant $`\delta >0`$. The description of the construction is not complicated but the proof of its properties relies on tools from various mathematical areas. These include some ideas from algebraic geometry obtained in , the well known bound of Weil on character sums, spectral techniques and their connection to the pseudo-random properties of graphs, the known bounds of  for the problem of Zarankiewicz and the well known Erdős-Rado bound for the existence of $`\mathrm{\Delta }`$-systems.

The above example is typical, and illustrates the fact that tools from various mathematical disciplines often appear in the design of explicit constructions of combinatorial structures. Other examples that demonstrate this fact are the construction of Algebraic Geometry codes, and the construction of sparse pseudo-random graphs called expanders.

## 6 . Some future challenges

Several specific open problems in Discrete Mathematics are mentioned throughout this article. These, and many additional ones, provide interesting challenges for future research in the area. We conclude with some brief comments on two more general future challenges.

It seems safe to predict that in the future there will be additional incorporation of methods from other mathematical areas in Combinatorics. However, such methods often provide non-constructive proof techniques, and the conversion of these to algorithmic ones may well be one of the main future challenges of the area. Another interesting recent development is the increased appearance of Computer aided proofs in Combinatorics, starting with the proof of the Four Color Theorem, and including automatic methods for the discovery and proof of hypergeometric identities — see . A successful incorporation of such proofs in the area, without losing its special beauty and appeal, is another challenge. These challenges, the fundamental nature of the area, its tight connection to other disciplines, and the many fascinating specific open problems studied in it, ensure that Discrete Mathematics will keep playing an essential role in the general development of science in the future as well.


format: text

text:
# References

1. Introduction. The concept of partial breaking of global supersymmetry (PBGS)  provides a manifestly worldvolume supersymmetric description of various superbranes in terms of Goldstone superfields .

Most of the PBGS theories known to date correspond to superbranes on flat super Minkowski backgrounds (see  and refs. therein). On the other hand, keeping in mind the renowned AdS/CFT correspondence , it is the AdS$`{}_{n}{}^{}\times S^m`$ and PP-wave type  superbackgrounds which are of primary interest. However, not too many explicit examples of the worldvolume superfield PBGS actions on such backgrounds were constructed so far. Such actions were given only for $`N=1`$ supermembrane in AdS4  and some its dimensional reductions .

It is tempting to construct PBGS versions of superstring and D3-brane on the AdS$`{}_{5}{}^{}\times S^5`$ background which is in the heart of the original AdS/CFT conjecture. These systems should be associated with the partial breaking of $`N=4,d=4`$ superconformal group $`SU(2,2|4)`$ which determines the corresponding superisometries. 111The space-time Green-Schwarz-type actions for these systems were constructed in . It is natural to firstly study some truncations of these models based on simpler $`N=1`$ and $`N=2`$, $`d=4`$ superconformal groups $`SU(2,2|1)`$ and $`SU(2,2|2)`$. An attempt to construct a PBGS model for $`SU(2,2|1)`$ which would generalize that of  was undertaken in . This model involves Goldstone $`N=1`$ chiral superfield as the basic one and is expected to describe a scalar 3-brane on AdS$`{}_{5}{}^{}\times S^1`$. However, no proper Goldstone superfield action in the explicit form was given.

The aim of this letter is to present AdS5 generalizations of the two versions of the off-shell minimal Goldstone superfield actions of partially broken $`N=2,d=4`$ Poincaré supersymmetry: the one with the $`N=1`$ Goldstone tensor multiplet  and the one with the chiral Goldstone $`N=1`$ supermultiplet . Instead of dealing with a nonlinear realization of $`SU(2,2|1)`$ in the standard approach  like this has been done in , we prefer to follow the line of refs. . As a first step, we construct a nonlinear realization of $`SU(2,2|1)`$ on the set of three $`N=1`$ superfields: an improved $`N=1`$ tensor superfield $`L`$ and mutually conjugated chiral superfields $`F,\overline{F}`$. This set is subjected to some nonlinear covariant constraints which leave us with the single superfield $`L`$ as the only Goldstone one. Its $`SU(2,2|1)`$ invariant action describes $`N=1`$ L3-brane on AdS5.222See e.g.  for the relevant nomenclature. The bosonic core of this action is a static-gauge Nambu-Goto action of L3-brane in AdS5, with one scalar physical field of $`L`$ being a transverse brane coordinate and another (on-shell) bosonic degree of freedom being carried out by the notoph field strength. Then we dualize $`L`$ into a pair of mutually conjugated chiral $`N=1`$ superfields and obtain an analog of the action of ref. . It describes a scalar super 3-brane on AdS$`{}_{5}{}^{}\times S^1`$. This action corresponds to the PBGS option studied in  and in the bosonic sector precisely yields the $`S^5S^1`$ reduction of the scalar part of D3-brane action on AdS$`{}_{5}{}^{}\times S^5`$ .

2. Goldstone tensor $`N=1`$ multiplet in a flat background. The idea to utilize $`N=1`$ tensor multiplet as the Goldstone one for describing the partial breaking of the global $`N=2,d=4`$ Poincaré supersymmetry down to $`N=1`$ has been worked out in .

One starts with $`N=2,d=4`$ Poincaré superalgebra extended by a real central charge $`D`$

$$\{Q_\alpha ,\overline{Q}_{\dot{\alpha }}\}=2P_{\alpha \dot{\alpha }},\{S_\alpha ,\overline{S}_{\dot{\alpha }}\}=2P_{\alpha \dot{\alpha }},\{Q_\alpha ,S_\beta \}=\epsilon _{\alpha \beta }D,\{\overline{Q}_{\dot{\alpha }},\overline{S}_{\dot{\beta }}\}=\epsilon _{\dot{\alpha }\dot{\beta }}D.$$
(1)
Here $`Q_\alpha ,\overline{Q}_{\dot{\alpha }}`$ and $`S_\alpha ,\overline{S}_{\dot{\alpha }}`$ are generators of the unbroken and broken $`N=1`$ supersymmetries, respectively. These generators and the 4-translation generator $`P_{\alpha \dot{\alpha }}`$ possess the standard commutation relations with the Lorentz $`so(1,3)`$ generators $`(M_{\alpha \beta },\overline{M}_{\dot{\alpha }\dot{\beta }})`$:

$`i[M_{\alpha \beta },M_{\rho \sigma }]=\epsilon _{\alpha \rho }M_{\beta \sigma }+\epsilon _{\alpha \sigma }M_{\beta \rho }+\epsilon _{\beta \rho }M_{\alpha \sigma }+\epsilon _{\beta \sigma }M_{\alpha \rho }\left(M\right)_{\alpha \beta ,\rho \sigma },`$
$`i[\overline{M}_{\dot{\alpha }\dot{\beta }},\overline{M}_{\dot{\rho }\dot{\sigma }}]=\left(\overline{M}\right)_{\dot{\alpha }\dot{\beta },\dot{\rho }\dot{\sigma }},i[M_{\alpha \beta },P_{\rho \dot{\rho }}]=\epsilon _{\alpha \rho }P_{\beta \dot{\rho }}+\epsilon _{\beta \rho }P_{\alpha \dot{\rho }},`$
$`i[\overline{M}_{\dot{\alpha }\dot{\beta }},P_{\rho \dot{\rho }}]=\epsilon _{\dot{\alpha }\dot{\rho }}P_{\rho \dot{\beta }}+\epsilon _{\dot{\beta }\dot{\rho }}P_{\rho \dot{\alpha }},i[M_{\alpha \beta },Q_\gamma ]=\epsilon _{\alpha \gamma }Q_\beta +\epsilon _{\beta \gamma }Q_\alpha \left(Q\right)_{\alpha \beta ,\gamma },`$
$`i[M_{\alpha \beta },S_\gamma ]=\left(S\right)_{\alpha \beta ,\gamma },i[\overline{M}_{\dot{\alpha }\dot{\beta }},\overline{Q}_{\dot{\gamma }}]=\left(\overline{Q}\right)_{\dot{\alpha }\dot{\beta },\dot{\gamma }},i[\overline{M}_{\dot{\alpha }\dot{\beta }},\overline{S}_{\dot{\gamma }}]=\left(\overline{S}\right)_{\dot{\alpha }\dot{\beta },\dot{\gamma }}.`$ (2)
Then one introduces two $`N=1`$ superfields: a real one $`L(x,\theta )`$ subjected to the constraint

$$D^2L=\overline{D}^2L=0,$$
(3)
and so describing a linear (or tensor) $`N=1`$ supermultiplet, and a complex chiral $`N=1`$ superfield $`F,\overline{F}`$,

$$D_\alpha F=\overline{D}_{\dot{\alpha }}\overline{F}=0.$$
(4)
Here

$$D_\alpha =\frac{}{\theta ^\alpha }+i\overline{\theta }^{\dot{\alpha }}_{\alpha \dot{\alpha }},\overline{D}_{\dot{\alpha }}=\frac{}{\overline{\theta }^{\dot{\alpha }}}i\theta ^\alpha _{\alpha \dot{\alpha }},D^2=D^\alpha D_\alpha ,\overline{D}^2=\overline{D}_{\dot{\alpha }}\overline{D}^{\dot{\alpha }}.$$
(5)
On these $`N=1`$ superfields one implements  the following off-shell representation of the full $`N=2`$ supersymmetry (1):

$$\delta L=i\left(\eta ^\alpha \theta _\alpha \overline{\eta }_{\dot{\alpha }}\overline{\theta }^{\dot{\alpha }}\right)+\eta ^\alpha D_\alpha \overline{F}\overline{\eta }^{\dot{\alpha }}\overline{D}_{\dot{\alpha }}F,\delta F=\eta ^\alpha D_\alpha L,\delta \overline{F}=\overline{\eta }^{\dot{\alpha }}\overline{D}_{\dot{\alpha }}L,$$
(6)
where $`\eta _\alpha ,\overline{\eta }_{\dot{\alpha }}`$ are the infinitesimal transformation parameters associated with the generators $`S_\alpha `$, $`\overline{S}_{\dot{\alpha }}`$. It is a modification of the transformation law of $`N=2`$ tensor multiplet  written in terms of its $`N=1`$ superfield components. This modification is such that we are in fact facing the Goldstone $`N=2`$ tensor multiplet: the spinor derivatives $`D_\alpha L|,\overline{D}_{\dot{\alpha }}L|`$ are shifted by $`\eta _\alpha ,\overline{\eta }_{\dot{\alpha }}`$ and so are Goldstone fermions for the partial spontaneous breaking $`N=2N=1`$, while $`L|`$ is shifted by a constant under the action of the generator $`D`$ and so is the relevant Goldstone field ($`|`$ means restriction to the $`\theta ,\overline{\theta }`$ independent parts).

One can construct the simplest invariant ‘action’ as follows

$$S=\frac{1}{4}d^4xd^2\overline{\theta }F+\frac{1}{4}d^4xd^2\theta \overline{F}.$$
(7)
To make it meaningful one should express the chiral supermultiplet $`F,\overline{F}`$ in terms of the Goldstone tensor multiplet $`L`$ by imposing proper covariant constraints. These additional constraints were simply guessed in  and later re-derived in  from the nilpotency conditions imposed on the appropriate superfields. They read

$$F=\frac{D^\alpha LD_\alpha L}{2D^2\overline{F}}\overline{F}=\frac{\overline{D}_{\dot{\alpha }}L\overline{D}^{\dot{\alpha }}L}{2\overline{D}^2F}$$
(8)
and can be easily solved

$$F=\psi ^2+\frac{1}{2}D^2\left[\frac{\psi ^2\overline{\psi }^2}{1+\frac{1}{2}A+\sqrt{1+A+\frac{1}{4}B^2}}\right],$$
(9)
where

$$\psi _\alpha D_\alpha L,\overline{\psi }_{\dot{\alpha }}\overline{D}_{\dot{\alpha }}L,A=\frac{1}{2}\left(D^2\overline{\psi }^2+\overline{D}^2\psi ^2\right),B=\frac{1}{2}\left(D^2\overline{\psi }^2\overline{D}^2\psi ^2\right).$$
(10)
Finally, the action (7) becomes

$$S=\frac{1}{4}d^4xd^2\theta \overline{\psi }^2\frac{1}{4}d^4xd^2\overline{\theta }\psi ^2+\frac{1}{4}d^4xd^4\theta \frac{\psi ^2\overline{\psi }^2}{1+\frac{1}{2}A+\sqrt{1+A+\frac{1}{4}B^2}}.$$
(11)
It is a nonlinear extension of the standard $`N=1`$ tensor multiplet action. In the bosonic sector it gives rise to the static-gauge Nambu-Goto action for L3-brane in $`d=5`$ Minkowski space, with one physical scalar of $`L`$ being the transverse brane coordinate and another one represented by the notoph field strength. After dualizing $`L`$ into a pair of conjugated chiral and antichiral $`N=1`$ superfields (the notoph strength is dualized into a scalar field) the PBGS form of the worldvolume action of super 3-brane in $`d=6`$ is reproduced .

We would like to point out that the constraints (8) which play the central role in deriving the action (11) are intimately related to the 5-dimensional nature of the brane under consideration. They guarantee 5-dimensional Lorentz covariance.

Indeed, the generator $`D`$ in (1) can be treated as the generator of translations in 5th dimension and the full automorphism algebra of (1) can be checked to be $`so(1,4)`$ (we ignore the $`R`$-symmetry $`SU(2)`$ automorphisms which are explicitly broken in (11)). The 5D Lorentz algebra $`so(1,4)`$ includes, besides 4D Lorentz generators $`M_{\alpha \beta },\overline{M}_{\dot{\alpha }\dot{\beta }}`$, an additional 4D vector $`K_{\alpha \dot{\alpha }}`$ belonging to the coset $`SO(1,4)/SO(1,3)`$. The full set of additional commutation relations is as follows:

$`i[M_{\alpha \beta },K_{\rho \dot{\rho }}]=\epsilon _{\alpha \rho }K_{\beta \dot{\rho }}+\epsilon _{\beta \rho }K_{\alpha \dot{\rho }},i[K_{\alpha \dot{\alpha }},K_{\beta \dot{\beta }}]=\epsilon _{\alpha \beta }\overline{M}_{\dot{\alpha }\dot{\beta }}\epsilon _{\dot{\alpha }\dot{\beta }}M_{\alpha \beta },`$
$`i[D,K_{\alpha \dot{\alpha }}]=2P_{\alpha \dot{\alpha }},i[P_{\alpha \dot{\alpha }},K_{\beta \dot{\beta }}]=\epsilon _{\alpha \beta }\epsilon _{\dot{\alpha }\dot{\beta }}D,`$
$`i[K_{\alpha \dot{\alpha }},Q_\beta ]=\epsilon _{\alpha \beta }\overline{S}_{\dot{\alpha }},i[K_{\alpha \dot{\alpha }},\overline{S}_{\dot{\beta }}]=\epsilon _{\dot{\alpha }\dot{\beta }}Q_\alpha .`$ (12)
Now one can check that the following nonlinear transformations

$`\delta ^{}L=a_{\alpha \dot{\alpha }}x^{\alpha \dot{\alpha }}a^{\alpha \dot{\alpha }}_{\alpha \dot{\alpha }}\left(L^22F\overline{F}\right)+ia^{\alpha \dot{\alpha }}\theta _\alpha \overline{D}_{\dot{\alpha }}Fia^{\alpha \dot{\alpha }}\overline{\theta }_{\dot{\alpha }}D_\alpha \overline{F},`$
$`\delta ^{}F=2a^{\alpha \dot{\alpha }}_{\alpha \dot{\alpha }}\left(FL\right)+ia^{\alpha \dot{\alpha }}\overline{\theta }_{\dot{\alpha }}D_\alpha L,\delta ^{}\overline{F}=2a^{\alpha \dot{\alpha }}_{\alpha \dot{\alpha }}\left(\overline{F}L\right)ia^{\alpha \dot{\alpha }}\theta _\alpha \overline{D}_{\dot{\alpha }}L`$ (13)
are just the $`SO(1,4)/SO(1,3)`$ ones, with $`a^{\alpha \dot{\alpha }}`$ being a transformation parameter related to the additional generator $`K_{\alpha \dot{\alpha }}`$. They have a correct closure on $`SO(1,3)`$ and are compatible with the defining constraints (3), (4) only provided the nonlinear constraints (8) are imposed. The action (11) is invariant under these transformations.

3. AdS5 background. Now we wish to generalize the flat superspace construction described in the previous Section to the case of partial spontaneous breaking of the simplest AdS5 supersymmetry which is $`SU(2,2|1)`$, that is $`N=1`$ superconformal group in $`d=4`$.

The superalgebra $`su(2,2|1)`$ contains $`so(2,4)\times u(1)`$ bosonic subalgebra with the generators $`\{P_{\alpha \dot{\alpha }},M_{\alpha \beta },\overline{M}_{\dot{\alpha }\dot{\beta }},K_{\alpha \dot{\alpha }},D\}`$ and $`\left\{J\right\}`$ and eight supercharges $`\{Q_\alpha ,\overline{Q}_{\dot{\alpha }},S_\alpha ,\overline{S}_{\dot{\alpha }}\}`$. We choose the basis in a such way, that the generators $`K_{\alpha \dot{\alpha }}`$ form $`so(1,4)`$ subalgebra together with the $`d=4`$ Lorentz generators $`\{M_{\alpha \beta },\overline{M}_{\dot{\alpha }\dot{\beta }}\}`$, as in the first line of (S0.Ex4). The rest of non-trivial (anti)commutators reads

$`i[D,P_{\alpha \dot{\alpha }}]=mP_{\alpha \dot{\alpha }},i[D,K_{\alpha \dot{\alpha }}]=2P_{\alpha \dot{\alpha }}mK_{\alpha \dot{\alpha }},`$
$`i[P_{\alpha \dot{\alpha }},K_{\beta \dot{\beta }}]=\epsilon _{\alpha \beta }\epsilon _{\dot{\alpha }\dot{\beta }}D{\displaystyle \frac{m}{2}}\left(\epsilon _{\alpha \beta }\overline{M}_{\dot{\alpha }\dot{\beta }}+\epsilon _{\dot{\alpha }\dot{\beta }}M_{\alpha \beta }\right),`$
$`\{Q_\alpha ,S_\beta \}=\epsilon _{\alpha \beta }\left(D+imJ\right)+mM_{\alpha \beta },\{Q_\alpha ,\overline{Q}_{\dot{\alpha }}\}=2P_{\alpha \dot{\alpha }},\{S_\alpha ,\overline{S}_{\dot{\alpha }}\}=2P_{\alpha \dot{\alpha }}2mK_{\alpha \dot{\alpha }},`$
$`i[D,Q_\alpha ]={\displaystyle \frac{m}{2}}Q_\alpha ,i[D,S_\alpha ]={\displaystyle \frac{m}{2}}S_\alpha ,[J,Q_\alpha ]={\displaystyle \frac{3}{2}}Q_\alpha ,[J,S_\alpha ]={\displaystyle \frac{3}{2}}S_\alpha ,`$
$`i[K_{\alpha \dot{\alpha }},Q_\beta ]=\epsilon _{\alpha \beta }\overline{S}_{\dot{\alpha }},i[K_{\alpha \dot{\alpha }},S_\beta ]=\epsilon _{\alpha \beta }\overline{Q}_{\dot{\alpha }},i[P_{\alpha \dot{\alpha }},S_\beta ]=m\epsilon _{\alpha \beta }\overline{Q}_{\dot{\alpha }}.`$ (14)
This basis is an example of the ‘AdS basis’ of conformal superalgebras  which perfectly suits their interpretation as the superisometry groups of the appropriate AdS superspaces. Indeed, the generators $`P_{\alpha \dot{\alpha }},D,J`$ form a maximal solvable bosonic subgroup in $`su(2,2|1)`$ and span the coset $`SO(2,4)/SO(1,4)\times U(1)`$ AdS$`{}_{5}{}^{}\times S^1`$. The parameter $`m`$ has the meaning of the inverse AdS5 radius, $`m=R^1`$. In the limit $`m=0`$ ($`R=\mathrm{}`$) one recovers from (S0.Ex7) the $`N=1,d=5`$ Poincaré superalgebra, with $`D`$ becoming the 5th component of momenta. The generators $`J`$ and $`K_{\alpha \dot{\alpha }},M_{\alpha \beta },\overline{M}_{\dot{\alpha }\dot{\beta }}`$ decouple and generate outer $`u(1)so(1,4)`$ automorphisms.

Our goal is to construct an AdS5 version of the nonlinear realization (6), (8). The main hints which allowed us to do this are as follows. Firstly, we assert that this realization involves some modification of $`N=1`$ tensor multiplet $`L`$ and, as before, a pair of mutually conjugated $`N=1`$ chiral and anti-chiral superfields $`F,\overline{F}`$ subjected to some generalization of (8). Second, in a close analogy with the flat case we require that the following ‘action’

$$Sd^4xd^2\overline{\theta }F+d^4xd^2\theta \overline{F}$$
(15)
is an invariant of the AdS5 supersymmetry. Since the right-chiral integration measure $`d^4xd^2\overline{\theta }`$ has the $`D`$ weight $`3m`$ and, with our normalization of $`J`$, the $`U(1)`$ charge $`3`$, the superfield $`F`$ should carry the $`D`$ and $`J`$ weights equal to $`3m`$ and $`3`$ ($`\overline{F}`$ has the same $`D`$ weight and the $`J`$ charge equal to $`3`$). Third, in the limit $`m=0`$ our construction should reproduce the flat case outlined in Sec. 2. At last, it is sufficient to find the realization of conformal $`S`$ supersymmetry, since the rest of $`SU(2,2|1)`$ transformations appears in the closure of these $`S`$ transformations with themselves and with those of $`N=1`$ Poincaré supersymmetry.

It turns out that this reasoning almost uniquely fixes the sought transformation laws and constraints (more details of the derivation are given in ). These are

$`\delta ^{}\overline{F}`$ $`=`$ $`6im\theta ^\alpha \eta _\alpha \overline{F}\mathrm{\Delta }x^{\alpha \dot{\alpha }}_{\alpha \dot{\alpha }}\overline{F}+\mathrm{\Delta }\theta ^\alpha D_\alpha \overline{F}+ie^{2mL}\overline{\eta }^{\dot{\alpha }}\overline{D}_{\dot{\alpha }}L,`$
$`\delta ^{}F`$ $`=`$ $`6im\overline{\theta }_{\dot{\alpha }}\overline{\eta }^{\dot{\alpha }}F\mathrm{\Delta }x^{\alpha \dot{\alpha }}_{\alpha \dot{\alpha }}F\mathrm{\Delta }\overline{\theta }^{\dot{\alpha }}\overline{D}_{\dot{\alpha }}F+ie^{2mL}\eta ^\alpha D_\alpha L,`$
$`\delta ^{}L`$ $`=`$ $`i(\theta ^\alpha \eta _\alpha \overline{\theta }_{\dot{\alpha }}\overline{\eta }^{\dot{\alpha }})\mathrm{\Delta }x^{\alpha \dot{\alpha }}_{\alpha \dot{\alpha }}L+\mathrm{\Delta }\theta ^\alpha D_\alpha L\mathrm{\Delta }\overline{\theta }^{\dot{\alpha }}\overline{D}_{\dot{\alpha }}L`$ (16)
$`ie^{2mL}\left[\eta ^\alpha D_\alpha \left(e^{2mL}\overline{F}\right)+\overline{\eta }^{\dot{\alpha }}\overline{D}_{\dot{\alpha }}\left(e^{2mL}F\right)\right],`$
$`{\displaystyle \frac{1}{m}}D^2e^{2mL}`$ $`=`$ $`{\displaystyle \frac{1}{m}}\overline{D}^2e^{2mL}=0,D_\alpha F=\overline{D}_{\dot{\alpha }}\overline{F}=0,`$ (17)
$`F`$ $`=`$ $`{\displaystyle \frac{e^{2mL}D^\alpha LD_\alpha L}{2e^{4mL}D^2\overline{F}}},\overline{F}={\displaystyle \frac{e^{2mL}\overline{D}_{\dot{\alpha }}L\overline{D}^{\dot{\alpha }}L}{2e^{4mL}\overline{D}^2F}}.`$ (18)
Here

$`\mathrm{\Delta }x^{\alpha \dot{\alpha }}=2im\left(\eta _\beta x^{\beta \dot{\alpha }}\theta ^\alpha +\overline{\eta }_{\dot{\beta }}x^{\alpha \dot{\beta }}\overline{\theta }^{\dot{\alpha }}\right)m\left(\theta ^2\eta ^\alpha \overline{\theta }^{\dot{\alpha }}\overline{\theta }^2\overline{\eta }^{\dot{\alpha }}\theta ^\alpha \right),`$
$`\mathrm{\Delta }\theta ^\alpha =m\overline{\eta }_{\dot{\alpha }}x^{\alpha \dot{\alpha }}+im\left(\theta ^2\eta ^\alpha \overline{\theta }_{\dot{\alpha }}\overline{\eta }^{\dot{\alpha }}\theta ^\alpha \right),\mathrm{\Delta }\overline{\theta }^{\dot{\alpha }}=m\eta _\alpha x^{\alpha \dot{\alpha }}im\left(\overline{\theta }^2\overline{\eta }^{\dot{\alpha }}\theta ^\alpha \eta _\alpha \overline{\theta }^{\dot{\alpha }}\right)`$ (19)
are the standard transformations of the $`N=1`$ superspace coordinates with respect to the conformal supersymmetry.

In the limit $`m=0`$ eqs. (16), (17) and (18) go, respectively, into (6), (3), (4) and (8). We have checked that, on the surface of the nonlinear constraints (18), the off-shell transformations (16) are, first, compatible with the differential constraints (17) and, second, produce the whole $`SU(2,2|1)`$ symmetry when commuted among themselves and with $`N=1`$ Poincaré supersymmetry. Had we neglected the last nonlinear terms in (16), we would recover the standard linear $`N=1`$ superconformal transformation laws of the improved tensor superfield $`e^{2mL}`$ and chiral superfields $`F,\overline{F}`$ which close without any need in the nonlinear constraints (18). It is just due to the presence of these extra mixed terms the transformations (16) constitute a realization of $`SU(2,2|1)`$ as the superisometry group of super AdS5 background and correctly generalize the flat superspace realization (6). A striking difference between (6) and (16) lies, however, in the fact that (6) close on $`N=2`$ Poincaré superalgebra before imposing the constraints (8), while (16) define a closed supergroup structure only provided the corresponding constraints (18) are imposed from the very beginning. In this sense the situation is similar to the implementation of the $`SO(1,4)`$ transformations (S0.Ex6) in the flat case, which are closed (together with the $`SO(1,3)`$ ones) only on the surface of (8). Since in the case of the supergroup $`SU(2,2|1)`$ these $`SO(1,4)`$ transformations appear in the anticommutators of the $`Q`$ and $`S`$ supersymmetry generators, it is quite natural that the constraints (18) should enter the game already at the stage of defining $`S`$ supersymmetry transformations. It is straightforward to check that (18) by themselves are covariant under the transformations (16).

Inspecting (16), one can be convinced that this realization just corresponds to a half-breaking of the $`SU(2,2|1)`$ supersymmetry: the spinor derivatives of $`L`$ are shifted by spinor parameters under the action of $`S`$ supersymmetry, thus signaling that the latter is spontaneously broken. Broken are also $`D`$ transformations (with $`L|`$ as the Goldstone field) and the $`SO(1,4)/SO(1,3)`$ transformations generated by $`K_{\alpha \dot{\alpha }}`$ (with $`_{\alpha \dot{\alpha }}L|`$ as the relevant ‘Goldstone field’).

Like their flat counterparts, the constraint (18) can be easily solved

$$F=e^{2mL}\psi ^2+\frac{1}{2}D^2\left[\frac{\psi ^2\overline{\psi }^2}{1+\frac{1}{2}A+\sqrt{1+A+\frac{1}{4}B^2}}\right],$$
(20)
where

$$\psi _\alpha D_\alpha L,\overline{\psi }_{\dot{\alpha }}\overline{D}_{\dot{\alpha }}L,A=\frac{1}{2}e^{2mL}\left(D^2\overline{\psi }^2+\overline{D}^2\psi ^2\right),B=\frac{1}{2}e^{2mL}\left(D^2\overline{\psi }^2\overline{D}^2\psi ^2\right).$$
(21)
Finally, the action (15) can be written in the form

$$S=\frac{1}{4}d^4xd^2\theta e^{2mL}\overline{\psi }^2\frac{1}{4}d^4xd^2\overline{\theta }e^{2mL}\psi ^2+\frac{1}{4}d^4xd^4\theta \frac{\psi ^2\overline{\psi }^2}{1+\frac{1}{2}A+\sqrt{1+A+\frac{1}{4}B^2}}.$$
(22)
The first two terms in (22) are recognized as the action of the improved tensor $`N=1`$ superfield . In the limit $`m=0`$ (22) converts into the flat superspace Goldstone superfield action (11).

Defining the bosonic components as

$$\varphi =L|_{\theta =0},[D_\alpha ,\overline{D}_{\dot{\alpha }}]e^{2mL}|_{\theta =0}=2mV_{\alpha \dot{\alpha }},$$
(23)
where in virtue of (18)

$$_{\alpha \dot{\alpha }}V^{\alpha \dot{\alpha }}=0,$$
(24)
the bosonic part of (22) proves to be

$$S_B=d^4xe^{4m\varphi }\left[1\sqrt{1+\frac{1}{2}e^{6m\varphi }V^22e^{2m\varphi }(\varphi )^2e^{8m\varphi }(V^{\alpha \dot{\alpha }}_{\alpha \dot{\alpha }}\varphi )^2}\right].$$
(25)
It is a conformally-invariant extension of the static gauge Nambu-Goto action for L3-brane in $`d=5`$: the dilaton $`\varphi `$ can be interpreted as a radial brane coordinate, while $`V^{\alpha \dot{\alpha }}`$ is the field strength of notoph which contributes one more scalar degree of freedom on shell. As is well known, $`V^{\alpha \dot{\alpha }}`$ can be dualized in an off-shell scalar by introducing the constraint (24) into the action with a Lagrange scalar multiplier and then eliminating $`V^{\alpha \dot{\alpha }}`$ by its algebraic equation of motion. Extending (25) as

$$S_BS_B^{dual}=S_B+d^4x\lambda _{\alpha \dot{\alpha }}V^{\alpha \dot{\alpha }}$$
(26)
and eliminating $`V^{\alpha \dot{\alpha }}`$, after some algebra we get

$$S_B^{dual}=d^4x|Z|^4\left[1\sqrt{\text{det}\left(\eta _{\mu \nu }\frac{2}{m^2}\frac{_\mu Z^n_\nu Z^n}{|Z|^4}\right)}\right],$$
(27)
where

$$Z^1=r\mathrm{cos}\vartheta ,Z^2=r\mathrm{sin}\vartheta ,re^{m\varphi },\vartheta m\lambda ,\eta _{\mu \nu }=\text{diag}(+).$$
(28)
The action (27) is recognized as the $`S^5S^1`$ reduction of the scalar part of the D3-brane action on AdS$`{}_{5}{}^{}\times S^5`$ , that is the static-gauge Nambu-Goto action of scalar 3-brane on AdS$`{}_{5}{}^{}\times S^1`$.

4. AdS$`{}_{5}{}^{}\times S^1`$ Goldstone superfield action. Here we repeat the above duality transformation at the full superfield level and obtain in this way an $`SU(2,2|1)`$ invariant action of Goldstone chiral $`N=1`$ superfield which generalizes the action of  and describes a super 3-brane on AdS$`{}_{5}{}^{}\times S^1`$ superbackground. We shall be sketchy about details which can be found in . In its basic steps this dualization procedure is similar to the flat superspace one of .

We start with the superfield action (22) and relax the constraints for $`L`$ in (17) by adding a Lagrange multiplier term to the superfield Lagrangian

$$S^{dual}=\frac{1}{4}d^4xd^2\theta d^2\overline{\theta }\left[\frac{1}{2m^2}Y\left(\mathrm{ln}Y1\right)+\frac{Y^4}{(2m)^4}(DY)^2(\overline{D}Y)^2f+\frac{Y}{2m}\left(\phi +\overline{\phi }\right)\right].$$
(29)
Here

$$Ye^{2mL},\overline{D}_{\dot{\alpha }}\phi =D_\alpha \overline{\phi }=0,f=\frac{1}{1+\frac{1}{2}A+\sqrt{1+A+\frac{1}{4}B^2}}.$$
(30)
Next we vary the action (29) with respect to $`Y`$ in order to obtain an algebraic equation that would allow us to trade $`Y`$ for $`\phi ,\overline{\phi }`$. Though the expression for $`Y`$ is rather complicated , the calculations are greatly simplified due to the property that only terms bilinear in fermions really contribute to the dualized action after substitution of this expression back into (29). Also, the terms $`\overline{D}^2Y,D^2Y`$ can be reabsorbed into a redefinition of chiral Lagrange multiplier like in the flat case . Skipping details, the dual action turns out to be as follows

$`S^{dual}`$ $`=`$ $`{\displaystyle \frac{1}{8}}{\displaystyle }d^4xd^4\theta ({\displaystyle \frac{e^{m(\phi +\overline{\phi })}}{m^2}}`$ (31)
$`+{\displaystyle \frac{\frac{1}{8}(D\phi )^2(\overline{D}\overline{\phi })^2}{1e^{m(\phi +\overline{\phi })}\phi \overline{\phi }+\sqrt{(1e^{m(\phi +\overline{\phi })}\phi \overline{\phi })^2e^{2m(\phi +\overline{\phi })}(\phi )^2(\overline{\phi })^2}}}).`$
This action goes into the flat $`N=2N=1`$ chiral Goldstone superfield action of  in the limit $`m=0`$ and is obviously $`SU(2,2|1)`$ invariant as it was obtained by dualizing the $`SU(2,2|1)`$ invariant action (22). We do not give the precise form of the $`SU(2,2|1)`$ transformations of the chiral superfields $`\phi ,\overline{\phi }`$ because they look not too illuminating. However, it is noteworthy that the standard $`U(1)`$ isometry associated with the duality transformation, viz. $`\delta \phi =i\alpha `$, $`\delta \overline{\phi }=i\alpha `$, now appears in the closure of the $`Q`$ and $`S`$ transformations on these Goldstone superfields, with the imaginary part of $`\phi |`$ being the related extra Goldstone field. It is just the $`J`$ (or $`\gamma _5`$) symmetry of $`SU(2,2|1)`$, i.e. the duality transformation brings this symmetry from the stability subgroup into the coset. A similar phenomenon was observed in  in the context of the duality between real and complex forms of $`N=2`$ superconformal mechanics. The bosonic core of the action (31) coincides with (27) after the identification

$$\varphi =\frac{1}{2}\left(\phi +\overline{\phi }\right),\lambda =\frac{i}{2}\left(\phi \overline{\phi }\right).$$
(32)
Thus we conclude that the Goldstone superfield action (31) describes the option when the internal $`U(1)`$ R-symmetry with the generator $`J`$ is also broken in addition to the (super)symmetries broken in the action (22). The bosonic coset is basically AdS$`{}_{5}{}^{}\times S^1\{x^{\alpha \dot{\alpha }},\varphi \}\times \{\lambda \}`$ and the bosonic part of the action (31) is just the static-gauge Nambu-Goto action of a 3-brane on this manifold. This solves the problem of constructing an invariant Goldstone superfield action for such PBGS option, as it was posed in . Note that both the Goldstone superfield actions (22), (31) are uniquely restored from the $`SU(2,2|1)`$ invariance and do not involve any free parameters, like their flat superspace counterparts. It is also worth mentioning that the corresponding Lagrangian densities, once again in tight analogy with the Goldstone superfield Lagrangians on the Minkowski superbackgrounds, are invariant under $`SU(2,2|1)`$ only up to full derivatives and are similar in this respect to WZW or CS Lagrangians.

5. Concluding remarks. In this note we have presented new nonlinear realizations of the simplest AdS5 superisometry group $`SU(2,2|1)`$ in terms of $`N=1`$ tensor and chiral Goldstone superfields. We have explicitly given the corresponding minimal Goldstone superfield actions, for the second option by dualizing the action for the first one, and shown that they provide a manifestly $`N=1`$ supersymmetric off-shell superfield form of worldvolume actions of L3-superbrane on AdS5 and scalar super 3-brane on AdS$`{}_{5}{}^{}\times S^1`$. The latter is a truncation of the AdS$`{}_{5}{}^{}\times S^5`$ D3-action. In the limit of infinite AdS5 radius these new actions go into their flat superspace counterparts describing the partial breaking of $`N=2,d=4`$ supersymmetry down to $`N=1`$ supersymmetry .

This study can be considered as a first step towards finding out Goldstone superfield actions for various patterns of partial breaking of AdS5 supersymmetries. As was already mentioned in , it is interesting to look for the action corresponding to the half-breaking of $`N=2`$ AdS5 supergroup $`SU(2,2|2)`$ in a supercoset with the AdS$`{}_{5}{}^{}\times S^1`$ bosonic part. The basic Goldstone superfield which we can expect to encounter in this case should be the appropriate generalization of the $`N=2`$ Maxwell superfield strength. This action should be a superconformal version of Dirac-Born-Infeld action describing the $`N=4N=2`$ partial breaking in the flat superspace . In this connection, let us recall that in the flat case there exists one more $`N=2N=1`$ PBGS option associated with the choice of vector $`N=1,d=4`$ multiplet as the Goldstone one and corresponding to the space-filling $`N=1`$ D3-brane . No AdS5 analog of this realization can be defined. The reason is that for achieving $`SU(2,2|1)`$ invariance one always needs a dilaton among the worldvolume Goldstone fields and hence within the relevant $`N=1`$ Goldstone superfield. In the vector Goldstone $`N=2`$ supermultiplet there are two scalar fields and, therefore, the above objection is evaded. An interesting related problem is to construct PBGS actions for the PP-wave type superbackgrounds via proper contractions of AdS supersymmetries and their Goldstone superfield actions.

Acknowledgements. This work was partially supported by the European Community’s Human Potential Programme under contract HPRN-CT-2000-00131 Quantum Spacetime, the INTAS-00-0254 grant and the Iniziativa Specifica MI12 of the Commissione IV of INFN, grant DFG 436 RUS 113/669, RFBR-DFG grant No. 02-0204002, as well as RFBR-CNRS grant No. 01-02-22005. E.I. and S.K. thank the INFN-LNF for warm hospitality during the course of this work.


text:
# New Nitrogen and Carbon in AF-supergiants

## 1. Introduction

Reviews on massive star evolution have shown there are a number of observations that suggest an additional parameter affects the evolution scenarios, ranging from blue-to-red supergiant ratios in clusters to CNO abundances in main-sequence and evolved stars; c.f., Maeder & Meynet (2000), Heger & Langer (2000 = HL00), Maeder & Conti (1994). In Galactic supergiants, the N/C ratios have long supported a parameter that varies from star-to-star, like rotation. This is because a variety of N/C ratios have been found within clusters of stars (thus, not natal variations), and because the N/C ratios do not clearly scale with effective temperature, luminosity, or mass.

Evolution models that include effects of rotation emerged in 2000. Not only can rotation help to explain the abundance ratios and certain mass discrepancies, but the new models also predict that massive stars may produce and mix primary nitrogen into their atmospheres (by Meynet & Maeder 2002). The new models have been calibrated based on abundance ratios, masses, rotation rates, and ages in the published literature. But they also make definate predictions that can be tested for further refinement.

Unfortunately, one direct test that is difficult to implement is to examine abundance ratios versus rotation rate. Rarely do we know the inclination angle of a rotating star. Also, as $`v`$sin$`i`$ increases, then the spectral lines become so shallow and broad that the atmospheric analysis becomes quite difficult and less certain. Fortunately, there are other indirect tests.

## 2. Boron and Rotation

One of the new predictions from stellar evolution calculations that include rotation is that the surface abundances of lithium, beryllium, and boron (LiBeB) will be rapidly depleted before significant mixing of any other material (see Heger & Langer 2000). These elements are fragile and easily destroyed when exposed to hot protons, thus any mixing in the atmosphere will rapidly dilute LiBeB and destroy those atoms that are mixed downwards. This should be detectable in main-sequence stars; but boron is the only element with measurable absorption lines in B-type stars.

Boron has been measured in a handful of main-sequence B-stars (see Figure 1) from the BIII 2066 and BII 1362 resonance lines. Both require UV spectral observations, such as with HST-STIS. There is a large range in the initial boron abundances in main-sequence B-stars, by a factor of 10 to 100. This variation is not natal since several stars within a single association show this range, for example, the star in the Orion association.

In Figure 1, boron is observed to be depleted before there is any detectable nitrogen enrichment. This matches predictions, as seen from the HL00 model for a 12 M star at 200 km s-1 through H-core burning and three sets of initial abundances \[(B, N) = (2.6, 7.6), (2.8, 7.7), (2.8, 7.8)\]. Thick lines connect boron abundances for the same stars from different analyses. The boron abundance papers are listed in the legend (see references), the nitrogen abundances are from Cunha & Lambert (1994 =CL94), Gies & Lambert (1992 =GL92), or Vrancken et al. (2000). Currently, the most extreme rotating models suggest that boron can be depleted by a factor of 10 before nitrogen is enriched (e.g., M = 25 M, v$`{}_{rot}{}^{}`$ 400 km s-1 ). The current data (especially star HD 36591 in Ori OB1) suggest even larger depletions are possible before nitrogen enrichment.

These boron depletions in main-sequence B-star, without significant nitrogen enhancements, are unique to rotating stellar evolution models. It is possibly to reproduce a boron-depletion with a nitrogen-enhancement through mass-transfer in a binary system (Wellstein, Langer, & Braun 2001).

## 3. CNO in Intermediate-Mass Supergiants

Another prediction of the rotating models is that there should be a wide range in the C and N abundances in evolved massive stars if these stars had a range in rotational velocities on the main-sequence. This has been seen and is well documented for Galactic stars in the literature, e.g., in O-stars (Herrero et al. 1992) in B-supergiants (McErlean et al. 1999, Lennon et al. 1988) and in A-F supergiants (Venn 1995). More recently, Smartt et al. (2002) found that Sher 25, an evolved early B-supergiant surrounded by nebular ejecta, has only a small nitrogen enrichment, incompatable with the predicted first dredge-up abundances. The fact that many of the N/C ratios in these stars ranged from solar ratios to only slightly enriched supports the idea that it is rotation that affects these abundances. Another possibility has been that the N/C ratios are affected by surface mixing and the first dredge-up during a previous red giant phase; in this case, we expect an offset in the mean N/C ratio (of $``$+0.5 dex for stars $``$10 M), which has not been seen in the literature until now (below).

In most of the supergiants, non-LTE corrections have had to be applied to the C, and especially the N, abundances. The non-LTE corrections result in N/C ratios in Galactic supergiants that show no relationships with effective temperature, luminosity, or mass. And a variety of N/C ratios are often found for stars in the same OB association. Thus, the variations in N/C are best attributed to star-to-star variations, such as rotation.

New Solar Abundances: Before proceeding with a comparison of N/C ratios, it is important to notice that the solar abundances have been significantly improved through the 3-D convection models by M. Asplund and collaborators. In this conference proceedings, new solar CNO abundances are presented, showing excellent agreement between a variety of abundance indicators for each element. In the rest of this paper, we will adopt these new solar abundances; 12 + log (C, N, O, Fe) = (8.41, 7.80, 8.66, 7.45).

## 4. New Nitrogen Abundances

Much of the sample for the N/C ratios in Galactic supergiants comes from the A-F supergiants (Venn 1995). Since then, new collisional excitation data has become available for NI (Frost et al. 1998), which does affect the non-LTE corrections (Przybilla 2002, and this proceedings), particularly for the hotter stars. This atomic data was sorely needed for the most reliable nitrogen abundance determinations since the collision excitation cross-sections were the most significant source of uncertainty in the Lemke & Venn (1996) nitrogen model calculations in A-stars. Now, the new atomic data shows that the NI level populations are more collisionally coupled, which reduces the NLTE corrections (which increases the NI abundances).

In this conference proceedings, we present a new table of nitrogen abundances for the A-F supergiants; see Table 1. These new results include the updates to the corrections calculated by NP (see Przybilla 2002 for a detailed description), which makes a substantial difference to the hotter supergiants, yielding higher nitrogen abundances. Only the NI $`\lambda \lambda `$7440 and $`\lambda \lambda `$8700 multiplets, and $`\lambda `$8629 line are included in these new NLTE calculations. The new NLTE corrections do not significantly affect the cooler stars since their NI atomic levels are already more closely collisionally coupled. Thus, similar calculations to those in Venn (1995) have been used for the six coolest stars (which include more lines). We have also recalculated the ATLAS9 model atmospheres using the most recent unix version. This has only a minor effect on the final abundances. The old abundances from Venn (1995) are also shown for comparison. The average nitrogen abundance has significantly increased, and the distribution in abundances with effective temperature is shown in Figure 2. Note that Asplund’s solar abundances listed above are used in these new figures.

In Figure 2, there is no clear trend in the N abundances with temperature above 8000 K. All stars show similar large N enrichments. The coolest stars show smaller N enrichments though, with one star (HD196379) showing no indication of internal mixing. We also show the NLTE CI abundances from Venn (1995), as well as new NLTE CII abundances in three stars from Przybilla (2002). The carbon abundances in the cool stars are from the weak $`\lambda `$7115 multiplet and show very small NLTE corrections. However the carbon abundances in the hotter supergiants (hollow circles) are from the strong $`\lambda `$9100 multiplet which have very large, and less certain NLTE corrections. In general, the N enrichments are accompanied by smaller C depletions, as expected in CN-cycled gas. Finally, the N/C ratios are shown. The N/C ratios scatter about the predicted first dredge-up abundances (on the red giant branch) for 9 to 20 M stars from the non-rotating evolution tracks of Schaller et al. (1992).

## 5. SMC Abundances

We have also recalculated the NLTE NI abundances in the SMC AF-supergiants from Venn (1999). Metallicity has a negligible effect on the statistical equilibrium of nitrogen in these atmospheres. The new SMC NI abundances are listed in Table 2 and plotted in Figure 3. Nearly all stars have higher nitrogen abundances from the new calculations. For only the two coolest stars, where the levels are more closely collisionally coupled, have we used similar calculations from Venn (1999, which also include more lines). Like with the Galactic stars, the new NLTE nitrogen abundances are higher than the published values, and there continues to be no clear trend in the abundances with temperature. Also like the Galactic stars, one very cool star shows no significant nitrogen enrichment. Notice that the initial \[N/Fe\] ratio for SMC stars is significantly below solar (dotted line) because of the different chemical evolution of this galaxy.

### 5.1. Primary Nitrogen?

That the SMC nitrogen abundances are so much larger than the first dredge-up predictions (indicated by the solid line in Figure 3) suggests these stars have undergone excessive mixing. Even if these are post-RGB stars, their nitrogen indicates even more mixing as predicted by the new rotating evolution models. Does this mean that there is primary nitrogen in the atmospheres of these metal-poor supergiants (as predicted for metal-poor stars by Meynet & Maeder 2002)? At present, we can only say that the metal-poor SMC stars have more nitrogen in their atmospheres. Its nucleosynthetic history is an open question.

## 6. More Rotation? First Dredge-Up?

A comparison of the N abundances in Galactic B-stars, Galactic AF-supergiants, and SMC AF-supergiants is shown in the histograms in Figure 4. Clearly the new Galactic AF-supergiant results are offset from the initial (solar and B-stars) N value by $``$0.5 dex. This was not seen in the previously published results (dashed line, where the mean nitrogen abundance was close to the initial N abundance). In the SMC, the same broad distribution in nitrogen is seen as before, but now with more stars at higher values.

In Maeder & Meynet’s review (2000), their Figure 6 shows that a large spread in the N abundances in the A-F supergiants are expected through variations in the rotational velocities. This spread can be larger in higher mass stars or lower metallicity stars. We certainly see a larger spread in the SMC stars versus the Galactic stars, and we expect this is due to metallicity since the stars have similar mass ranges (see Figure 5).

Since all of the AF-supergiants exhibit significantly enriched N abundances, and the metal-poor SMC stars show the largest enrichments of all, then these results suggest:

(a) All of the stars had very high rotation rates ($`>`$300 km s-1 ) on the main-sequence. This does not seem likely since the samples include alot of stars and the mean $`v`$sin$`i`$ values for these stars when on the main-sequence (B2-type) is only $``$200 km s-1 (e.g., Fukuda 1982, de Jager 1980).

(b) The stars have higher masses than expected. This is possible, but unlikely. The stars appear to range in mass from 5 to 25 M based on a comparison with standard evolution tracks (Figure 5), and even if those tracks are not appropriate (e.g., rotational mixing can affect the post-main sequence evolution) there does not appear to be a relationship in the N or N/C ratios with mass.

(c) Rotational mixing is more efficient than currently predicted.

(d) The stars have undergone the first dredge-up during a previous red giant phase. This certainly supports the N and N/C ratios observed, but since rotational mixing must also happen on the main-sequence (to explain the boron dispersion in main-sequence B-stars), then the scatter in the N abundances and N/C ratios could be attributed to early rotational evolution effects in addition to first dredge-up abundances. In the SMC, additional mixing beyond the first dredge-up predictions is clearly indicated. \[Of course, the few coolest stars with low N (SMC) or N/C ratios (Galactic) could not have undergone the first dredge-up yet and must be evolving directly from the main-sequence\].

Either of the last two options is likely given the current theoretical models. In addition, post-RGB evolution is indicated for blue supergiants (from a He-burning sequence parallel to the main-sequence) in metal-poor Local Group dwarf irregular galaxies from deep and accurate HST colour-magnitude diagrams (e.g., Dohm-Palmer et al. 1997 (SexA), 1998 (Gr8); Tolstoy et al. 1998 (LeoA)). Thus, excessive N enrichments in the SMC AF-supergiants are most simply explained as post-RGB first dredge-up abundances. But if we also consider the range in the nitrogen abundances, and the SMC B-star nitrogen enrichments, then main-sequence rotational mixing, as well as RGB convective mixing, are both indicated in metal-poor stars.

Is the first dredge-up indicated at Galactic metallicities? The new AF-supergiant nitrogen abundances do cluster around the first dredge-up predictions. But we also know now that rotational mixing is important in interpreting abundance ratios, in SMC supergiants and in Galactic main-sequence stars (e.g., boron). Thus, the Galactic AF-supergiants may also have been RGB stars in their past, but it is also possible that their \[N/C\] ratios could be explained by excessive rotational mixing alone.

## References

Barbuy B., Spite M., Spite F., Milone A., 1991, A&A, 247, 15 (B+91)

Cunha K., Lambert D.L., 1994, ApJ, 426, 170 (CL94)

Cunha K., et al., 1997, ApJ, 478, 211 (C+97)

de Jager C., 1980, in GAM Vol 19, The Brightest Stars (Dordrecht: Reidel), 50

Dohm-Palmer R., et al. 1998, AJ, 116, 1227

Dohm-Palmer R., et al. 1997, AJ, 114, 2527

Fukuda I., 1982, PASP, 94, 271

Frost R.M., et al., 1998, Journal of Applied Physics, 84, 2989

Gies D.R., Lambert D.L., 1992, ApJ, 387, 673 (GL92)

Heger A., Langer N., 2000, ApJ, 544, 1016 (HL00)

Herrero A., et al., 1992, A&A, 261, 209

Hill V., 1997, A&A, 324, 435 (H97)

Lemke M., Cunha K., Lambert D.L. (2000) in The Galactic Halo, eds A. Noels et al. (Liege: Institute d’Astrophysique et de Geophysique), 223 (L+00)

Lennon D.J., Brown P.J.F., Dufton P.L., 1988, A&A, 195, 208

Lennon D.J., et al., 1991, A&A, 252, 498 (L+91)

Lennon D.J., et al., 1996, A&A, 314, 243 (L+96)

Luck R.E., Lambert D.L., 1992, ApJS, 79, 303 (LL92)

Maeder A., Conti P.S. 1994, ARA&A, 32, 227

Maeder A., Meynet G., 2000, ARA&A, 38, 143

Maeder A., Meynet G., 2001, A&A, 373, 555

Meynet G., Maeder A., 2002, A&A, 381, 25

Proffitt C.R., et al., 1999, ApJ, 516, 342 (P+99)

Proffitt C.R., Quigley M.F., 2001, ApJ, 548, 429 (PQ01)

Przybilla N., 2002, PhD thesis, Univ. Munich.

Reitermann A., Baschek B., Stahl O., Wolf B., 1990, A&A, 234, 109 (R+90)

Rolleston W.R.J., et al., 1993, A&A, 277, 10 (R+93)

Schaller G., Schaerer D., Maeder A., Meynet G., 1992, A&AS, 96, 269

Smartt S.J., et al. 2002, A&A, 391, 979

Tolstoy E., et al., 1998, AJ, 116, 1244

Venn K.A., 1995, ApJ, 449, 839

Venn K.A., 1999, ApJ, 518, 405

Venn K.A., et al., 2002, ApJ, 565, 571

Vrancken M., et al., 2000, A&A, 358, 639

Wellstein S., Langer N., Braun H., 2001, A&A, 369, 939