A linear algorithm for minimum 1-identifying codes in oriented trees

Consider an oriented graph G=(V,A), a subset of vertices C⊆V, and an integer r?1; for any vertex v∈V, let denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v∈V, the sets are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.     

A refinement of Cusick-Cheon bound for the second order binary Reed-Muller code

We prove a stronger form of the conjectured Cusick-Cheon lower bound for the number of quadratic balanced Boolean functions. We also prove various asymptotic results involving B(k,m), the number of balanced Boolean functions of degree ≤k in m variables, in the case k=2. Finally, we connect our results for k=2 with the (still unproved) conjectures of Cusick-Cheon for the functions B(k,m) with k>2.     

Monotonicity of the minimum cardinality of an identifying code in the hypercube

Let M_t(n) denote the minimum cardinality of a t-identifying code in the n-cube. It was conjectured that for all n?2 and t?1 we have M_t(n)?M_t(n+1). We prove this inequality for t=1.     

An upper bound on the domination number of a graph with minimum degree 2

A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let P_n and C_n denote a path and a cycle, respectively, on n vertices. Let k₁(F) and k₂(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P₃,P₄,P₅,C₅} and {P₁,P₂}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .     

A lower bound for the critical probability of the square lattice site percolation

Summary We prove by elementary combinatorial considerations that the critical probability of the square lattice site percolation is larger than 0.503478.Work supported by the Central Research Found of the Hungarian Academy of Sciences (Grant No. 476/82)     

A lower bound for the length of a partial transversal in a Latin square

It is proved that every n×n Latin square has a partial transversal of length at least n−O(log²n). The previous papers proving these results (including one by the second author) not only contained an error, but were sloppily written and quite difficult to understand. We have corrected the error and improved the clarity.     

Extremal perfect graphs for a bound on the domination number

We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+β_v(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and β_v(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs.     

A superlinear lower bound for the size of a critical set in a latin square

A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. Let scs(n) denote the smallest possible size of a critical set in a latin square of order n. We show that for all n, . Thus scs(n) is superlinear with respect to n. We also show that scs(n) ≥ 2n?32 and if n ≥ 25, . © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 269–282, 2007     

A new lower bound for the critical probability of site percolation on the square lattice

The critical probability for site percolation on the square lattice is not known exactly. Several authors have given rigorous upper and lower bounds. Some recent lower bounds are (each displayed here with the first three digits) 0.503 (Tóth [13]), 0.522 (Zuev [15]), and the best lower bound so far, 0.541 (Menshikov and Pelikh [12]). By a modification of the method of Menshikov and Pelikh we get a significant improvement, namely, 0.556. Apart from a few classical results on percolation and coupling, which are explicitly stated in the Introduction, this paper is self-contained. © 1996 John Wiley & Sons, Inc.     

New enumeration formulas for alternating sign matrices and square ice partition functions

The refined enumeration of alternating sign matrices (ASMs) of given order having prescribed behavior near one or more of their boundary edges has been the subject of extensive study, starting with the Refined Alternating Sign Matrix Conjecture of Mills–Robbins–Rumsey (1983) [25], its proof by Zeilberger (1996) [31], and more recent work on doubly-refined and triply-refined enumerations by several authors. In this paper we extend the previously known results on this problem by deriving explicit enumeration formulas for the “top–left–bottom” (triply-refined) and “top–left–bottom–right” (quadruply-refined) enumerations. The latter case solves the problem of computing the full boundary correlation function for ASMs. The enumeration formulas are proved by deriving new representations, which are of independent interest, for the partition function of the square ice model with domain wall boundary conditions at the “combinatorial point” η=2π/3$\eta =2\pi /3$.     

New lower bound for the Hilbert number in piecewise quadratic differential systems

We study the number of limit cycles bifurcating from a piecewise quadratic system. All the differential systems considered are piecewise in two zones separated by a straight line. We prove the existence of 16 crossing limit cycles in this class of systems. If we denote by $H_p(n)$ the extension of the Hilbert number to degree n piecewise polynomial differential systems, then $H_p(2)\ge 16$. As fas as we are concerned, this is the best lower bound for the quadratic class. Moreover, in the studied cases, all limit cycles appear nested bifurcating from a period annulus of a isochronous quadratic center.