Search results for "Combinatorics"
showing 10 items of 1770 documents
Regularity of renormalized solutions to nonlinear elliptic equations away from the support of measure data
2018
We prove boundedness and continuity for solutions to the Dirichlet problem for the equation $$ - {\rm{div}}(a(x,\nabla u)) = h(x,u) + \mu ,\;\;\;\;\;{\rm{in}}\;{\rm{\Omega }} \subset \mathbb{R}^{N},$$ where the left-hand side is a Leray-Lions operator from $$- {W}^{1,p}_0(\Omega)$$ into W−1,p′(Ω) with 1 < p < N, h(x,s) is a Caratheodory function which grows like ∣s∣p−1 and μ is a finite Radon measure. We prove that renormalized solutions, though not globally bounded, are Holder-continuous far from the support of μ.
The Dirichlet problem for the total variation flow
2001
Suppose that Ω is an open bounded domain with a Lipschitz boundary. The purpose of this chapter is to study the Dirichlet problem $$ \left\{ \begin{gathered} \frac{{\partial u}} {{\partial t}} = div\left( {\frac{{Du}} {{\left| {Du} \right|}}} \right)in Q = \left( {0,\infty } \right) \times \Omega , \hfill \\ u\left( {t,x} \right) = \phi \left( x \right)on S = \left( {0,\infty } \right) \times \partial \Omega , \hfill \\ u\left( {0,x} \right) = u_0 \left( x \right)in x \in \Omega \hfill \\ \end{gathered} \right. $$ (5.1) where u0 ∈ L1(Ω) and ϕ ∈ L1 (∂Ω). This evolution equation is related to the gradient descent method used to solve the problem $$ \begin{gathered} Minimize \int {_\Omega \lef…
Shape optimization for monge-ampére equations via domain derivative
2011
In this note we prove that, if $\Omega$ is a smooth, strictly convex, open set in $R^n$ $(n \ge 2)$ with given measure, the $L^1$ norm of the convex solution to the Dirichlet problem $\det D^2 u=1$ in $\Omega$, $u=0$ on $\partial\Omega$, is minimum whenever $\Omega$ is an ellipsoid.
Leveraging Specific Contexts and Outcomes to Generalize in Combinatorial Settings
2018
International audience; Generalization is a fundamental aspect of mathematics, and it is a practice with which undergraduate students should engage and gain fluency. It is important for students in combinatorial settings to be able to generalize, but combinatorics lends itself to engagement with specific examples, concrete outcomes, and particular contexts. In this paper, we seek to inform the nature of generalization in combinatorial settings by demonstrating ways in which students leverage specific, concrete settings to engage in generalizing activity in combinatorics. We provide two data examples that highlight ways in which concrete and specific ideas can be leveraged to help students d…
Anti-concentration property for random digraphs and invertibility of their adjacency matrices
2016
Let Dn,dDn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,dDn,d and M be its adjacency matrix. We show that M is invertible with probability at least View the MathML source1−Cln3d/d for C≤d≤cn/ln2nC≤d≤cn/ln2n, where c,Cc,C are positive absolute constants. To this end, we establish a few properties of directed d-regular graphs. One of them, a Littlewood–Offord-type anti-concentration property, is of independent interest: let J be a subset of vertices of G with |J|≤cn/d|J|≤cn/d. Let δiδi be the indicator of the event that the vertex i is connected to J and δ=(δ1,δ2,…,δn)∈{0,1}nδ=(δ1,δ2,…,δn)∈{0,1}n. Then δ is not concentrate…
An exact method for graph coloring
2006
International audience; We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.
Longest Motifs with a Functionally Equivalent Central Block
2004
International audience; This paper presents a generalization of the notion of longest repeats with a block of k don't care symbols introduced by [Crochemore et al., LATIN 2004] (for k fixed) to longest motifs composed of three parts: a first and last that parameterize match (that is, match via some symbol renaming, initially unknown), and a functionally equivalent central block. Such three-part motifs are called longest block motifs. Different types of functional equivalence, and thus of matching criteria for the central block are considered, which include as a subcase the one treated in [Crochemore et al., LATIN 2004] and extend to the case of regular expressions with no Kleene closure or …
Distance graphs and the T-coloring problem
1999
Abstract The T-coloring problem is, given a graph G = (V, E), a set T of nonnegative integers containing 0, and a ‘span’ bound s ⩾ 0, to compute an integer coloring f of the vertices of G such that |f(ν) − f(w)| ∉ T ∀νw ∈ E and max f − min f ⩽ s. This problem arises in the planning of channel assignments for broadcast networks. When restricted to complete graphs, the T-coloring problem boils down to a number problem which can be solved efficiently for many types of sets T. The paper presents results indicating that this is not the case if the set T is arbitrary. To these ends, the class of distance graphs is introduced, which consists of all graphs G : G ≅ G(A) for some (finite) set of posi…
On the additivity of block designs
2016
We show that symmetric block designs $${\mathcal {D}}=({\mathcal {P}},{\mathcal {B}})$$D=(P,B) can be embedded in a suitable commutative group $${\mathfrak {G}}_{\mathcal {D}}$$GD in such a way that the sum of the elements in each block is zero, whereas the only Steiner triple systems with this property are the point-line designs of $${\mathrm {PG}}(d,2)$$PG(d,2) and $${\mathrm {AG}}(d,3)$$AG(d,3). In both cases, the blocks can be characterized as the only k-subsets of $$\mathcal {P}$$P whose elements sum to zero. It follows that the group of automorphisms of any such design $$\mathcal {D}$$D is the group of automorphisms of $${\mathfrak {G}}_\mathcal {D}$$GD that leave $$\mathcal {P}$$P in…
Combinatorial isomorphism between Fibonacci classes
2008
Abstract In 1985 Simion and Schmidt showed that the set S n (T 3) of length n permutations avoiding the set of patterns T 3={123, 132, 213} is counted by (the second order) Fibonacci numbers. They also presented a constructive bijection between the set F n–1 of length (n–1) binary strings with no two consecutive 1s and S n (T 3). In 2005, Egge and Mansour generalized the first Simion-Simion’s result and showed that S n (T p ), the set of permutations avoiding the patterns T p ={12…p, 132, 213}, is counted by the (p–1)th order Fibonacci numbers. In this paper we extend the second Simion-Schmidt’s result by giving a bijection between the set of length (n–1) binary strings with no (p–1) consec…