A simple graph on $n$ vertices may contain a lot of maximum cliques. But how many can it potentially contain? We will define prime and composite graphs, and we will show that if $n \ge 15$, then the grpahs with the maximum number of maximum cliques have to be composite. Moreover, we will show an edge bound from which we will prove that if any factor of a composite graph has $\omega(G_i) \ge 5$, then it cannot have the maximum number of maximum cliques. Using this we will show that the graph that contains $3^{\lfloor n/3 \rfloor}c$ maximum cliques has the most number of maximum cliques on $n$ vertices, where $c\in\{1,\frac{4}{3},2\}$, depending on $n \text{ mod } 3$.
相關內容
Given a graph~$G$, the domination number, denoted by~$\gamma(G)$, is the minimum cardinality of a dominating set in~$G$. Dual to the notion of domination number is the packing number of a graph. A packing of~$G$ is a set of vertices whose pairwise distance is at least three. The packing number~$\rho(G)$ of~$G$ is the maximum cardinality of one such set. Furthermore, the inequality~$\rho(G) \leq \gamma(G)$ is well-known. Henning et al.\ conjectured that~$\gamma(G) \leq 2\rho(G)+1$ if~$G$ is subcubic. In this paper we progress towards this conjecture by showing that~${\gamma(G) \leq \frac{120}{49}\rho(G)}$ if~$G$ is a bipartite cubic graph. We also show that $\gamma(G) \leq 3\rho(G)$ if~$G$ is a maximal outerplanar graph, and that~$\gamma(G) \leq 2\rho(G)$ if~$G$ is a biconvex graph. Moreover, in the last case, we show that this upper bound is tight.
Multigraded Betti numbers are one of the simplest invariants of multiparameter persistence modules. This invariant is useful in theory -- it completely determines the Hilbert function of the module and the isomorphism type of the free modules in its minimal free resolution -- as well as in practice -- it is easy to visualize and it is one of the main outputs of current multiparameter persistent homology software, such as RIVET. However, to the best of our knowledge, no bottleneck stability result with respect to the interleaving distance has been established for this invariant so far, and this potential lack of stability limits its practical applications. We prove a stability result for multigraded Betti numbers, using an efficiently computable bottleneck-type dissimilarity function we introduce. Our notion of matching is inspired by recent work on signed barcodes, and allows matching bars of the same module in homological degrees of different parity, in addition to matchings bars of different modules in homological degrees of the same parity. Our stability result is a combination of Hilbert's syzygy theorem, Bjerkevik's bottleneck stability for free modules, and a novel stability result for projective resolutions. We also prove, in the $2$-parameter case, a $1$-Wasserstein stability result for Hilbert functions with respect to the $1$-presentation distance of Bjerkevik and Lesnick.
We have developed an efficient and unconditionally energy-stable method for simulating droplet formation dynamics. Our approach involves a novel time-marching scheme based on the scalar auxiliary variable technique, specifically designed for solving the Cahn-Hilliard-Navier-Stokes phase field model with variable density and viscosity. We have successfully applied this method to simulate droplet formation in scenarios where a Newtonian fluid is injected through a vertical tube into another immiscible Newtonian fluid. To tackle the challenges posed by nonhomogeneous Dirichlet boundary conditions at the tube entrance, we have introduced additional nonlocal auxiliary variables and associated ordinary differential equations. These additions effectively eliminate the influence of boundary terms. Moreover, we have incorporated stabilization terms into the scheme to enhance its numerical effectiveness. Notably, our resulting scheme is fully decoupled, requiring the solution of only linear systems at each time step. We have also demonstrated the energy decaying property of the scheme, with suitable modifications. To assess the accuracy and stability of our algorithm, we have conducted extensive numerical simulations. Additionally, we have examined the dynamics of droplet formation and explored the impact of dimensionless parameters on the process. Overall, our work presents a refined method for simulating droplet formation dynamics, offering improved efficiency, energy stability, and accuracy.
We construct a new family of permutationally invariant codes that correct $t$ Pauli errors for any $t\ge 1$. We also show that codes in the new family correct quantum deletion errors as well as spontaneous decay errors. Our construction contains some of the previously known permutationally invariant quantum codes as particular cases, which also admit transversal gates. In many cases, the codes in the new family are shorter than the best previously known explicit permutationally invariant codes for Pauli errors and deletions. Furthermore, our new code family includes a new $((4,2,2))$ optimal single-deletion-correcting code. As a separate result, we generalize the conditions for permutationally invariant codes to correct $t$ Pauli errors from the previously known results for $t=1$ to any number of errors. For small $t$, these conditions can be used to construct new examples of codes by computer.
In this note, we apply some techniques developed in [1]-[3] to give a particular construction of bivariate Abelian Codes from cyclic codes, multiplying their dimension and preserving their apparent distance. We show that, in the case of cyclic codes whose maximum BCH bound equals its minimum distance the obtained abelian code verifies the same property; that is, the strong apparent distance and the minimum distance coincide. We finally use this construction to multiply Reed-Solomon codes to abelian codes
We consider finite element approximations to the optimal constant for the Hardy inequality with exponent $p=2$ in bounded domains of dimension $n=1$ or $n \geq 3$. For finite element spaces of piecewise linear and continuous functions on a mesh of size $h$, we prove that the approximate Hardy constant converges to the optimal Hardy constant at a rate proportional to $1/| \log h |^2$. This result holds in dimension $n=1$, in any dimension $n \geq 3$ if the domain is the unit ball and the finite element discretization exploits the rotational symmetry of the problem, and in dimension $n=3$ for general finite element discretizations of the unit ball. In the first two cases, our estimates show excellent quantitative agreement with values of the discrete Hardy constant obtained computationally.
Using dominating sets to separate vertices of graphs is a well-studied problem in the larger domain of identification problems. In such problems, the objective is typically to separate any two vertices of a graph by their unique neighbourhoods in a suitably chosen dominating set of the graph. Such a dominating and separating set is often referred to as a \emph{code} in the literature. Depending on the types of dominating and separating sets used, various problems arise under various names in the literature. In this paper, we introduce a new problem in the same realm of identification problems whereby the code, called the \emph{open-separating dominating code}, or the \emph{OSD-code} for short, is a dominating set and uses open neighbourhoods for separating vertices. The paper studies the fundamental properties concerning the existence, hardness and minimality of OSD-codes. Due to the emergence of a close and yet difficult to establish relation of the OSD-codes with another well-studied code in the literature called the open locating dominating codes, or OLD-codes for short, we compare the two on various graph classes. Finally, we also provide an equivalent reformulation of the problem of finding OSD-codes of a graph as a covering problem in a suitable hypergraph and discuss the polyhedra associated with OSD-codes, again in relation to OLD-codes of some graph classes already studied in this context.
For a sequence of random structures with $n$-element domains over a relational signature, we define its first order (FO) complexity as a certain subset in the Banach space $\ell^{\infty}/c_0$. The well-known FO zero-one law and FO convergence law correspond to FO complexities equal to $\{0,1\}$ and a subset of $\mathbb{R}$, respectively. We present a hierarchy of FO complexity classes, introduce a stochastic FO reduction that allows to transfer complexity results between different random structures, and deduce using this tool several new logical limit laws for binomial random structures. Finally, we introduce a conditional distribution on graphs, subject to a FO sentence $\varphi$, that generalises certain well-known random graph models, show instances of this distribution for every complexity class, and prove that the set of all $\varphi$ validating 0--1 law is not recursively enumerable.
In this paper, we consider the hull of an algebraic geometry code, meaning the intersection of the code and its dual. We demonstrate how codes whose hulls are algebraic geometry codes may be defined using only rational places of Kummer extensions (and Hermitian function fields in particular). Our primary tool is explicitly constructing non-special divisors of degrees $g$ and $g-1$ on certain families of function fields with many rational places, accomplished by appealing to Weierstrass semigroups. We provide explicit algebraic geometry codes with hulls of specified dimensions, producing along the way linearly complementary dual algebraic geometric codes from the Hermitian function field (among others) using only rational places and an answer to an open question posed by Ballet and Le Brigand for particular function fields. These results complement earlier work by Mesnager, Tang, and Qi that use lower-genus function fields as well as instances using places of a higher degree from Hermitian function fields to construct linearly complementary dual (LCD) codes and that of Carlet, Mesnager, Tang, Qi, and Pellikaan to provide explicit algebraic geometry codes with the LCD property rather than obtaining codes via monomial equivalences.
We build on the theory of ontology logs (ologs) created by Spivak and Kent, and define a notion of wiring diagrams. In this article, a wiring diagram is a finite directed labelled graph. The labels correspond to types in an olog; they can also be interpreted as readings of sensors in an autonomous system. As such, wiring diagrams can be used as a framework for an autonomous system to form abstract concepts. We show that the graphs underlying skeleton wiring diagrams form a category. This allows skeleton wiring diagrams to be compared and manipulated using techniques from both graph theory and category theory. We also extend the usual definition of graph edit distance to the case of wiring diagrams by using operations only available to wiring diagrams, leading to a metric on the set of all skeleton wiring diagrams. In the end, we give an extended example on calculating the distance between two concepts represented by wiring diagrams, and explain how to apply our framework to any application domain.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191