skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on April 1, 2026

Title: L-Systems and the Lovász Number
Abstract Given integers$$n> k > 0$$ n > k > 0 , and a set of integers$$L \subset [0, k-1]$$ L [ 0 , k - 1 ] , anL-systemis a family of sets$$\mathcal {F}\subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) $$ F [ n ] k such that$$|F \cap F'| \in L$$ | F F | L for distinct$$F, F'\in \mathcal {F}$$ F , F F .L-systems correspond to independent sets in a certain generalized Johnson graphG(n, k, L), so that the maximum size of anL-system is equivalent to finding the independence number of the graphG(n, k, L). TheLovász number$$\vartheta (G)$$ ϑ ( G ) is a semidefinite programming approximation of the independence number$$\alpha $$ α of a graphG. In this paper, we determine the leading order term of$$\vartheta (G(n, k, L))$$ ϑ ( G ( n , k , L ) ) of any generalized Johnson graph withkandLfixed and$$n\rightarrow \infty $$ n . As an application of this theorem, we give an explicit construction of a graphGonnvertices with a large gap between the Lovász number and the Shannon capacityc(G). Specifically, we prove that for any$$\epsilon > 0$$ ϵ > 0 , for infinitely manynthere is a generalized Johnson graphGonnvertices which has ratio$$\vartheta (G)/c(G) = \Omega (n^{1-\epsilon })$$ ϑ ( G ) / c ( G ) = Ω ( n 1 - ϵ ) , which improves on all known constructions. The graphGa fortiorialso has ratio$$\vartheta (G)/\alpha (G) = \Omega (n^{1-\epsilon })$$ ϑ ( G ) / α ( G ) = Ω ( n 1 - ϵ ) , which greatly improves on the best known explicit construction.  more » « less
Award ID(s):
2038080
PAR ID:
10615619
Author(s) / Creator(s):
Publisher / Repository:
Springer
Date Published:
Journal Name:
Combinatorica
Volume:
45
Issue:
2
ISSN:
0209-9683
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. A<sc>bstract</sc> Using data samples of 983.0 fb−1and 427.9 fb−1accumulated with the Belle and Belle II detectors operating at the KEKB and SuperKEKB asymmetric-energye+ecolliders, singly Cabibbo-suppressed decays$$ {\Xi}_c^{+}\to p{K}_S^0 $$ Ξ c + p K S 0 ,$$ {\Xi}_c^{+}\to \Lambda {\pi}^{+} $$ Ξ c + Λ π + , and$$ {\Xi}_c^{+}\to {\Sigma}^0{\pi}^{+} $$ Ξ c + Σ 0 π + are observed for the first time. The ratios of branching fractions of$$ {\Xi}_c^{+}\to p{K}_S^0 $$ Ξ c + p K S 0 ,$$ {\Xi}_c^{+}\to \Lambda {\pi}^{+} $$ Ξ c + Λ π + , and$$ {\Xi}_c^{+}\to {\Sigma}^0{\pi}^{+} $$ Ξ c + Σ 0 π + relative to that of$$ {\Xi}_c^{+}\to {\Xi}^{-}{\pi}^{+}{\pi}^{+} $$ Ξ c + Ξ π + π + are measured to be$$ {\displaystyle \begin{array}{c}\frac{\mathcal{B}\left({\Xi}_c^{+}\to p{K}_S^0\right)}{\mathcal{B}\left({\Xi}_c^{+}\to {\Xi}^{-}{\pi}^{+}{\pi}^{+}\right)}=\left(2.47\pm 0.16\pm 0.07\right)\%,\\ {}\frac{\mathcal{B}\left({\Xi}_c^{+}\to \Lambda {\pi}^{+}\right)}{\mathcal{B}\left({\Xi}_c^{+}\to {\Xi}^{-}{\pi}^{+}{\pi}^{+}\right)}=\left(1.56\pm 0.14\pm 0.09\right)\%,\\ {}\frac{\mathcal{B}\left({\Xi}_c^{+}\to {\Sigma}^0{\pi}^{+}\right)}{\mathcal{B}\left({\Xi}_c^{+}\to {\Xi}^{-}{\pi}^{+}{\pi}^{+}\right)}=\left(4.13\pm 0.26\pm 0.22\right)\%.\end{array}} $$ B Ξ c + p K S 0 B Ξ c + Ξ π + π + = 2.47 ± 0.16 ± 0.07 % , B Ξ c + Λ π + B Ξ c + Ξ π + π + = 1.56 ± 0.14 ± 0.09 % , B Ξ c + Σ 0 π + B Ξ c + Ξ π + π + = 4.13 ± 0.26 ± 0.22 % . Multiplying these values by the branching fraction of the normalization channel,$$ \mathcal{B}\left({\Xi}_c^{+}\to {\Xi}^{-}{\pi}^{+}{\pi}^{+}\right)=\left(2.9\pm 1.3\right)\% $$ B Ξ c + Ξ π + π + = 2.9 ± 1.3 % , the absolute branching fractions are determined to be$$ {\displaystyle \begin{array}{c}\mathcal{B}\left({\Xi}_c^{+}\to p{K}_S^0\right)=\left(7.16\pm 0.46\pm 0.20\pm 3.21\right)\times {10}^{-4},\\ {}\mathcal{B}\left({\Xi}_c^{+}\to \Lambda {\pi}^{+}\right)=\left(4.52\pm 0.41\pm 0.26\pm 2.03\right)\times {10}^{-4},\\ {}\mathcal{B}\left({\Xi}_c^{+}\to {\Sigma}^0{\pi}^{+}\right)=\left(1.20\pm 0.08\pm 0.07\pm 0.54\right)\times {10}^{-3}.\end{array}} $$ B Ξ c + p K S 0 = 7.16 ± 0.46 ± 0.20 ± 3.21 × 10 4 , B Ξ c + Λ π + = 4.52 ± 0.41 ± 0.26 ± 2.03 × 10 4 , B Ξ c + Σ 0 π + = 1.20 ± 0.08 ± 0.07 ± 0.54 × 10 3 . The first and second uncertainties above are statistical and systematic, respectively, while the third ones arise from the uncertainty in$$ \mathcal{B}\left({\Xi}_c^{+}\to {\Xi}^{-}{\pi}^{+}{\pi}^{+}\right) $$ B Ξ c + Ξ π + π +
    more » « less
  2. Abstract We consider the Cauchy problem for the logarithmically singular surface quasi-geostrophic (SQG) equation, introduced by Ohkitani,$$\begin{aligned} \begin{aligned} \partial _t \theta - \nabla ^\perp \log (10+(-\Delta )^{\frac{1}{2}})\theta \cdot \nabla \theta = 0, \end{aligned} \end{aligned}$$ t θ - log ( 10 + ( - Δ ) 1 2 ) θ · θ = 0 , and establish local existence and uniqueness of smooth solutions in the scale of Sobolev spaces with exponent decreasing with time. Such a decrease of the Sobolev exponent is necessary, as we have shown in the companion paper (Chae et al. in Illposedness via degenerate dispersion for generalized surface quasi-geostrophic equations with singular velocities,arXiv:2308.02120) that the problem is strongly ill-posed in any fixed Sobolev spaces. The time dependence of the Sobolev exponent can be removed when there is a dissipation term strictly stronger than log. These results improve wellposedness statements by Chae et al. (Comm Pure Appl Math 65(8):1037–1066, 2012). This well-posedness result can be applied to describe the long-time dynamics of the$$\delta $$ δ -SQG equations, defined by$$\begin{aligned} \begin{aligned} \partial _t \theta + \nabla ^\perp (10+(-\Delta )^{\frac{1}{2}})^{-\delta }\theta \cdot \nabla \theta = 0, \end{aligned} \end{aligned}$$ t θ + ( 10 + ( - Δ ) 1 2 ) - δ θ · θ = 0 , for all sufficiently small$$\delta >0$$ δ > 0 depending on the size of the initial data. For the same range of$$\delta $$ δ , we establish global well-posedness of smooth solutions to the dissipative SQG equations. 
    more » « less
  3. A<sc>bstract</sc> A time-dependent, flavour-tagged measurement ofCPviolation is performed withB0→ D+Dand$$ {B}_s^0 $$ B s 0 →$$ {D}_s^{+}{D}_s^{-} $$ D s + D s decays, using data collected by the LHCb detector in proton-proton collisions at a centre-of-mass energy of 13 TeV corresponding to an integrated luminosity of 6 fb−1. InB0→ D+Ddecays theCP-violation parameters are measured to be$$ {\displaystyle \begin{array}{c}{S}_{D^{+}{D}^{-}}=-0.552\pm 0.100\left(\textrm{stat}\right)\pm 0.010\left(\textrm{syst}\right),\\ {}{C}_{D^{+}{D}^{-}}=0.128\pm 0.103\left(\textrm{stat}\right)\pm 0.010\left(\textrm{syst}\right).\end{array}} $$ S D + D = 0.552 ± 0.100 stat ± 0.010 syst , C D + D = 0.128 ± 0.103 stat ± 0.010 syst . In$$ {B}_s^0 $$ B s 0 →$$ {D}_s^{+}{D}_s^{-} $$ D s + D s decays theCP-violating parameter formulation in terms ofϕsand|λ|results in$$ {\displaystyle \begin{array}{c}{\phi}_s=-0.086\pm 0.106\left(\textrm{stat}\right)\pm 0.028\left(\textrm{syst}\right)\textrm{rad},\\ {}\mid {\lambda}_{D_s^{+}{D}_s^{-}}\mid =1.145\pm 0.126\left(\textrm{stat}\right)\pm 0.031\left(\textrm{syst}\right).\end{array}} $$ ϕ s = 0.086 ± 0.106 stat ± 0.028 syst rad , λ D s + D s = 1.145 ± 0.126 stat ± 0.031 syst . These results represent the most precise single measurement of theCP-violation parameters in their respective channels. For the first time in a single measurement,CPsymmetry is observed to be violated inB0→ D+Ddecays with a significance exceeding six standard deviations. 
    more » « less
  4. A<sc>bstract</sc> A search for the fully reconstructed$$ {B}_s^0 $$ B s 0 → μ+μγdecay is performed at the LHCb experiment using proton-proton collisions at$$ \sqrt{s} $$ s = 13 TeV corresponding to an integrated luminosity of 5.4 fb−1. No significant signal is found and upper limits on the branching fraction in intervals of the dimuon mass are set$$ {\displaystyle \begin{array}{cc}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu}^{+}{\mu}^{-}\right)\in \left[2{m}_{\mu },1.70\right]\textrm{GeV}/{c}^2,\\ {}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<7.7\times {10}^{-8},&\ m\left({\mu}^{+}{\mu}^{-}\right)\in \left[\textrm{1.70,2.88}\right]\textrm{GeV}/{c}^2,\\ {}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu}^{+}{\mu}^{-}\right)\in \left[3.92,{m}_{B_s^0}\right]\textrm{GeV}/{c}^2,\end{array}} $$ B B s 0 μ + μ γ < 4.2 × 10 8 , m μ + μ 2 m μ 1.70 GeV / c 2 , B B s 0 μ + μ γ < 7.7 × 10 8 , m μ + μ 1.70, 2.88 GeV / c 2 , B B s 0 μ + μ γ < 4.2 × 10 8 , m μ + μ 3.92 m B s 0 GeV / c 2 , at 95% confidence level. Additionally, upper limits are set on the branching fraction in the [2mμ,1.70] GeV/c2dimuon mass region excluding the contribution from the intermediateϕ(1020) meson, and in the region combining all dimuon-mass intervals. 
    more » « less
  5. Abstract A search for the very rare$$B^{*0}\rightarrow \mu ^+\mu ^-$$ B 0 μ + μ - and$$B_{s}^{*0}\rightarrow \mu ^+\mu ^-$$ B s 0 μ + μ - decays is conducted by analysing the$$B_c^+\rightarrow \pi ^+\mu ^+\mu ^-$$ B c + π + μ + μ - process. The analysis uses proton-proton collision data collected with the LHCb detector between 2011 and 2018, corresponding to an integrated luminosity of 9$$\text {\,fb}^{-1}$$ \,fb - 1 . The signal signatures correspond to simultaneous peaks in the$$\mu ^+\mu ^-$$ μ + μ - and$$\pi ^+\mu ^+\mu ^-$$ π + μ + μ - invariant masses. No evidence for an excess of events over background is observed for either signal decay mode. Upper limits at the$$90\%$$ 90 % confidence level are set on the branching fractions relative to that for$$B_c^+\rightarrow J\hspace{-1.66656pt}/\hspace{-1.111pt}\psi \pi ^+$$ B c + J / ψ π + decays,$$\begin{aligned} \mathcal{R}_{B^{*0}(\mu ^+\mu ^-)\pi ^+/J\hspace{-1.66656pt}/\hspace{-1.111pt}\psi \pi ^+}&< 3.8\times 10^{-5}\ \text { and }\\ \mathcal{R}_{B_{s}^{*0}(\mu ^+\mu ^-)\pi ^+/J\hspace{-1.66656pt}/\hspace{-1.111pt}\psi \pi ^+}&< 5.0\times 10^{-5}. \end{aligned}$$ R B 0 ( μ + μ - ) π + / J / ψ π + < 3.8 × 10 - 5 and R B s 0 ( μ + μ - ) π + / J / ψ π + < 5.0 × 10 - 5 .  
    more » « less