Short propositional refutations for dense random 3CNF formulas

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many propositional proof systems are known. Most notable are the exponential-size resolution refutation lower bounds for random 3CNF formulas with Ω(n^1.5−ε)$\mathrm{\Omega }(n^{1.5-\epsilon })$ clauses (Chvátal and Szemerédi [14], Ben-Sasson and Wigderson [10]). On the other hand, the only known non-trivial upper bound on the size of random 3CNF refutations in a non-abstract propositional proof system is for resolution with Ω(n²/log?n)$\mathrm{\Omega }(n^2/\log ?n)$ clauses, shown by Beame et al. [6]. In this paper we show that already standard propositional proof systems, within the hierarchy of Frege proofs, admit short refutations for random 3CNF formulas, for sufficiently large clause-to-variable ratio. Specifically, we demonstrate polynomial-size propositional refutations whose lines are TC⁰${\mathit{T}\mathit{C}}^0$ formulas (i.e., TC⁰${\mathit{T}\mathit{C}}^0$-Frege proofs) for random 3CNF formulas with n   variables and Ω(n^1.4)$\mathrm{\Omega }(n^{1.4})$ clauses.     

The incidence game chromatic number

We introduce the incidence game chromatic number which unifies the ideas of game chromatic number and incidence coloring number of an undirected graph. For k-degenerate graphs with maximum degree Δ, the upper bound 2Δ+4k−2 for the incidence game chromatic number is given. If Δ≥5k, we improve this bound to the value 2Δ+3k−1. We also determine the exact incidence game chromatic number of cycles, stars and sufficiently large wheels and obtain the lower bound for the incidence game chromatic number of graphs of maximum degree Δ.     

Values of automorphic L-functions with prime power level at the point $$$$

We discuss in this work the distributions of values of L(1, f), where f is a primitive cusp form whose level is a prime power. We prove the upper bound part of the Montgomery–Vaughan’s first conjecture and give a weaker version of the lower bound part for automorphic L-functions in this case. We establish an unweighted trace formula in aspect of prime power level in our proof.     

Improved bounds on equilibria solutions in the network design game

In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most \(H_n\), the n-th harmonic number. This bound is tight for directed graphs.For undirected graphs, it has only recently been shown that the price of stability is at most \(H_n \left( 1-\frac{1}{\Theta (n^4)} \right) \), while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most \(H_{n/2} + \varepsilon \) for any \(\varepsilon \) starting from some suitable \(n \ge n(\varepsilon )\).We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of \(\frac{4}{3}\) and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90–100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of \(\frac{4}{3}\), and provide an upper bound of \(\frac{26}{19}\). To the end, we conjecture and argue that the right answer is \(\frac{4}{3}\).     

On the deque conjecture for the splay algorithm

Splay is a simple, efficient algorithm for searching binary search trees, devised by Sleator and Tarjan, that reorganizes the tree after each search by means of rotations. An open conjecture of Sleator and Tarjan states that Splay is, in essence, the fastest algorithm for processing any sequence of search operations on a binary search tree, using only rotations to reorganize the tree. Tarjan proved a basic special case of this conjecture, called theScanning Theorem, and conjectured a more general special case, called theDeque Conjecture. The Deque Conjecture states that Splay requires linear time to process sequences of deque operations on a binary tree. We prove the following results:

1. Almost tight lower and upper bounds on the maximum numbers of occurrences of various types of right rotations in a sequence of right rotations performed on a binary tree. In particular, the lower bound for right 2-turns refutes Sleator's Right Turn Conjecture.
2. A linear times inverse Ackerman upper bound for the Deque Conjecture. This bound is derived using the above upper bounds.
3. Two new proofs of the Scanning Theorem, one, a simple potential-based proof that solves Tarjan's problem of finding a potential-based proof for the theorem, the other, an inductive proof that generalizes the theorem.

     

Squarefree P-modules and the cd-index

In this paper, we introduce a new algebraic concept, which we call squarefree P-modules. This concept is inspired from Karu's proof of the non-negativity of the cd-indices of Gorenstein* posets, and supplies a way to study cd-indices from the viewpoint of commutative algebra. Indeed, by using the theory of squarefree P-modules, we give several new algebraic and combinatorial results on CW-posets. First, we define an analogue of the cd-index for any CW-poset and prove its non-negativity when a CW-poset is Cohen–Macaulay. This result proves that the h-vector of the barycentric subdivision of a Cohen–Macaulay regular CW-complex is unimodal. Second, we prove that the Stanley–Reisner ring of the barycentric subdivision of an odd dimensional Cohen–Macaulay polyhedral complex has the weak Lefschetz property. Third, we obtain sharp upper bounds of the cd-indices of Gorenstein* posets for a fixed rank generating function.     

On hyperovals of polar spaces

We derive lower and upper bounds for the size of a hyperoval of a finite polar space of rank 3. We give a computer-free proof for the uniqueness, up to isomorphism, of the hyperoval of size 126 of H(5, 4) and prove that the near hexagon ${\mathbb E_3}$ has up to isomorphism a unique full embedding into the dual polar space DH(5, 4).     

Bounds for the error of linear systems of equations using the theory of moments

Consider the system, of linear equations Ax = b where A is an n × n real symmetric, positive definite matrix and b is a known vector. Suppose we are given an approximation to x, ξ, and we wish to determine upper and lower bounds for ∥ x − ξ ∥ where ∥ ··· ∥ indicates the euclidean norm. Given the sequence of vectors {r_i}_{i^k = 0}, where r_i = Ar_{i − 1} and r₀ = b − Aξ, it is shown how to construct a sequence of upper and lower bounds for ∥ x − ξ ∥ using the theory of moments.     

The Relaxed Edge-Coloring Game and <Emphasis Type="Italic">k</Emphasis>-Degenerate Graphs

The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ(F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ?j and d≥2j+2 for 0≤j≤Δ?1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767–1775, 2007). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767–1775, 2007) by showing that if G is k-degenerate with Δ(G)=Δ and j∈[Δ+k?1], then there exists a function h(k,j) such that Alice has a winning strategy for this game with r=Δ+k?j and d≥h(k,j).     

A sharp eigenvalue theorem for fractional elliptic equations

The invisibility graph I(X) of a set X ? R ^d is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in X. We consider the following three parameters of a set X: the clique number ω(I(X)), the chromatic number χ(I(X)) and the convexity number γ(X), which is the minimum number of convex subsets of X that cover X.We settle a conjecture of Matou?ek and Valtr claiming that for every planar set X, γ(X) can be bounded in terms of χ(I(X)). As a part of the proof we show that a disc with n one-point holes near its boundary has χ(I(X)) ≥ log log(n) but ω(I(X)) = 3.We also find sets X in R⁵ with χ(X) = 2, but γ(X) arbitrarily large.     

From Single Agent to Multi-Agent via Hypersequents

In this paper we present a sequent calculus for the multi-agent system S5 _m . First, we introduce a particularly simple alternative Kripke semantics for the system S5 _m . Then, we construct a hypersequent calculus for S5 _m that reflects at the syntactic level this alternative interpretation. We prove that this hypersequent calculus is theoremwise equivalent to the Hilbert-style system S5 _m , that it is contraction-free and cut-free, and finally that it is decidable. All results are proved in a purely syntactic way and the cut-elimination procedure yields an upper bound of ip ₂ (n, 0) where ip ₂ is an hyperexponential function of base 2.     

Extensions and generalizations of a theorem of Widder and of the theory of symmetric local semigroups

The theory of symmetric local semigroups due to A. Klein and L. Landau (J. Funct. Anal.44 (1981), 121–136) is generalized to semigroups indexed by subsets of $\text{R}$ⁿ for n > 1. The result implies a similar result of A. E. Nussbaum (J. Funct. Anal.48 (1982), 213–223). It is further generalized to semigroups that are symmetric local in some directions and unitary in others. The results are used to give a simple proof of A. Devinatz's (Duke Math. J.22 (1955), 185–192) and N. I. Akhiezer's (“the Classical Moment Problem and Some Related Questions,” Hafner, New York, 1965) generalization of a theorem of Widder concerning the representation of functions as Laplace integrals. This result is extended to the representation as a Laplace integral of a function taking values in $\text{B}$($\text{R}$), the set of bounded linear operators on a Hilbert space $\text{R}$. Also, a theorem is proved encompassing both the result of Devinatz and Akhiezer, and Bochner's theorem on the representation of positive definite functions as Fourier integrals.     

Variational Inequalities: an Elementary Approach

We will deal with the following problem: Let M be an n×n matrix with real entries. Under which conditions the family of inequalities: x∈? ⁿ ;x?0;M·x?0has non–trivial solutions? We will prove that a sufficient condition is given by m_i,j+m_j,i?0 (1?i,j?n); from this result we will derive an elementary proof of the existence theorem for Variational Inequalities in the framework of Monotone Operators.     

A proof for the Burton and Miller integral equation approach for the Helmholtz equation

The A. J. Burton and G. F. Miller integral equation formulation for the exterior Neumann problem for the Helmholtz equation [Proc. Roy. Soc. London Ser. A323 (1971), 201–210] is one of the most important integral equation approaches in that area. However, the kind of space settings they are working with is not clear. Evidently, the Fredholm integral equation of the second kind which they deduced is not well defined on the usual C(S) or L²(S), where S is a closed bounded smooth surface. In this paper, appropriate space settings are found and a rigorous existence and uniqueness proof for their integral equation formulation is given.     

Some remarks on a game of Telgársky

In [3] R. Telgársky (1975) asked: does the first player have a winning strategy in the game G(F,X×X) if the first player has a winning strategy in the game G(F,X)? I give a positive answer to this question and prove that this result is also true for spaces where the first player has a winning strategy in game G(K,X) where K=1, F, C, for σC if X is P-space and for DC if X is collectionwise-normal space. The last result is related to the Telgársky's (1983) conjecture discussed in [1]. These results are not true for infinite product of spaces.     

Extended quasi-homogeneous polynomial system in {\mathbb{R}^{3}}

In this paper we define an extended quasi-homogeneous polynomial system d x/dt = Q = Q ₁ + Q ₂ + ... + Q _δ , where Q _i are some 3-dimensional quasi-homogeneous vectors with weight α and degree i, i = 1, . . . ,δ. Firstly we investigate the limit set of trajectory of this system. Secondly let Q _T be the projective vector field of Q. We show that if δ ≤ 3 and the number of closed orbits of Q _T is known, then an upper bound for the number of isolated closed orbits of the system is obtained. Moreover this upper bound is sharp for δ = 3. As an application, we show that a 3-dimensional polynomial system of degree 3 (resp. 5) admits 26 (resp. 112) isolated closed orbits. Finally, we prove that a 3-dimensional Lotka-Volterra system has no isolated closed orbits in the first octant if it is extended quasi-homogeneous.     

Evolving networks for social optima in the “weakest link game”

Previous models have applied evolving networks based on node-level “copy and rewire” rules to simple two player games (e.g. the Prisoner’s Dilemma). It was found that such models tended to evolve toward socially optimal behavior. Here we apply a similar technique to a more tricky co-ordination game (the weakest link game) requiring interactions from several players (nodes) that may play several strategies. We define a variant of the game with several equilibria—each offering increasing social benefit. We found that the evolving network functions to select and spread more optimal equilibria while resisting invasion by lower ones. Hence the network acts as a kind of “social ratchet” selecting for increasing social benefit. Such networks have applications in peer-to-peer computing and may have implications for understanding social systems.

Inequalities for the product of the volumes of a partition determined in a convex body by a surface

A generalization is given of the work of J. Bokowski [1] referring to the product of the volumes of the two parts into which a convex body is divided by a plane. The proof uses formulas of Integral Geometry and a conjecture of L. A. Santaló [2], and holds for the two parts determined by any (n?1)-dimensional surface in the euclideann-space and for dimensionsn=2, 3 in the hyperbolic space.